On the group memory complexity of extended finite automata over groups

Abstract 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 is 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 N to 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 O ( n ) or 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 Ω ( n ) .