| Issue |
RAIRO-Theor. Inf. Appl.
Volume 52, Number 2-3-4, April–December 2018
8th Workshop on Non-classical Models of Automata and Applications (NCMA 2016)
|
|
|---|---|---|
| Page(s) | 253 - 268 | |
| DOI | https://doi.org/10.1051/ita/2018017 | |
| Published online | 24 January 2019 | |
Regular Article
Language classes associated with automata over matrix groups★,★★,★★★
1
Department of Computer Engineering, Boğaziçi University,
Bebek 34342,
İstanbul, Turkey.
2
Department of Mathematics, Boğaziçi University,
Bebek 34342,
İstanbul, Turkey.
3
Dipartimento di Matematica,
Università di Roma “La Sapienza”,
Piazzale Aldo Moro 2,
00185 Roma, Italy.
* Corresponding author: ozlem.salehi@boun.edu.tr
Received:
21
November
2018
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.
Mathematics Subject Classification: 68Q45 / 68Q05
Key words: Group automata / time complexity
This work was supported by Boğaziçi University Research Fund under grant number 11760. A preliminary version of this work was presented at the 8th Workshop on Non-Classical Models of Automata and Applications (NCMA), Debrecen, Hungary, August 29–30, 2016.
© EDP Sciences, 2019
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.