Magic Numbers in Periodic Sequences

Automatic sequences; Constant-recursive sequences; Magic numbers; Periodic sequences; Regular sequences; Constant-recursive sequence; Deterministic finite automata; Formal languages and automata; Integer-N; Nondeterministic finite automaton; Periodic sequence; Recursive sequences; Regular sequence; Theoretical Computer Science; Computer Science (all)

Abstract :

In formal languages and automata theory, the magic number problem can be formulated as follows: for a given integer n, is it possible to find a number d in the range [ n, 2 n] such that there is no minimal deterministic finite automaton with d states that can be simulated by a minimal nondeterministic finite automaton with exactly n states? If such a number d exists, it is called magic. In this paper, we consider the magic number problem in the framework of deterministic automata with output, which are known to characterize automatic sequences. More precisely, we investigate magic numbers for periodic sequences viewed as either automatic, regular, or constant-recursive.

Disciplines :

Mathematics

Author, co-author :

Kreczman, Savinien ; Université de Liège - ULiège > Mathematics

Prigioniero, Luca ; Dipartimento di Informatica, Università degli Studi di Milano, Milan, Italy

Rowland, Eric ; Department of Mathematics, Hofstra University, Hempstead, United States

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

Language :

English

Title :

Magic Numbers in Periodic Sequences

Publication date :

2023

Event name :

14th International Conference on WORDS 2023

Event place :

Umeå, Swe

Event date :

12-06-2023 => 16-06-2023

Audience :

International

Main work title :

Combinatorics on Words - 14th International Conference, WORDS 2023, Proceedings

Editor :

Frid, Anna

Publisher :

Springer Science and Business Media Deutschland GmbH

ISBN/EAN :

978-3-03-133179-4

Pages :

206—219

Peer reviewed :

Peer reviewed

Additional URL :

https://link.springer.com/content/pdf/10.1007/978-3-031-33180-0_16

Funders :

F.R.S.-FNRS - Fonds de la Recherche Scientifique

Available on ORBi :

since 30 May 2024

Statistics

Number of views

91 (20 by ULiège)

Number of downloads

104 (3 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenAlex citations

Bibliography

Alexeev, B.: Minimal DFA for testing divisibility. J. Comput. Syst. Sci. 69(2), 235–243 (2004). https://doi.org/10.1016/j.jcss.2004.02.001
Allouche, J.P., Shallit, J.O.: The ring of k-regular sequences. Theor. Comput. Sci. 98(2), 163–197 (1992). https://doi.org/10.1016/0304-3975(92)90001-V
Allouche, J.P., Shallit, J.O.: Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, Cambridge (2003)
Berstel, J., Reutenauer, C.: Noncommutative Rational Series with Applications, Encyclopedia of Mathematics and its Applications, vol. 137. Cambridge University Press, Cambridge (2011)
Boigelot, B., Mainz, I., Marsault, V., Rigo, M.: An efficient algorithm to decide periodicity of b-recognisable sets using MSDF convention. In: ICALP 2017. LIPIcs, vol. 80, pp. 118:1–118:14. Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2017). https://doi.org/10.4230/LIPIcs.ICALP.2017.118
Bosma, W.: Complexity of periodic sequences (2019). Preprint available at https://www.math.ru.nl/~bosma/pubs/periodic.pdf
Büchi, R.J.: Weak second-order arithmetic and finite automata. Math. Log. Q. 6(1–6), 66–92 (1960). https://doi.org/10.1002/malq.19600060105
Cobham, A.: Uniform tag sequences. Math. Systems Theory 6, 164–192 (1972). https://doi.org/10.1007/BF01706087
Everest, G., van der Poorten, A.J., Shparlinski, I.E., Ward, T.: Recurrence Sequences, Mathematical Surveys and Monographs, vol. 104. American Mathematical Society (2003)
Garrett, P.B.: Abstract Algebra. Chapman & Hall/CRC, Boca Raton (2008)
Geffert, V.: (Non)determinism and the size of one-way finite automata. In: DCFS 2005. Proceedings, pp. 23–37. Università degli Studi di Milano, Milan, Italy (2005)
Geffert, V.: Magic numbers in the state hierarchy of finite automata. Inf. Comput. 205(11), 1652–1670 (2007). https://doi.org/10.1016/j.ic.2007.07.001
Hiller, H.: The crystallographic restriction in higher dimensions. Acta Crystallogr. A 41(6), 541–544 (1985). https://doi.org/10.1107/S0108767385001180
Holzer, M., Jakobi, S., Kutrib, M.: The magic number problem for subregular language families. Int. J. Found. Comput. Sci. 23(1), 115–131 (2012). https://doi. org/10.1142/S0129054112400084
Honkala, J.: A decision method for the recognizability of sets defined by number systems. RAIRO Theor. Inform. Appl. 20(4), 395–403 (1986). https://doi.org/10. 1051/ita/1986200403951
Iwama, K., Kambayashi, Y., Takaki, K.: Tight bounds on the number of states of DFAs that are equivalent to n-state NFAs. Theor. Comput. Sci. 237(1–2), 485–494 (2000). https://doi.org/10.1016/S0304-3975(00)00029-3
Iwama, K., Matsuura, A., Paterson, M.: A family of NFAs which need 2n − α deterministic states. Theor. Comput. Sci. 301(1–3), 451–462 (2003). https://doi. org/10.1016/S0304-3975(02)00891-5
Jirásková, G.: Deterministic blow-ups of minimal NFA’s. RAIRO Theor. Inf. Appl. 40(3), 485–499 (2006). https://doi.org/10.1051/ita:2006032
Jirásková, G.: On the state complexity of complements, stars, and reversals of regular languages. In: DLT 2008. Proceedings. LNCS, vol. 5257, pp. 431–442. Springer, Cham (2008). https://doi.org/10.1007/978-3-540-85780-8_34
Jirásková, G.: Magic numbers and ternary alphabet. Int. J. Found. Comput. Sci. 22(2), 331–344 (2011). https://doi.org/10.1142/S0129054111008076
Koo, R.: A classification of matrices of finite order over C, R and Q. Math. Mag. 76(2), 143–148 (2003)
Marsault, V.: An efficient algorithm to decide periodicity of b-recognisable sets using LSDF convention. Log. Methods Comput. Sci. 15(3) (2019). https://doi. org/10.23638/LMCS-15(3:8)2019
Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars, and formal systems. In: 12th Annual Symposium on Switching and Automata Theory, East Lansing, Michigan, USA, 13–15 October 1971, pp. 188–191. IEEE Computer Society (1971). https://doi.org/10.1109/SWAT.1971.11
Ouaknine, J., Worrell, J.: Decision problems for linear recurrence sequences. In: RP 2012. LNCS, vol. 7550, pp. 21–28. Springer, Heidelberg (2012). https://doi. org/10.1007/978-3-642-33512-9_3
Sloane, N.J.A.: The On-Line Encyclopedia of Integer Sequences. http://oeis.org
Sutner, K.: Divisibility and state complexity. Mathematica J. 11(3), 430–445 (2009). https://doi.org/10.3888/tmj.11.3-8
Sutner, K., Tetruashvili, S.: Inferring automatic sequences (2012). https://www. cs.cmu.edu/~sutner/papers/auto-seq.pdf
Zantema, H., Bosma, W.: Complexity of automatic sequences. Inf. Comput. 288, 104710 (2022). https://doi.org/10.1016/j.ic.2021.104710. Special Issue: Selected Papers of the 14th International Conference on Language and Automata Theory and Applications, LATA 2020