Automatic semigroups

DOI10.1016/S0304-3975(99)00151-6zbMath0987.20033MaRDI QIDQ1589444

Richard M. Thomas, Colin M. Campbell, Edmund F. Robertson, Nikola Ruškuc

Publication date: 12 December 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

free semigroups; word problem; finitely generated semigroups; automatic semigroups

Mathematics Subject Classification ID

68Q45: Formal languages and automata

20M05: Free semigroups, generators and relations, word problems

20M35: Semigroups in automata theory, linguistics, etc.

Related Items

AUTOMATIC SEMIGROUPS WITH SUBSEMIGROUPS OF FINITE REES INDEX, The loop problem for monoids and semigroups, DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS, Subsemigroups of groups: presentations, Malcev presentations, and automatic structures, LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE, Finiteness and Dehn functions of automatic monoids having directed fellow traveller property., A geometric characterization of automatic semigroups, FA-presentable groups and rings, Automaton semigroups, Undecidable properties of monoids with word problem solvable in linear time. II: Cross sections and homological and homotopical finiteness conditions., Extensions and submonoids of automatic monoids., Automatic semigroups and categories., Automatic structures for semigroup constructions., Automatic subsemigroups of free products., Finite transducers for divisibility monoids, Uniform decision problems for automatic semigroups., On graph products of automatic monoids, Automatic Presentations for Cancellative Semigroups, Properties of the subsemigroups of the bicyclic monoid, MONOIDS PRESENTED BY REWRITING SYSTEMS AND AUTOMATIC STRUCTURES FOR THEIR SUBMONOIDS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Small cancellation theory and automatic groups
• Small cancellation theory and automatic groups. II
• Easy multiplications. II: Extensions of rational semigroups
• Easy multiplications. I: The realm of Kleene's theorem
• Automatic groups and amalgams
• The use of Knuth-Bendix methods to solve the word problem in automatic groups
• Syntactic and Rees indices of subsemigroups
• Automatic completely-simple semigroups
• Reidemeister-Schreier type rewriting for semigroups
• Strongly geodesically automatic groups are hyperbolic
• DETERMINING IDEALS OF A GIVEN FINITE INDEX IN A FINITELY PRESENTED SEMIGROUP
• Generators and relations of direct products of semigroups
• Structure Results for Transitive, Untwisted, Superlinked Finite Covers
• A NOTE ON CONTEXT-SENSITIVE LANGUAGES AND WORD PROBLEMS
• Automatic monoids and change of generators