DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS

DOI10.1142/S0129054105003248zbMATH Open1146.20314MaRDI QIDQ5462671FDOQ5462671

Markus Lohrey

Publication date: 3 August 2005

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

Cayley graphsword problemhyperbolic groupsfirst-order theoriesautomatic monoids

Mathematics Subject Classification ID

Hyperbolic groups and nonpositively curved groups (20F67) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Decidability of theories and sets of sentences (03B25) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)

Cites Work

• Title not available (Why is that?)
• Géométrie et théorie des groupes. Les groupes hyperboliques de Gromov. (Geometry and group theory. The hyperbolic groups of Gromov)
• Recursive Unsolvability of a problem of Thue
• Notions of automaticity in semigroups.
• Automatic semigroups
• Word hyperbolic semigroups
• Canonical representatives and equations in hyperbolic groups
• Logical aspects of Cayley-graphs: the group case
• The theory of ends, pushdown automata, and second-order logic
• A combinatorial property and Cayley graphs of semigroups
• Groups, the theory of ends, and context-free languages
• A uniform method for proving lower bounds on the computational complexity of logical theories
• Membership for growing context-sensitive grammars is polynomial
• Groups and graphs: Groups acting on trees, ends, and cancellation diagrams
• Properties that characterize LOGCFL
• On the Tape Complexity of Deterministic Context-Free Languages
• Tree-size bounded alternation
• Confluent and Other Types of Thue Systems
• McNaughton families of languages.
• Finite presentations of infinite structures: Automata and interpretations
• WORD-HYPERBOLIC GROUPS HAVE REAL-TIME WORD PROBLEM
• Finite complete rewriting systems and the complexity of word problem
• Extensions and submonoids of automatic monoids.

Cited In (23)

• Incidence monoids: automorphisms and complexity
• THE COMPLEXITY OF DECIDING CODE AND MONOID PROPERTIES FOR REGULAR SETS
• Improved parallel algorithms for generalized Baumslag groups
• Title not available (Why is that?)
• Parallel algorithms for power circuits and the word problem of the Baumslag group
• Cayley graphs as classifiers for data mining: the influence of asymmetries
• LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE
• Inverse monoids: decidability and complexity of algebraic questions.
• The power word problem in graph products
• Title not available (Why is that?)
• Knapsack in hyperbolic groups
• Complexity of word problems for HNN-extensions
• Complexity of word problems for HNN-extensions
• Compression techniques in group theory
• Title not available (Why is that?)
• Logspace computations in graph products
• Title not available (Why is that?)
• Title not available (Why is that?)
• The automata that define representations of monomial algebras.
• Finite Gröbner-Shirshov bases for plactic algebras and biautomatic structures for plactic monoids.
• 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}\)
• Uniform decision problems for automatic semigroups.
• Automatic Decidability and Combinability Revisited

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)