Minimal DFAs for Testing Divisibility

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We present and prove a theorem answering the question "how many states does a minimal deterministic finite automaton (DFA) that recognizes the set of base-b numbers divisible by k have?"
LaTeX, 7 pages (corrected typo in new version)

Keywords

Computational Complexity, F.1.1; F.4.3

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/130404

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0309052
 http://arxiv.org/abs/cs/0309052
 J. Comput. System Sci. 69 (2004), no. 2, 235--243
 doi:10.1016/j.jcss.2004.02.001

Collections

arXiv