Syntactic Complexity of Ultimately Periodic Sets of Integers and Application to a Decision Procedure

• Autorzy: Lacroix, A. , Rampersad, N. , Rigo, M. , Vandomme, Ë.
• Języki publikacji: EN

Abstrakty

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.

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 116, nr 1-4
• Strony: 175-187
• Opis fizyczny: Bibliogr. 20 poz., tab.

Twórcy

autor

Lacroix, A.

autor

Rampersad, N.

autor

Rigo, M.

autor

Vandomme, Ë.

• Institute of Mathematics, University of Liege Grande Traverse 12 (B 37), B-4000 Liege, Belgium,

Bibliografia

• [1] B. Alexeev,Minimal DFA for testing divisibility, J. Comput. Syst. Sci. 69 (2004), 235-243.
• [2] J.-P. Allouche, N. Rampersad, J. Shallit, Periodicity, repetitions, and orbits of an automatic sequence, Theoret. Comput. Sci. 410 (2009), 2795-2803.
• [3] 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.
• [4] V. Berthé, M. Rigo (Eds), Combinatorics, Automata and Number Theory, Encyclopedia of Mathematics and its Applications 135, Cambridge University Press (2010).
• [5] V. Bruyère, G. Hansel, C. Michaux, R. Villemaire, Logic and p-recognizable sets of integers, Bull. Belg. Math. Soc. 1 (1994), 191-238.
• [6] 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).
• [7] J. Brzozowski, Y. Ye, Syntactic Complexity of Ideal and Closed Languages, preprint (2010) arXiv:1010.3263v1
• [8] E. Charlier, N. Rampersad, M. Rigo, L. Waxweiler, The minimal automaton recognizing mN in a linear numeration system, INTEGERS 11b (2011), #A4.
• [9] 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.
• [10] F. Durand, Decidability of the HD0L ultimate periodicity problem, preprint (2011) arXiv:1111.3268.
• [11] S. Eilenberg, Automata, Languages and Machines, Vol. A, Academic Press, New York, 1974.
• [12] 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.
• [13] T. Harju,M. Linna, On the periodicity of morphisms on freemonoids, RAIRO Inform. Théor. Appl. 20 (1986), 47-54.
• [14] J. Honkala, A decision method for the recognizability of sets defined by number systems, Theor. Inform. Appl. 20 (1986), 395-403.
• [15] J. Honkala,M. Rigo, A note on decidability questions related to abstract numeration systems, Discrete Math. 285 (2004), 329-333.
• [16] I.Mitrofanov, A proof for the decidability of HD0L ultimate periodicity, preprint (2011) arXiv:1110.4780.
• [17] J. Myhill, Finite automata and representation of events, Wright Air Development Center Technical Report 57-624 (1957).
• [18] 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.).
• [19] M. Perles, M. O. Rabin, E. Shamir, The theory of definite automata, IEEE Trans. Electron. Comp. (1963) 233-243.
• [20] 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.