Language classes associated with automata over matrix groups. (English) Zbl 1429.68105
Summary: We investigate the language classes recognized by group automata over matrix groups. For the case of \(2 \times 2\) matrices, we prove that the corresponding group automata for rational matrix groups are more powerful than the corresponding group automata for integer matrix groups. Finite automata over some special matrix groups, such as the discrete Heisenberg group and the Baumslag-Solitar group are also examined. We also introduce the notion of time complexity for group automata and demonstrate some separations among related classes. The case of linear-time bounds is examined in detail throughout our repertory of matrix group automata.
MSC:
| 68Q45 | Formal languages and automata |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q70 | Algebraic theory of languages and automata |
References:
| [1] | G. Baumslag and J.E. Roseblade, Subgroups of direct products of free groups. J. Lond. Math. Soc. 2 (1984) 44-52 · Zbl 0559.20018 · doi:10.1112/jlms/s2-30.1.44 |
| [2] | N.P. Brown and N. Ozawa, C*-algebras and finite-dimensional approximations, In Vol. 88. American Mathematical Society (2008) · Zbl 1160.46001 |
| [3] | S. Cleary, M. Elder and G. Ostheimer, The word problem distinguishes counter languages. Preprint (2006) |
| [4] | J.M. Corson, Extended finite automata and word problems. Int. J. Algebra Comput.15 (2005) 455-466 · Zbl 1098.68067 |
| [5] | J. Dassow and V. Mitrana, Finite automata over free groups. Int. J. Algebra Comput. 10 (2000) 725-737 · Zbl 0969.68093 |
| [6] | M. Elder, M. Kambites and G. Ostheimer, On groups and counter automata. Int. J. Algebra Comput. 18 (2008) 1345-1364 · Zbl 1171.20021 |
| [7] | G.Z. Elston and G. Ostheimer, On groups whose word problem is solved by a counter automaton. Theoret. Comput. Sci. 320 (2004) 175-185 · Zbl 1061.20029 · doi:10.1016/j.tcs.2003.09.007 |
| [8] | P.C. Fischer, A.R. Meyer and A.L. Rosenberg, Real time counter machines, in Proc. of the 8th Annual Symposium on Switching and Automata Theory (SWAT 1967), FOCS ’67 1967 148-154 · doi:10.1109/FOCS.1967.29 |
| [9] | J.B. Fraleigh and V.J. Katz, A first course in abstract algebra. Addison-Wesley world student series. Addison-Wesley (2003) |
| [10] | I. Glaister and J. Shallit, Automaticity III: Polynomial automaticity and context-free languages. Comput. Complex. 7 (1998) 371-387 · Zbl 0973.11031 · doi:10.1007/s000370050016 |
| [11] | S.A. Greibach, Remarks on blind and partially blind one-way multicounter machines. Theoret. Comput. Sci. 7 (1978) 311-324 · Zbl 0389.68030 · doi:10.1016/0304-3975(78)90020-8 |
| [12] | R.I Grigorchuk, On growth in group theory, in vol. 1 of Proc. of the International Congress of Mathematicians (1990) 325-338 · Zbl 0749.20016 |
| [13] | O.H. Ibarra, S.K. Sahni and C.E. Kim, Finite automata with multiplication. Theoret. Comput. Sci. 2 (1976) 271-294 · Zbl 0345.68029 · doi:10.1016/0304-3975(76)90081-5 |
| [14] | M. Kambites, Formal languages and groups as memory. Commun. Algebra37 (2009) 193-208 · Zbl 1163.68029 |
| [15] | M.I. Kargapolov and J.I. Merzljakov, Fundamentals of the Theory of Groups. Springer-Verlag (1979) · Zbl 0549.20001 · doi:10.1007/978-1-4612-9964-6 |
| [16] | P. De La Harpe, Topics in geometric group theory. The University of Chicago Press, Chicago (2000) · Zbl 0965.20025 |
| [17] | R.C. Lyndon and P.E. Schupp, Combinatorial . Springer-Verlag (1977) · Zbl 0368.20023 |
| [18] | V. Mitrana and R. Stiebe, The accepting power of finite automata over groups, in New Trends in Formal Languages. Springer-Verlag (1997) 39-48 · doi:10.1007/3-540-62844-4_4 |
| [19] | E. Render, Rational monoid and semigroup automata. Ph.D. thesis, University of Manchester (2010) · Zbl 1187.68299 |
| [20] | S. Żak, A Turing machine time hierarchy. Theoret. Comput. Sci. 26 (1983) 327-333 · Zbl 0525.68026 · doi:10.1016/0304-3975(83)90015-4 |
| [21] | G. Zetzsche, Silent transitions in automata with storage, in International Colloquium on Automata, Languages, and Programming. Springer, Berlin, Heidelberg (2013) 434-445 · Zbl 1334.68125 |
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.
