Inverse monoids: decidability and complexity of algebraic questions.

DOI10.1016/J.IC.2007.01.002MaRDI QIDQ2643082zbMATH OpenOpenAlexFDO

Authors Markus Lohrey, Nicole Ondrusch

Publication date 23 August 2007

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-22557

zbMATH Keywords

Cayley graphsword problemalgorithmic complexityinverse monoidsfirst-order theories

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Decidability of theories and sets of sentences (03B25) Free semigroups, generators and relations, word problems (20M05) Inverse semigroups (20M18)

Recommendations

• Mathematical Foundations of Computer Science 2005
• The word problem of inverse monoids presented by one idempotent relator
• Partially commutative inverse monoids.
• Algorithmic properties of inverse monoids with hyperbolic and tree-like Schützenberger graphs
• Presentations of inverse monoids

Cites work

• scientific article; zbMATH DE number 1670767 (Why is no real title available?)
• scientific article; zbMATH DE number 1722707 (Why is no real title available?)
• scientific article; zbMATH DE number 988810 (Why is no real title available?)
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 3869616 (Why is no real title available?)
• scientific article; zbMATH DE number 53151 (Why is no real title available?)
• scientific article; zbMATH DE number 3510287 (Why is no real title available?)
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• scientific article; zbMATH DE number 1335884 (Why is no real title available?)
• scientific article; zbMATH DE number 1346498 (Why is no real title available?)
• scientific article; zbMATH DE number 1088188 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• scientific article; zbMATH DE number 3047078 (Why is no real title available?)
• A Geometric Characterization of Automatic Monoids
• A uniform method for proving lower bounds on the computational complexity of logical theories
• Alternation
• Commutativity in free inverse monoids
• Confluent and Other Types of Thue Systems
• DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS
• Decidability of DPDA equivalence
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Diophantine theories of free inverse semigroups
• EQUATIONS IN FREE INVERSE MONOIDS
• Extensions and submonoids of automatic monoids.
• Free Inverse Semigroups
• Groups and graphs: Groups acting on trees, ends, and cancellation diagrams
• Groups, the theory of ends, and context-free languages
• Inverse Monoids, Trees, and Context-Free Languages
• LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE
• Logical aspects of Cayley-graphs: the group case
• Mathematical Foundations of Computer Science 2005
• On free inverse monoid languages
• On the algorithmic insolvability of the word problem in group theory
• Partially Commutative Inverse Monoids
• Presentations of inverse monoids
• Pushdown processes: Games and model-checking
• RATIONAL LANGUAGES AND INVERSE MONOID PRESENTATIONS
• Recursive unsolvability of a problem of Thue
• Subgroups of small Cancellation Groups
• The Kleene Equality for Graphs
• The Word Problem in the Variety of Inverse Semigroups with Abélian Covers
• The loop problem for monoids and semigroups
• The second-order monadic theory of the free inverse monoid is undecidable
• The theory of ends, pushdown automata, and second-order logic
• The word problem
• The word problem of inverse monoids presented by one idempotent relator
• Word Problems Solvable in Logspace

Cited in

(16)

• The word problem for free adequate semigroups.
• The word problem for nilpotent inverse monoids
• INEVITABLE GRAPHS AND PROFINITE TOPOLOGIES: SOME SOLUTIONS TO ALGORITHMIC PROBLEMS IN MONOID AND AUTOMATA THEORY, STEMMING FROM GROUP THEORY
• ALGORITHMIC PROBLEMS ON INVERSE MONOIDS OVER VIRTUALLY FREE GROUPS
• Finite idempotent inverse monoid presentations.
• On the complexity of inverse semigroup conjugacy
• Inverse Monoids, Trees, and Context-Free Languages
• Partially commutative inverse monoids.
• Algorithmic properties of inverse monoids with hyperbolic and tree-like Schützenberger graphs
• The Thompson-Higman monoids \(M_{k,i}\): the \(\mathcal J\)-order, the \(\mathcal D\)-relation, and their complexity.
• COMBINATORIAL GROUP THEORY, INVERSE MONOIDS, AUTOMATA, AND GLOBAL SEMIGROUP THEORY
• On labeled birooted tree languages: algebras, automata and logic
• Decision problems for inverse monoids presented by a single sparse relator.
• On groups that have normal forms computable in logspace.
• Compressed word problems for inverse monoids
• Mathematical Foundations of Computer Science 2005

This page was built for publication: Inverse monoids: decidability and complexity of algebraic questions.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2643082)