Decidability and complexity in automatic monoids.

DOI10.1007/978-3-540-30550-7_26MaRDI QIDQ5711964zbMATH OpenOpenAlexDBLPFDO

Authors Markus Lohrey

Publication date 22 December 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b103739

zbMATH Keywords

automatic monoidsCayley graphsfirst-order theorieshyperbolic groupsword problem

Mathematics Subject Classification ID

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

• DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS
• Logical aspects of Cayley-graphs: the group case
• Decidable theories of Cayley-graphs
• From automatic structures to automatic groups.
• Mathematical Foundations of Computer Science 2005

Cited in

(16)

• Incidence monoids: automorphisms and complexity
• Some decidability and undecidability results on Green's relations for automatic monoids.
• 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?)
• Decidable theories of Cayley-graphs
• A Geometric Characterization of Automatic Monoids
• THE COMPLEXITY OF DECIDING CODE AND MONOID PROPERTIES FOR REGULAR SETS
• Word problems for 2-homogeneous monoids and symmetric logspace
• The Cayley-graph of the queue monoid: logic and decidability
• scientific article; zbMATH DE number 223548 (Why is no real title available?)
• Notions of Hyperbolicity in Monoids
• DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS
• Logical aspects of Cayley-graphs: the group case

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 Q5711964)