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.
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
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
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
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)
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.: 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
Similar publications
Sorry the service is unavailable at the moment. Please try again later.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.
