Automatic semigroups
From MaRDI portal
Publication:1589444
DOI10.1016/S0304-3975(99)00151-6zbMath0987.20033OpenAlexW2915052804MaRDI QIDQ1589444
Richard M. Thomas, Nikola Ruškuc, Colin M. Campbell, Edmund F. Robertson
Publication date: 12 December 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(99)00151-6
Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)
Related Items (52)
AUTOMATIC SEMIGROUPS WITH SUBSEMIGROUPS OF FINITE REES INDEX ⋮ An automatic semigroup of languages ⋮ Automaticity of one-relator semigroups with length less than or equal to three ⋮ Automatic semigroups and categories. ⋮ Crystal monoids \& crystal bases: rewriting systems and biautomatic structures for plactic monoids of types \(A_{n}\), \(B_{n}\), \(C_{n}\), \(D_{n}\), and \(G_{2}\) ⋮ Decision problems for word-hyperbolic semigroups ⋮ Notions of hyperbolicity in monoids. ⋮ A geometric characterization of automatic semigroups ⋮ Markov semigroups, monoids and groups ⋮ Automatic structure for generalized Bruck-Reilly ∗-extension of a monoid ⋮ Quasi-automatic semigroups ⋮ Two applications of monoid actions to cross-sections ⋮ Undecidable properties of monoids with word problem solvable in linear time. II: Cross sections and homological and homotopical finiteness conditions. ⋮ Green index in semigroups: generators, presentations, and automatic structures. ⋮ Automatic semigroups and Bruck-Reilly extensions. ⋮ The monoid of queue actions ⋮ The rotating normal form of braids is regular ⋮ A note on automatic semigroups. ⋮ Automatic presentations and semigroup constructions ⋮ A language hierarchy of binary relations ⋮ Automatic structures for subsemigroups of Baumslag-Solitar semigroups. ⋮ Automatic Presentations for Cancellative Semigroups ⋮ The monoids of the patience sorting algorithm ⋮ Finite Gröbner-Shirshov bases for plactic algebras and biautomatic structures for plactic monoids. ⋮ CONTEXT-FREE REWRITING SYSTEMS AND WORD-HYPERBOLIC STRUCTURES WITH UNIQUENESS ⋮ FA-presentable groups and rings ⋮ Quasi-automatic semigroups ⋮ Automatic structures for semigroup constructions. ⋮ Automatic subsemigroups of free products. ⋮ ON CERTAIN PAIRS OF NON-ENGEL ELEMENTS IN FINITE GROUPS ⋮ The loop problem for monoids and semigroups ⋮ On finite complete rewriting systems, finite derivation type, and automaticity for homogeneous monoids ⋮ ON THE STRUCTURE OF FINITELY GENERATED SEMIGROUPS OF UNARY REGULAR LANGUAGES ⋮ Unnamed Item ⋮ Finite transducers for divisibility monoids ⋮ Uniform decision problems for automatic semigroups. ⋮ Finiteness and Dehn functions of automatic monoids having directed fellow traveller property. ⋮ DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS ⋮ Properties of the subsemigroups of the bicyclic monoid ⋮ A strong geometric hyperbolicity property for directed graphs and monoids. ⋮ Subsemigroups of groups: presentations, Malcev presentations, and automatic structures ⋮ MONOIDS PRESENTED BY REWRITING SYSTEMS AND AUTOMATIC STRUCTURES FOR THEIR SUBMONOIDS ⋮ Where Automatic Structures Benefit from Weighted Automata ⋮ LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE ⋮ Automaton semigroups ⋮ Automatic presentations for semigroups. ⋮ Quasi-automatic groups are asynchronously automatic ⋮ Rewriting systems and biautomatic structures for Chinese, hypoplactic, and sylvester monoids ⋮ On the automaticity of singular Artin monoids of finite type ⋮ Extensions and submonoids of automatic monoids. ⋮ Automatic semigroup acts. ⋮ On graph products of automatic monoids
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Automatic semigroups
