Divisibility criterion; State complexity; Periodicity; Numeration system; Automata
Abstract :
[en] 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 mN in the Fibonacci system is exactly 2m^2.
Disciplines :
Computer science Mathematics
Author, co-author :
Charlier, Emilie ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Rampersad, Narad ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Rigo, Michel ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Waxweiler, Laurent ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
State complexity of testing divisibility
Publication date :
2010
Event name :
Descriptional Complexity of Formal Systems DFCS 2010
Event organizer :
University of Saskatchewan
Event place :
Saskatoon, Canada
Event date :
from 8-8-2010 to 10-8-2010
Audience :
International
Journal title :
Electronic Proceedings in Theoretical Computer Science
