zbMATH — the first resource for mathematics

Automaton semigroups: the two-state case. (English) Zbl 1345.20074
A Mealy automaton $$(A,\Sigma,\delta=(\delta_i\colon A\to A)_{i\in\Sigma},\rho=(\rho_x\colon\Sigma\to\Sigma)_{x\in A})$$ is invertible if the output functions $$\rho_x$$ are permutations of the input-output alphabet $$\Sigma$$ and reversible if the state transition functions $$\delta_i$$ are permutations of the set of states $$A$$. The output functions $$\rho_x$$, $$x\in A$$, can in natural way be extended to mappings $$\Sigma^*\to\Sigma^*$$; it is proved, that the semigroup of a two-state reversible Mealy automaton generated by these mappings is either finite or free; for invertible automaton is presented also an effective decision procedure.

MSC:
 20M35 Semigroups in automata theory, linguistics, etc. 68Q45 Formal languages and automata 20M05 Free semigroups, generators and relations, word problems 03B25 Decidability of theories and sets of sentences 03D05 Automata and formal grammars in connection with logical questions
Software:
FR; AutomGrp; GAP; automata
Full Text:
References:
 [1] Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The design and analysis of computer algorithms. Addison-Wesley (1974) · Zbl 0326.68005 [2] Akhavi, A; Klimann, I; Lombardy, S; Mairesse, J; Picantin, M, On the finiteness problem for automaton (semi)groups, Int. J. Algebra Comput., 22, 26, (2012) · Zbl 1280.20038 [3] Alešin, SV, Finite automata and the Burnside problem for periodic groups, Mat. Zametki, 11, 319-328, (1972) [4] Antonenko, AS, On transition functions of mealy automata of finite growth, Matematychni Studii, 29, 3-17, (2008) · Zbl 1164.20368 [5] Bartholdi, L.: FR Functionally recursive groups - a GAP package, v.1.2.4.2 (2011) · Zbl 1239.20033 [6] Bartholdi, L; Reznykov, II; Sushchanskiı̆, VI, The smallest mealy automaton of intermediate growth, J. Algebra, 295, 387-414, (2006) · Zbl 1095.20045 [7] Bondarenko, I; Grigorchuk, RI; Kravchenko, R; Muntyan, Y; Nekrashevych, V; Savchuk, D; Šunić, Z, On classification of groups generated by 3-state automata over a 2-letter alphabet, Algebra Discrete Math., 1, 1-163, (2008) · Zbl 1164.20004 [8] Bondarenko, IV; Bondarenko, NV; Sidki, SN; Zapata, FR, On the conjugacy problem for finite-state automorphisms of regular rooted trees, Groups Geom. Dyn., 7, 323-355, (2013) · Zbl 1286.20034 [9] Cain, AJ, Automaton semigroups, Theor. Comput. Sci., 410, 5022-5038, (2009) · Zbl 1194.68133 [10] D’Angeli, D., Rodaro, E.: Groups and semigroups defined by colorings of synchronizing automata. Int. J. Algebra Comput., 21 (2014) · Zbl 1314.20028 [11] de la Harpe, P.: Topics in geometric group theory. University of Chicago Press (2000) · Zbl 0965.20025 [12] The GAP Group: GAP - groups, algorithms, and programming, v.4.4.12 (2008) · Zbl 1069.20504 [13] Gillibert, P, The finiteness problem for automaton semigroups is undecidable, Int. J. Algebra Comput., 24, 1-9, (2014) · Zbl 1292.20040 [14] Glasner, Y; Mozes, Sh, Automata and square complexes, Geom. Dedicata, 111, 43-6, (2005) · Zbl 1088.20037 [15] Grigorchuk, R; żuk, A, The lamplighter group as a group generated by a 2-state automaton, and its spectrum, Geom. Dedicata, 87, 209-244, (2001) · Zbl 0990.60049 [16] Grigorchuk, RI, On burnside’s problem on periodic groups, Funktsional. Anal. i Prilozhen., 14, 53-54, (1980) · Zbl 0595.20029 [17] Grigorchuk, RI; Nekrashevich, VV; Sushchanskiı̆, VI, Automata, dynamical systems, and groups, Tr. Mat. Inst. Steklova, 231, 134-214, (2000) [18] Klimann, I., Mairesse, J., Picantin, M.: Implementing computations in automaton (semi)groups. In. Proc. 17th CIAA, volume 7381 of LNCS, pp 240-252 (2012) · Zbl 1297.68145 [19] Klimann, I.: The finiteness of a group generated by a 2-letter invertible-reversible Mealy automaton is decidable. In Proc. 30th STACS, vol. 20 of LIPIcs, pp 502-513 (2013) · Zbl 1354.68159 [20] Maltcev, V, Cayley automaton semigroups, Int. J. Algebra Comput., 19, 79-95, (2009) · Zbl 1188.20068 [21] Mintz, A, On the Cayley semigroup of a finite aperiodic semigroup, Int. J. Algebra Comput., 19, 723-746, (2009) · Zbl 1210.20054 [22] Muntyan, Y., Savchuk, D.: sutomgrp Automata Groups - a GAP package, v.1.1.4.1 (2008) · Zbl 1292.20040 [23] Nekrashevych, V.: Self-similar groups, volume 117 of mathematical surveys and monographs. American mathematical society, providence, RI (2005) · Zbl 1280.20038 [24] Savchuk, DM; Vorobets, Y, Automata generating free products of groups of order 2, J. Algebra, 336, 53-66, (2011) · Zbl 1239.20032 [25] Sidki, SN, Automorphisms of one-rooted trees: growth, circuit structure, and acyclicity, J. Math. Sci. (NewYork), 100, 1925-1943, (2000) · Zbl 1069.20504 [26] Silva, PV; Steinberg, B, On a class of automata groups generalizing lamplighter groups, Int. J. Algebra Comput., 15, 1213-1234, (2005) · Zbl 1106.20028 [27] Steinberg, B; Vorobets, M; Vorobets, Y, Automata over a binary alphabet generating free groups of even rank, Int. J. Algebra Comput., 21, 329-354, (2011) · Zbl 1239.20033 [28] Vorobets, M; Vorobets, Y, On a free group of transformations defined by an automaton, Geom. Dedicata, 124, 237-249, (2007) · Zbl 1183.20024 [29] Vorobets, M; Vorobets, Y, On a series of finite automata defining free transformation groups, Groups Geom Dyn., 4, 377-405, (2010) · Zbl 1227.20027
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.