Reference : Syntactical complexity of periodic sets
Scientific congresses and symposiums : Unpublished conference
Physical, chemical, mathematical & earth Sciences : Mathematics
Syntactical complexity of periodic sets
Charlier, Emilie mailto [Université Libre de Bruxelles - ULB > Département de mathématique > Géométrie, Théorie des Groupes et Combinatoire > >]
First Joint Conference of the Belgian, Royal Spanish and Luxembourg Mathematical Societies
du 6 juin 2012 au 8 juin 2012
[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?

File(s) associated to this reference

Fulltext file(s):

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.