DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS
From MaRDI portal
Decidability of theories and sets of sentences (03B25) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Hyperbolic groups and nonpositively curved groups (20F67) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Recommendations
Cites work
- A combinatorial property and Cayley graphs of semigroups
- A uniform method for proving lower bounds on the computational complexity of logical theories
- Automatic semigroups
- Canonical representatives and equations in hyperbolic groups
- Confluent and Other Types of Thue Systems
- Extensions and submonoids of automatic monoids.
- Finite complete rewriting systems and the complexity of word problem
- Finite presentations of infinite structures: Automata and interpretations
- Groups and graphs: Groups acting on trees, ends, and cancellation diagrams
- Groups, the theory of ends, and context-free languages
- Géométrie et théorie des groupes. Les groupes hyperboliques de Gromov. (Geometry and group theory. The hyperbolic groups of Gromov)
- scientific article; zbMATH DE number 53661 (Why is no real title available?)
- Logical aspects of Cayley-graphs: the group case
- McNaughton families of languages.
- Membership for growing context-sensitive grammars is polynomial
- Notions of automaticity in semigroups.
- On the Tape Complexity of Deterministic Context-Free Languages
- Properties that characterize LOGCFL
- Recursive unsolvability of a problem of Thue
- The theory of ends, pushdown automata, and second-order logic
- Tree-size bounded alternation
- Word hyperbolic semigroups
- WORD-HYPERBOLIC GROUPS HAVE REAL-TIME WORD PROBLEM
Cited in
(33)- Cayley graphs as classifiers for data mining: the influence of asymmetries
- 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}\)
- Incidence monoids: automorphisms and complexity
- Compression techniques in group theory
- Some decidability and undecidability results on Green's relations for automatic monoids.
- Uniform decision problems for automatic semigroups.
- Inverse monoids: decidability and complexity of algebraic questions.
- Cayley graph automatic groups are not necessarily Cayley graph biautomatic
- scientific article; zbMATH DE number 999598 (Why is no real title available?)
- scientific article; zbMATH DE number 4216027 (Why is no real title available?)
- Automatic Decidability and Combinability Revisited
- scientific article; zbMATH DE number 3917720 (Why is no real title available?)
- scientific article; zbMATH DE number 1944128 (Why is no real title available?)
- scientific article; zbMATH DE number 1962836 (Why is no real title available?)
- THE COMPLEXITY OF DECIDING CODE AND MONOID PROPERTIES FOR REGULAR SETS
- Finite Gröbner-Shirshov bases for plactic algebras and biautomatic structures for plactic monoids.
- The Cayley-graph of the queue monoid: logic and decidability
- The power word problem
- scientific article; zbMATH DE number 223548 (Why is no real title available?)
- Notions of Hyperbolicity in Monoids
- LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE
- Developments in Language Theory
- Complexity of word problems for HNN-extensions
- Knapsack in hyperbolic groups
- Logspace computations in graph products
- Complexity of word problems for HNN-extensions
- Parallel algorithms for power circuits and the word problem of the Baumslag group
- Improved parallel algorithms for generalized Baumslag groups
- The power word problem in graph products
- Logical aspects of Cayley-graphs: the group case
- Streaming in graph products
- Streaming word problems
- The automata that define representations of monomial algebras.
This page was built for publication: DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5462671)
