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