State Complexity of Testing Divisibility

Emilie Charlier
Narad Rampersad
Michel Rigo
Laurent Waxweiler

Under some mild assumptions, we study the state complexity of the trim minimal automaton accepting the greedy representations of the multiples of m >= 2 for a wide class of linear numeration systems. As an example, the number of states of the trim minimal automaton accepting the greedy representations of the multiples of m in the Fibonacci system is exactly 2m^2.

In Ian McQuillan and Giovanni Pighizzini: Proceedings Twelfth Annual Workshop on Descriptional Complexity of Formal Systems (DCFS 2010), Saskatoon, Canada, 8-10th August 2010, Electronic Proceedings in Theoretical Computer Science 31, pp. 48–57.
Published: 7th August 2010.

ArXived at: http://dx.doi.org/10.4204/EPTCS.31.7 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org