Electronic Proceedings in Theoretical Computer Science (Aug 2010)

State Complexity of Testing Divisibility

  • Emilie Charlier,
  • Narad Rampersad,
  • Michel Rigo,
  • Laurent Waxweiler

DOI
https://doi.org/10.4204/EPTCS.31.7
Journal volume & issue
Vol. 31, no. Proc. DCFS 2010
pp. 48 – 57

Abstract

Read online

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.