A new hierarchy for automaton semigroups. (English) Zbl 1474.68168
Summary: We define a new strict and computable hierarchy for the family of automaton semigroups, which reflects the various asymptotic behaviors of the state-activity growth. This hierarchy extends that given by
S. Sidki [J. Math. Sci., New York 100, No. 1, 1925–1943 (2000; Zbl 1069.20504)]
for automaton groups, and also gives new insights into the latter. Its exponential part coincides with a notion of entropy for some associated automata.
We prove that the Order Problem is decidable whenever the state-activity is bounded. The Order Problem remains open for the next level of this hierarchy, that is, when the state-activity is linear. P. Gillibert [Int. J. Algebra Comput. 24, No. 1, 1–9 (2014; Zbl 1292.20040)] showed that it is undecidable in the whole family.
We extend the aforementioned hierarchy via a semi-norm making it more coarse but somehow more robust and we prove that the Order Problem is still decidable for the first two levels of this alternative hierarchy.
We prove that the Order Problem is decidable whenever the state-activity is bounded. The Order Problem remains open for the next level of this hierarchy, that is, when the state-activity is linear. P. Gillibert [Int. J. Algebra Comput. 24, No. 1, 1–9 (2014; Zbl 1292.20040)] showed that it is undecidable in the whole family.
We extend the aforementioned hierarchy via a semi-norm making it more coarse but somehow more robust and we prove that the Order Problem is still decidable for the first two levels of this alternative hierarchy.
Software:
FRReferences:
| [1] | Akhavi, A., Klimann, I., Lombardy, S., Mairesse, J. and Picantin, M., The finiteness problem for automaton semigroups, Int. J. Alg. Comput.22(6) (2012) 1-26. · Zbl 1280.20038 |
| [2] | Antonenko, A. S., On transition functions of Mealy automata of finite growth, Matematychni Studii.29(1) (2008) 3-17. · Zbl 1164.20368 |
| [3] | Bartholdi, L., Algorithmic decidability of Engel’s property for automaton groups, CSR 2016, , Vol. 9691 (2016), pp. 29-40. · Zbl 1477.20067 |
| [4] | L. Bartholdi, \( \mathtt{F} \mathtt{R}-\mathtt{G} \mathtt{A} \mathtt{P}\) package “Computations with functionally recursive groups”, Version 2.4.3 (2017), http://www.gap-system.org/Packages/fr.html. |
| [5] | L. Bartholdi and I. Mitrofanov, The word and order problems for self-similar and automata groups (2017), https://arxiv.org/abs/1710.10109. · Zbl 1496.20056 |
| [6] | Bartholdi, L., Reznykov, I. I. and Sushchansky, V. I., The smallest mealy automaton of intermediate growth, J. Algebra295(2) (2006) 387-414. · Zbl 1095.20045 |
| [7] | Bartholdi, L. and Silva, P. V., Groups defined by automata, AutoMathA Handbook, ed. Pin, J.-É. (Europ. Math. Soc., 2018), https://arxiv.org/abs/1012.1531. |
| [8] | Bondarenko, I., Bondarenko, N., Sidki, S. and Zapata, F., On the conjugacy problem for finite-state automorphisms, Groups Geom. Dyn.7(2) (2013) 323-355. · Zbl 1286.20034 |
| [9] | I. Bondarenko and J. P. Wächter, On orbits and the finiteness of bounded automaton groups (2019), https://arxiv.org/abs/1912.06897. |
| [10] | Chomsky, N. and Miller, G. A., Finite state languages, Inform. Control1(2) (1958) 91-112. · Zbl 0081.14503 |
| [11] | Gawrychowski, P., Krieger, D., Rampersad, N. and Shallit, J., Finding the growth rate of a regular of context-free language in polynomial time, Developments in Language Theory(Berlin, Heidelberg) (Ito, Masami and Toyama, Masafumi, eds.) (Springer, Berlin, Heidelberg, 2008), pp. 339-358. · Zbl 1161.68528 |
| [12] | Gillibert, P., The finiteness problem for automaton semigroups is undecidable, Int. J. Alg. Comput.24(1) (2014) 1-9. · Zbl 1292.20040 |
| [13] | Gillibert, P., An automaton group with undecidable order and Engel problems, J. Algebra497 (2018) 363-392. · Zbl 1427.20040 |
| [14] | Godin, Th. and Klimann, I., On bireversible Mealy automata and the Burnside problem, Theor. Comput. Sci.707 (2018) 24-35. · Zbl 1405.68196 |
| [15] | Klimann, I., Mairesse, J., and Picantin, M., Implementing computations in automaton (semi)groups, CIAA 2012, , Vol. 7381 (2012), pp. 240-252. · Zbl 1297.68145 |
| [16] | Klimann, I. and Picantin, M., A characterization of those automata that structurally generate finite groups, LATIN 2014: Theoretical Informatics — 11th Latin American Symposium, Proceedings, Montevideo, Uruguay, , March 31-April 4 (2014), pp. 180-189. · Zbl 1407.68319 |
| [17] | Lind, D. A., The entropies of topological markov shifts and a related class of algebraic integers, Ergod. Th. Dyn. Syst.4(2) (1984) 283-300. · Zbl 0546.58035 |
| [18] | Lind, D. A. and Marcus, B., An Introduction to Symbolic Dynamics and Coding (Cambridge University Press, 1995). · Zbl 1106.37301 |
| [19] | M. Picantin, Automates, (semi)groupes, dualités, Habilitation à diriger des recherches, Univ Paris Diderot (2017), https://www.irif.fr/˜picantin/hdr.pdf. |
| [20] | Rabin, M. O. and Scott, D., Finite automata and their decision problems, IBM J. Res. Development3(2) (1959) 114-125. · Zbl 0158.25404 |
| [21] | Rigo, M., Words and Sequences from Scratch, Chap. 1 (John Wiley & Sons, Ltd, 2014), pp. 1-83. |
| [22] | Rigo, M., Advanced Graph Theory and Combinatorics (Wiley, 2016). · Zbl 1369.05001 |
| [23] | Russyev, A., Finite groups as groups of automata with no cycles with exit, Algebra and Discr. Math.9(1) (2010) 86-102. · Zbl 1209.20026 |
| [24] | Sakarovitch, J., Elements of Automata Theory (Cambridge University Press, 2009). · Zbl 1188.68177 |
| [25] | Shur, A. M., Combinatorial complexity of regular languages, CSR’08, , Vol. 5010 (2008), pp. 289-301. · Zbl 1142.68428 |
| [26] | Shur, A. M., Comparing complexity functions of a language and its extendable part, RAIRO-Theor. Inf. Appl.42(3) (2008) 647-655. · Zbl 1149.68055 |
| [27] | Sidki, S., Automorphisms of one-rooted trees: Growth, circuit structure, and acyclicity, J. Math. Sci.100(1) (2000) 1925-1943. · Zbl 1069.20504 |
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.
