Syntactic complexity of ultimately periodic sets of integers

[en] We compute the cardinality of the syntactic monoid of the language 0^∗rep_b(mN) made of base b expansions of the multiples of the integer m. We also give lower bounds for the syntactic complexity of any (ultimately) periodic set of integers written in base b. We apply our results to some well studied problem: decide whether or not a b-recognizable sets of integers is ultimately periodic.

Disciplines :

Computer science
Mathematics

Author, co-author :

Rigo, Michel ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes

Vandomme, Elise ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes

Language :

English

Title :

Syntactic complexity of ultimately periodic sets of integers

Publication date :

2011

Event name :

LATA 2011 (5th conf. Languages and Automata, Theory and Applications)

Event place :

Tarragona, Spain

Event date :

from 26-05-2011 to 30-05-2011

Audience :

International

Journal title :

Lecture Notes in Computer Science

ISSN :

0302-9743

eISSN :

1611-3349

Publisher :

Springer, Berlin, Germany

Volume :

6638

Pages :

477-488

Peer reviewed :

Peer reviewed

Available on ORBi :

since 25 February 2011

Statistics

Number of views

197 (36 by ULiège)

Number of downloads

3 (2 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

Bibliography

Alexeev, B.: Minimal DFA for testing divisibility. J. Comput. System Sci. 69(2), 235–243 (2004)
Allouche, J.P., Rampersad, N., Shallit, J.: Periodicity, repetitions, and orbits of an automatic sequence. Theoret. Comput. Sci. 410(30-32), 2795–2803 (2009)
Bell, J.P., Charlier, E., Fraenkel, A.S., Rigo, M.: A decision problem for ultimately periodic sets in non-standard numeration systems. Int. J. Algebra and Computation 19, 809–839 (2009)
Berthé, V., Rigo, M. (eds.): Combinatorics, Automata and Number Theory. Encyclopedia of Mathematics and its Applications, vol. 135. Cambridge University Press, Cambridge (2010)
Bruyère, V., Hansel, G., Michaux, C., Villemaire, R.: Logic and p-recognizable sets of integers. Bull. Belg. Math. Soc. 1, 191–238 (1994)
Brzozowski, J., Ye, Y.: Syntactic complexity of ideal and closed languages. preprint arXiv:1010.3263v1 (2010)
Brzozowski, J.A.: Canonical regular expressions and minimal state graphs for definite events. In: Fox, J. (ed.) Proceedings of the Symposium on Mathematical Theory of Automata New York. MRI Symposia Series, vol. 12, pp. 529–561. Polytechnic Press of the Polytechnic Institute of Brooklyn (1963)
Charlier, E., Rampersad, N., Rigo, M., Waxweiler, L.: The minimal automaton recognizing mN in a linear numeration system. Integers (to appear)
Eilenberg, S.: Automata, Languages, and Machines, vol. A. Academic Press, London (1974)
Honkala, J.: A decision method for the recognizability of sets defined by number systems. Theor. Inform. Appl. 20, 395–403 (1986)
Honkala, J., Rigo, M.: A note on decidability questions related to abstract numeration systems. Discrete Math. 285, 329–333 (2004)
Myhill, J.: Finite automata and representation of events. Technical Report 57-624, Wright Air Development Center Technical Report (1957)
Perles, M., Rabin, M.O., Shamir, E.: The theory of definite automata. IEEE Trans. Electron. Comp., 233–243 (1963)
Pin, J.E.: Syntactic semigroups. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Language Theory, vol. I, pp. 679–746. Springer, Heidelberg (1997)