We investigate the language classes recognized by group automata over matrix groups. For the case of 2 × 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.
Mots-clés : Group automata, time complexity
@article{ITA_2018__52_2-3-4_253_0, author = {Salehi, \"Ozlem and D{\textquoteright}Alessandro, Flavio and Say, A.C. Cem}, editor = {Bordihn, Henning and Nagy, Benedek and Vaszil, Gy\"orgy}, title = {Language classes associated with automata over matrix groups}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {253--268}, publisher = {EDP-Sciences}, volume = {52}, number = {2-3-4}, year = {2018}, doi = {10.1051/ita/2018017}, mrnumber = {3915312}, zbl = {1429.68105}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ita/2018017/} }
TY - JOUR AU - Salehi, Özlem AU - D’Alessandro, Flavio AU - Say, A.C. Cem ED - Bordihn, Henning ED - Nagy, Benedek ED - Vaszil, György TI - Language classes associated with automata over matrix groups JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2018 SP - 253 EP - 268 VL - 52 IS - 2-3-4 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita/2018017/ DO - 10.1051/ita/2018017 LA - en ID - ITA_2018__52_2-3-4_253_0 ER -
%0 Journal Article %A Salehi, Özlem %A D’Alessandro, Flavio %A Say, A.C. Cem %E Bordihn, Henning %E Nagy, Benedek %E Vaszil, György %T Language classes associated with automata over matrix groups %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2018 %P 253-268 %V 52 %N 2-3-4 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita/2018017/ %R 10.1051/ita/2018017 %G en %F ITA_2018__52_2-3-4_253_0
Salehi, Özlem; D’Alessandro, Flavio; Say, A.C. Cem. Language classes associated with automata over matrix groups. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 52 (2018) no. 2-3-4, pp. 253-268. doi : 10.1051/ita/2018017. http://archive.numdam.org/articles/10.1051/ita/2018017/
[1] Subgroups of direct products of free groups. J. Lond. Math. Soc. 2 (1984) 44–52 | DOI | MR | Zbl
and ,[2] C*-algebras and finite-dimensional approximations, In Vol. 88. American Mathematical Society (2008) | MR | Zbl
and ,[3] The word problem distinguishes counter languages. Preprint (2006) | arXiv
, and ,[4] Extended finite automata and word problems. Int. J. Algebra Comput. 15 (2005) 455–466 | DOI | MR | Zbl
,[5] Finite automata over free groups. Int. J. Algebra Comput. 10 (2000) 725–737 | DOI | MR | Zbl
and ,[6] On groups and counter automata. Int. J. Algebra Comput. 18 (2008) 1345–1364 | DOI | MR | Zbl
, and ,[7] On groups whose word problem is solved by a counter automaton. Theoret. Comput. Sci. 320 (2004) 175–185 | DOI | MR | Zbl
and ,[8] Real time counter machines, in Proc. of the 8th Annual Symposium on Switching and Automata Theory (SWAT 1967), FOCS ’67 1967 148–154 | DOI
, and ,[9] A first course in abstract algebra. Addison-Wesley world student series. Addison-Wesley (2003)
and ,[10] Polynomial automaticity and context-free languages. Comput. Complex. 7 (1998) 371–387 | DOI | MR | Zbl
and , :[11] Remarks on blind and partially blind one-way multicounter machines. Theoret. Comput. Sci. 7 (1978) 311–324 | DOI | MR | Zbl
,[12] On growth in group theory, in vol. 1 of Proc. of the International Congress of Mathematicians (1990) 325–338 | MR | Zbl
,[13] Finite automata with multiplication. Theoret. Comput. Sci. 2 (1976) 271–294 | DOI | MR | Zbl
, and ,[14] Formal languages and groups as memory. Commun. Algebra 37 (2009) 193–208 | DOI | MR | Zbl
,[15] Fundamentals of the Theory of Groups. Springer-Verlag (1979) | DOI | MR | Zbl
and ,[16] Topics in geometric group theory. The University of Chicago Press, Chicago (2000) | MR | Zbl
,[17]
and , (1977)[18] The accepting power of finite automata over groups, in New Trends in Formal Languages. Springer-Verlag (1997) 39–48 | DOI | MR
and ,[19] Rational monoid and semigroup automata. Ph.D. thesis, University of Manchester (2010)
,[20] A Turing machine time hierarchy. Theoret. Comput. Sci. 26 (1983) 327–333 | DOI | MR | Zbl
,[21] Silent transitions in automata with storage, in International Colloquium on Automata, Languages, and Programming. Springer, Berlin, Heidelberg (2013) 434–445 | MR | Zbl
,Cité par Sources :