Geodesic
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

Voir la notice de l'article provenant de la source Numdam

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.

DOI : 10.1051/ita/2018017
Classification : 68Q45, 68Q05
Keywords: Group automata, time complexity

Salehi, Özlem 1 ; D’Alessandro, Flavio 1 ; Say, A.C. Cem 1

1 
@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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :