Reference : State complexity of testing divisibility
Scientific congresses and symposiums : Paper published in a book
Physical, chemical, mathematical & earth Sciences : Mathematics
Engineering, computing & technology : Computer science
http://hdl.handle.net/2268/64877
State complexity of testing divisibility
English
Charlier, Emilie mailto [Université de Liège - ULg > Département de mathématique > Mathématiques discrètes >]
Rampersad, Narad [Université de Liège - ULg > Département de mathématique > Mathématiques discrètes >]
Rigo, Michel mailto [Université de Liège - ULg > Département de mathématique > Mathématiques discrètes >]
Waxweiler, Laurent [Université de Liège - ULg > Département de mathématique > Mathématiques discrètes >]
Aug-2010
Proceedings Twelfth Annual Workshop on Descriptional Complexity of Formal Systems
McQuillan, Ian, Pighizzini, Giovanni
48-57
Yes
No
International
2075-2180
Descriptional Complexity of Formal Systems DFCS 2010
from 8-8-2010 to 10-8-2010
University of Saskatchewan
Saskatoon
Canada
[en] Divisibility criterion ; State complexity ; Periodicity ; Numeration system ; Automata
[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.
Researchers
http://hdl.handle.net/2268/64877
10.4204/EPTCS.31
http://cgi.cse.unsw.edu.au/~rvg/eptcs/Published/DCFS2010/Papers/toc/DCFS2010.html

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
dcfs-crrw.pdfAuthor postprint165.33 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.