Inverse monoids: decidability and complexity of algebraic questions.

DOI10.1016/J.IC.2007.01.002zbMATH Open1139.20054OpenAlexW2111380805MaRDI QIDQ2643082FDOQ2643082

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

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

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)

Cites Work

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

Cited In (16)

• 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
• On the complexity of inverse semigroup conjugacy
• Finite idempotent inverse monoid presentations.
• 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
• Decision problems for inverse monoids presented by a single sparse relator.
• On labeled birooted tree languages: algebras, automata and logic
• On groups that have normal forms computable in logspace.
• Mathematical Foundations of Computer Science 2005
• Compressed word problems for inverse monoids
• The word problem for free adequate semigroups.

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)