×

Automata finiteness criterion in terms of van der Put series of automata functions. (English) Zbl 1262.11045

Summary: In the paper we develop the \(p\)-adic theory of discrete automata. Every automaton \(\mathfrak{A}\) (transducer) whose input/output alphabets consist of \(p\) symbols can be associated to a continuous (in fact, 1-Lipschitz) map from \(p\)-adic integers to \(p\)-adic integers, the automaton function \(f_{\mathfrak{A}}\). The \(p\)-adic theory (in particular, the \(p\)-adic ergodic theory) turned out to be very efficient in a study of properties of automata expressed via properties of automata functions. In the paper we prove a criterion for finiteness of the number of states of automaton in terms of van der Put series of the automaton function. The criterion displays connections between \(p\)-adic analysis and the theory of automata sequences.

MSC:

11B85 Automata sequences
11S80 Other analytic theory (analogues of beta and gamma functions, \(p\)-adic integration, etc.)
68Q45 Formal languages and automata
37B15 Dynamical aspects of cellular automata
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] J.-P. Allouche and J. Shallit, Automatic Sequences. Theory, Applications, Generalizations (Cambridge Univ. Press, 2003). · Zbl 1086.11015
[2] V. Anashin and A. Khrennikov, Applied Algebraic Dynamics, de Gruyter Expositions in Mathematics 49 (Walter de Gruyter GmbH & Co., Berlin, N.Y., 2009). · Zbl 1184.37002
[3] V. S. Anashin, A. Yu. Khrennikov and E. I. Yurova, ”Characterization of ergodicity of p-adic dynamical systems by using van der Put basis,” DokladyMath. 83(3), 306–308 (2011). · Zbl 1247.37007
[4] W. Brauer, Automatentheorie (B. G. Teubner, Stuttgart, 1984).
[5] R. I. Grigorchuk, ”Some topics in the dynamics of group actions on rooted trees,” Proc. Steklov Inst. Math. 273, 64–175 (2011). · Zbl 1268.20027 · doi:10.1134/S0081543811040067
[6] R. I. Grigorchuk, V. V. Nekrashevich and V. I. Sushchanskii, ”Automata, dynamical systems, and groups,” Proc. Steklov Inst. Math. 231, 128–203 (2000). · Zbl 1155.37311
[7] K. Hensel, ”Über eine neue Begr ündung der Theorie der algebraischen Zahlen,” Jahresbericht der Deutschen Mathematiker-Vereinigung 6(3), 83–88 (1897). · JFM 30.0096.03
[8] A. G. Lunts, ”The p-adic apparatus in the theory of finite automata,” Problemy Kibernetiki 14, 17–30 (1965) [in Russian].
[9] K. Mahler, p-Adic Numbers and Their Functions (Cambridge Univ. Press, 1981). · Zbl 0444.12013
[10] J.-E. Pin, ”Profinite methods in automata theory,” in Symposium on Theoretical Aspects of Computer Science – STACS 2009, pp. 31–50 (Freiburg, 2009). · Zbl 1236.68175
[11] W. H. Schikhof, Ultrametric Calculus (Cambridge Univ. Press, 1984). · Zbl 0553.26006
[12] V. S. Vladimirov and I. V. Volovich, ”Superanalysis 1. Differential calculus,” Theor. Math. Phys. 59, 317–335 (1984). · Zbl 0552.46023 · doi:10.1007/BF01028510
[13] V. S. Vladimirov and I. V. Volovich, ”Superanalysis 2. Integral calculus,” Theor. Math. Phys. 60, 743–765 (1985). · Zbl 0599.46068 · doi:10.1007/BF01018974
[14] V. S. Vladimirov, I. V. Volovich and E. I. Zelenov, p-Adic Analysis and Mathematical Physics (Scientific, Singapore, 1994). · Zbl 0812.46076
[15] I. V. Volovich, ”p-Adic string,” Class. Quant. Grav. 4, 83–87 (1987). · Zbl 0636.12015 · doi:10.1088/0264-9381/4/4/003
[16] J. Vuillemin, ”On circuits and numbers,” IEEE Trans. Comp. 43(8), 868–879 (1994). · Zbl 1066.68506 · doi:10.1109/12.295849
[17] J. Vuillemin, ”Finite digital synchronous circuits are characterized by 2-algebraic truth tables,” in Advances in Computing Science – ASIAN 2000, Lect. Notes Comp. Sci. 1961, 1–7 (2000). · Zbl 0987.94049 · doi:10.1007/3-540-44464-5_1
[18] J. Vuillemin, ”Digital algebra and circuits,” in Verification: Theory and Practice, Lect. Notes Comp. Sci. 2772, 733–746 (2003). · Zbl 1274.94164 · doi:10.1007/978-3-540-39910-0_31
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.