automaton; state complexity; syntactic complexity; recognizable sets; ultimately periodic sets
Abstract :
[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?
Disciplines :
Mathematics
Author, co-author :
Charlier, Emilie ; Université Libre de Bruxelles - ULB > Département de mathématique > Géométrie, Théorie des Groupes et Combinatoire
Language :
English
Title :
Syntactical complexity of periodic sets
Publication date :
June 2012
Event name :
First Joint Conference of the Belgian, Royal Spanish and Luxembourg Mathematical Societies
