zbMATH — the first resource for mathematics

On the group memory complexity of extended finite automata over groups. (English) Zbl 1462.68099
Summary: We define and investigate a complexity measure defined for extended finite automata over groups (EFA). Roughly, an EFA is a finite automaton augmented with a register storing an element of a group, initially the identity element. When a transition is performed, not only the state, but the register contents are updated. A word is accepted if, after reading completely the word, the automaton reached a final state, and the register returned to the identity element. The group memory complexity of an EFA over a group is a function from \(\mathbb{N}\) to \(\mathbb{N}\) which associates with each \(n\) the value 0, if there is no word of length \(n\) accepted by the automaton, or the minimal integer \(c\) such that for every word \(x\) of length \(n\) accepted by the automaton, there is a computation on \(x\) such that the number of transitions labeled by non-neutral element of the group used in that computation is at most \(c\). We prove that a language is regular if and only if it is accepted by an EFA with a finite group memory complexity. In particular, any EFA over a group such that all its finitely generated subgroups are finite accepts a regular language. We then provide examples of EFA over some groups that accept non-regular languages and have a sublinear group memory complexity, namely a function in \(\mathcal{O}(\sqrt{n})\) or \(\mathcal{O}(\log n)\). There are non-regular languages such that any EFA over some group that accepts that language has a group memory complexity in \(\Omega(n)\).
68Q45 Formal languages and automata
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
PDF BibTeX Cite
Full Text: DOI
[1] Dassow, J.; Mitrana, V., Finite automata over free groups, J. Algebra Comput., 10, 725-737 (2000) · Zbl 0969.68093
[2] Ibarra, O. H.; Sahni, S. K.; Kim, C. E., Finite automata with multiplication, Theor. Comput. Sci., 2, 271-294 (1976) · Zbl 0345.68029
[3] Greibach, S., Remarks on blind and partially blind one-way multicounter machines, Theor. Comput. Sci., 7, 311-324 (1978) · Zbl 0389.68030
[4] Păun, G., A new generative device: valence grammars, Rev. Roum. Math. Pures Appl., 25, 911-924 (1980) · Zbl 0463.68073
[5] Mitrana, V., Valence grammars on a free generated group, Bull. Eur. Assoc. Theor. Comput. Sci., 47, 174-179 (1992) · Zbl 0757.68073
[6] Gheorghe, M., Linear valence grammars, (Proc. Internat. Meeting of Young Computer Scientists (1986)), 281-285
[7] Fernau, H.; Stiebe, R., Valuated and valence grammars, (Developments in Language Theory. Developments in Language Theory, LNCS, vol. 2295 (2001), Springer Verlag), 281-292 · Zbl 1073.68658
[8] Fernau, H.; Stiebe, R., Valence grammars with target sets, (Words Semigroups and Transductions (2001), World Scientific: World Scientific Singapore), 129-140
[9] Fernau, H.; Stiebe, R., Regulation by valences, (Mathematical Foundations of Computer Science. Mathematical Foundations of Computer Science, LNCS, vol. 1295 (1997), Springer Verlag), 239-248 · Zbl 0946.68066
[10] Fernau, H.; Stiebe, R., Valences in Lindenmayer systems, Fundam. Inform., 45, 329-358 (2001) · Zbl 0974.68081
[11] Zetzsche, G., Silent transitions in automata with storage, (Automata, Languages, and Programming. Automata, Languages, and Programming, LNCS, vol. 7966 (2013), Springer Verlag), 434-445 · Zbl 1334.68125
[12] Zetzsche, G., On the Capabilities of Grammars, Automata, and Transducers Controlled by Monoids, Automata, Languages, and Programming, LNCS, vol. 6756, 222-233 (2011), Springer Verlag · Zbl 1333.68189
[13] Zetzsche, G., The emptiness problem for valence automata over graph monoids, Inf. Comput. (2020), in press
[14] Gilman, R. H.; Shapiro, M., On groups whose word problem is solved by a nested stack automaton (1998)
[15] Elston, G. Z.; Ostheimer, G., On groups whose word problem is solved by a counter automaton, Theor. Comput. Sci., 320, 175-185 (2004) · Zbl 1061.20029
[16] Kambites, M., Word problems recognisable by deterministic blind monoid automata, Theor. Comput. Sci., 362, 232-237 (2006) · Zbl 1100.68051
[17] Bordihn, H.; Mitrana, V., On the degrees of non-regularity and non-context-freeness, J. Comput. Syst. Sci., 108, 104-117 (2020) · Zbl 1447.68006
[18] Rozenberg, G.; Salomaa, A., Handbook of Formal Languages (1997), Springer-Verlag: Springer-Verlag Berlin · Zbl 0866.68057
[19] Lyndon, R. C.; Schupp, P. E., Combinatorial Group Theory (1977), Springer-Verlag: Springer-Verlag Berlin · Zbl 0368.20023
[20] Rotman, J. J., An Introduction to the Theory of Groups (1995), Springer-Verlag: Springer-Verlag Berlin · Zbl 0810.20001
[21] Mitrana, V.; Stiebe, R., Extended finite automata over groups, Discrete Appl. Math., 108, 287-300 (2001) · Zbl 0971.68093
[22] Corson, J. M., Extended finite automata and word problems, J. Algebra Comput., 15, 455-466 (2005) · Zbl 1098.68067
[23] Chomsky, N.; Schützenberger, M. P., The algebraic theory of context-free languages, (Computer Programming and Formal Systems (1963), North-Holland: North-Holland Amsterdam), 118-161 · Zbl 0148.00804
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.