You are here:
| 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  [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 >] | |
| 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):
| ||||||||||||||
All documents in ORBi are protected by a user license.
