Syntactic complexity of ultimately periodic sets of integers and application to a decision procedure

Lacroix, Anne; Rampersad, Narad; Rigo, Michel; Vandomme, Elise

doi:10.3233/FI-2012-677

Download

Article (Scientific journals)

Syntactic complexity of ultimately periodic sets of integers and application to a decision procedure

Lacroix, Anne; Rampersad, Narad; Rigo, Michel et al.

2012 • In Fundamenta Informaticae, 116, p. 175-187

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/2268/127570

DOI
10.3233/FI-2012-677

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

final.pdf

Author preprint (148.19 kB)

Download

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

integer base; syntactic monoid; complexity; ultimately periodic set; decision problem

Abstract :

[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 a well studied problem: decide whether or not a b-recognizable set of integers is ultimately periodic.

Disciplines :

Computer science
Mathematics

Author, co-author :

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

Rampersad, Narad

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 and application to a decision procedure

Publication date :

2012

Journal title :

Fundamenta Informaticae

ISSN :

0169-2968

Publisher :

IOS Press

Volume :

116

Pages :

175-187

Peer reviewed :

Peer Reviewed verified by ORBi

Available on ORBi :

since 16 July 2012

Statistics

Number of views

199 (30 by ULiège)

Number of downloads

274 (16 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

B. Alexeev,Minimal DFA for testing divisibility, J. Comput. Syst. Sci. 69 (2004), 235-243.
J.-P. Allouche, N. Rampersad, J. Shallit, Periodicity, repetitions, and orbits of an automatic sequence, Theoret. Comput. Sci. 410 (2009), 2795-2803.
J. P. Bell, E. Charlier, A. S. Fraenkel,M. Rigo, A decision problemfor ultimately periodic sets in non-standard numeration systems, Int. J. Algebra and Computation 19 (2009), 809-839.
V. Berthé, M. Rigo (Eds), Combinatorics, Automata and Number Theory, Encyclopedia of Mathematics and its Applications 135, Cambridge University Press (2010).
V. Bruyère, G. Hansel, C. Michaux, R. Villemaire, Logic and p-recognizable sets of integers, Bull. Belg. Math. Soc. 1 (1994), 191-238.
J. A. Brzozowski, Canonical Regular Expressions andMinimal State Graphs for Definite Events, Proceedings of the Symposium on Mathematical Theory of Automata New York, NY, April 24-26, 1962 J. Fox, ed., MRI Symposia Series, Vol. 12 Polytechnic Press of the Polytechnic Institute of Brooklyn, Brooklyn, NY pp. 529- 561, (1963).
J. Brzozowski, Y. Ye, Syntactic Complexity of Ideal and Closed Languages, preprint (2010) arXiv:1010.3263v1
E. Charlier, N. Rampersad, M. Rigo, L. Waxweiler, The minimal automaton recognizing mN in a linear numeration system, INTEGERS 11b (2011), #A4.
F. Durand, HD0L equivalence and periodicity problems in the primitive case (to the memory of G. Rauzy), to appear in J. of Uniform Distribution Theory.
F. Durand, Decidability of the HD0L ultimate periodicity problem, preprint (2011) arXiv:1111.3268.
S. Eilenberg, Automata, Languages and Machines, Vol. A, Academic Press, New York, 1974.
V. Halava, T. Harju, T. Kärki, A new proof for the decidability of D0L ultimate periodicity, in Proceedings of WORDS 2011, EPTCS 63, (2011), 147-151.
T. Harju,M. Linna, On the periodicity of morphisms on freemonoids, RAIRO Inform. Théor. Appl. 20 (1986), 47-54.
J. Honkala, A decision method for the recognizability of sets defined by number systems, Theor. Inform. Appl. 20 (1986), 395-403.
J. Honkala,M. Rigo, A note on decidability questions related to abstract numeration systems, Discrete Math. 285 (2004), 329-333.
I.Mitrofanov, A proof for the decidability of HD0L ultimate periodicity, preprint (2011) arXiv:1110.4780.
J. Myhill, Finite automata and representation of events, Wright Air Development Center Technical Report 57-624 (1957).
M. Rigo, E. Vandomme, Syntactic complexity of ultimately periodic sets of integers, Proceedings of the fifth conference LATA (Languages and Automata, Theory and Applications), Lect. Notes in Comput. Sci. 6638, Springer Verlag (2011), 477-488, A.-H. Dediu, S. Inenaga, C. Martin-Vide (Eds.).
M. Perles, M. O. Rabin, E. Shamir, The theory of definite automata, IEEE Trans. Electron. Comp. (1963) 233-243.
J.-E. Pin, Syntactic semigroups, Chap. 10 in Handbook of language theory, Vol. I, G. Rozenberg and A. Salomaa (ed.), Springer Verlag, (1997), 679-746.