Automatic quotients of free groups. (Q2570182)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Automatic quotients of free groups. |
scientific article |
Statements
Automatic quotients of free groups. (English)
0 references
26 October 2005
0 references
An automatic group is a group where group multiplication can be carried out by finite automata. (See, for example, [\textit{D. B. A. Epstein}, et al., Word processing in groups. Boston, MA: Jones and Bartlett (1992; Zbl 0764.20017)].) The basic problems about automatic groups are these: Which groups are automatic? In a given automatic group, how simply may the automatic structure be described? Relative to the second question, the author addresses this open question: Does every (synchronously) automatic group admit a prefix-closed automatic structure with uniqueness? U\-nique\-ness requires that the automaton describing group elements produces a unique representative for each group element. The structure is prefix-closed if each prefix of a representative is also a representative of a group element. Though the author does not answer the question, he does give two interesting characterizations of those groups which admit prefix-closed automatic structures with uniqueness. Both require, among other things, that \(G\) be a quotient of a finitely generated free group by a normal subgroup admitting a special kind of language called `linear'. The linear languages lie between the classes called regular and context-free.
0 references
automatic groups
0 references
regular languages
0 references
linear languages
0 references
context-free languages
0 references
prefix-closed automatic structures with uniqueness
0 references