Reference : Syntactical complexity of periodic sets
Scientific congresses and symposiums : Unpublished conference
Physical, chemical, mathematical & earth Sciences : Mathematics
http://hdl.handle.net/2268/125591
Syntactical complexity of periodic sets
English
Charlier, Emilie mailto [Université Libre de Bruxelles - ULB > Département de mathématique > Géométrie, Théorie des Groupes et Combinatoire > >]
Jun-2012
No
Yes
International
First Joint Conference of the Belgian, Royal Spanish and Luxembourg Mathematical Societies
du 6 juin 2012 au 8 juin 2012
Liege
Belgium
[en] automaton ; state complexity ; syntactic complexity ; recognizable sets ; ultimately periodic sets
[en] We are interested in the links between numbers and their representations. In the decimal numeration system, a number is even if its representation ends with 0, 2, 4, 6, or 8, which give rise to a simple representation set, that is, accepted by a finite automaton. More generally, in an integer base numeration system, any divisibility criterion is recognized by a finite automaton.
The state complexity of a regular language is the number of states of the minimal automaton accepting this language. The syntactic complexity is the size of the associated syntactical monoid. The first one only takes into account the context on the right side, whereas the second considers both left and right contexts.
Given a set of integers, we want to answer the following questions. What is the associated state complexity? What is the associated syntactic complexity? These questions extend to more general numeration systems, as linear numeration systems or abstract numeration systems. Such problems are motivated by decidability problems. For example : given an automaton recognizing a set of integers, decide if this set is ultimately periodic?
Researchers
http://hdl.handle.net/2268/125591

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
Charlier-expose-Liege2012.pdfAuthor preprint293.54 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.