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

algorithmic complexityCayley graphsfirst-order theoriesinverse monoidsword problem

Mathematics Subject Classification ID

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

Review text

The authors show that the word problem can be solved in linear time on a RAM and in logarithmic space for the class of inverse monoids generated by a set \(\Gamma\) subject to relations of the form \(e=f\), where \(e\) and \(f\) are idempotents in the free inverse monoid generated by \(\Gamma\). Also, it is shown that the first-order theory with regular path predicates is decidable for the Cayley-graphs of these monoids.

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

• 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
• 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?)
• Inverse Monoids, Trees, and Context-Free Languages
• Logical aspects of Cayley-graphs: the group case
• LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID 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 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 in the Variety of Inverse Semigroups with Abélian Covers
• The word problem of inverse monoids presented by one idempotent relator
• Word Problems Solvable in Logspace

Cited in

(17)

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

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)