Automatic quotients of free groups.

DOI10.1016/J.JPAA.2005.02.004MaRDI QIDQ2570182zbMATH OpenOpenAlexFDO

Authors Robert H. Gilman

Publication date 26 October 2005

Published in Journal of Pure and Applied Algebra (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0305065

zbMATH Keywords

automatic groupscontext-free languageslinear languagesprefix-closed automatic structures with uniquenessregular languages

Mathematics Subject Classification ID

Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Geometric group theory (20F65) Formal languages and automata (68Q45)

Abstract: Automatic groups admitting prefix closed automatic structures with uniqueness are characterized as the quotients of free groups by normal subgroups possessing sets of free generators satisfying certain language-theoretic conditions.

Review text

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.

Recommendations

• scientific article; zbMATH DE number 1944116
• scientific article; zbMATH DE number 665465
• The use of Knuth-Bendix methods to solve the word problem in automatic groups
• A NOTE ON THE GRAMMAR OF COMBINGS
• scientific article; zbMATH DE number 2101006
• Automata groups.
• Automatic Groups Associated with Word Orders Other than Shortlex
• Groups defined by automata
• Groups generated by automata.
• Groups and automata: a perfect match

Cites work

• DETERMINISTIC AND NON-DETERMINISTIC ASYNCHRONOUS AUTOMATIC STRUCTURES
• Discrete groups. Transl. from the Japanese by Ken'ichi Ohshika
• Geometric group theory
• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• scientific article; zbMATH DE number 1944116 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 2221698 (Why is no real title available?)
• Synchronized rational relations of finite and infinite words

Cited in

(7)

• Homophonic quotients of linguistic free groups: German, Korean, and Turkish
• Automatic subsemigroups of free products.
• TWO AUTOMATIC SPANNING TREES IN SMALL CANCELLATION GROUP PRESENTATIONS
• Algorithms and topology of Cayley graphs for groups.
• Quotients Homophones des Groupes Libres Homophonic Quotients of Free Groups
• Finite quotients of the automorphism group of a free group
• AUTOMORPHISM GROUPS OF QUANDLES

This page was built for publication: Automatic quotients of free groups.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2570182)