ALGORITHMIC PROBLEMS ON INVERSE MONOIDS OVER VIRTUALLY FREE GROUPS
DOI10.1142/S0218196708004366zbMath1190.20045OpenAlexW2032938926MaRDI QIDQ3502752
Markus Lohrey, Volker Diekert, Nicole Ondrusch
Publication date: 20 May 2008
Published in: International Journal of Algebra and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0218196708004366
Cayley graphsword probleminverse monoidsdecidabilitymembership problemfirst-order theoriesrational subsetsfinite presentationsBirget-Rhodes expansions
Free semigroups, generators and relations, word problems (20M05) Decidability of theories and sets of sentences (03B25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Word problems, etc. in computability and recursion theory (03D40) Inverse semigroups (20M18)
Related Items
Cites Work
- Logical aspects of Cayley-graphs: the group case
- Groups, the theory of ends, and context-free languages
- Almost finite expansions of arbitrary semigroups
- Diophantine theories of free inverse semigroups
- The theory of ends, pushdown automata, and second-order logic
- Group theory via global semigroup theory
- E-unitary inverse monoids and the Cayley graph of a group presentation
- A note on Birget-Rhodes expansion of groups
- Commutativity in free inverse monoids
- The word problem of inverse monoids presented by one idempotent relator
- On the rational subsets of the free group
- Inverse monoids: decidability and complexity of algebraic questions.
- On free inverse monoid languages
- Subgroups of small Cancellation Groups
- RATIONAL LANGUAGES AND INVERSE MONOID PRESENTATIONS
- A RESIDUALLY FINITE VERSION OF RIPS'S CONSTRUCTION
- PARTIAL ACTIONS OF GROUPS
- Term Rewriting and All That
- The Word Problem in the Variety of Inverse Semigroups with Abélian Covers
- EQUATIONS IN FREE INVERSE MONOIDS
