Automata finiteness criterion in terms of van der Put series of automata functions

被引：19

作者：

Anashin V. ^{[1
]}

机构：

[1] Moscow State University, Leninskie Gory 1, Moscow

来源：

P-Adic Numbers, Ultrametric Analysis, and Applications | 2012年 / 4卷 / 2期

基金：

俄罗斯基础研究基金会;

关键词：

automata sequences; automaton; finiteness conditions; p-adic numbers; van der Put series;

D O I：

10.1134/S2070046612020070

中图分类号：

学科分类号：

摘要：

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. © 2012, Pleiades Publishing, Ltd.

引用

页码：151 / 160

页数：9

共 18 条

[1]

Allouche J.-P., Shallit J., Automatic Sequences. Theory, (2003)

[2]

Anashin V., Khrennikov A., Applied Algebraic Dynamics, (2009)

[3]

Anashin V.S., Khrennikov A.Y., Yurova E.I., Characterization of ergodicity of p-adic dynamical systems by using van der Put basis, DokladyMath, 83, 3, pp. 306-308, (2011)

[4]

Brauer W., Automatentheorie, (1984)

[5]

Grigorchuk R.I., Some topics in the dynamics of group actions on rooted trees, Proc. Steklov Inst. Math, 273, pp. 64-175, (2011)

[6]

Grigorchuk R.I., Nekrashevich V.V., Sushchanskii V.I., Automata, dynamical systems, and groups, Proc. Steklov Inst. Math, 231, pp. 128-203, (2000)

[7]

Hensel K., Über eine neue Begr ündung der Theorie der algebraischen Zahlen, Jahresbericht der Deutschen Mathematiker-Vereinigung, 6, 3, pp. 83-88, (1897)

[8]

Lunts A.G., The p-adic apparatus in the theory of finite automata, Problemy Kibernetiki, 14, pp. 17-30, (1965)

[9]

Mahler K., p-Adic Numbers and Their Functions, (1981)

[10]

Pin, “Profinite methods in automata theory,” in Symposium on Theoretical Aspects of Computer Science — STACS 2009, pp, 31–50 (Freiburg, (2009)

← 1 2 →