Partially commutative inverse monoids.
type: Item
instance of: scholarly article
title: Partially commutative inverse monoids.
zbMATH Open document ID: 1156.20049
author: Volker Diekert
author: Markus Lohrey
author: Alexander Miller
published in: Semigroup Forum
publication date: 2008-12-02T00:00:00Z
review text: The paper studies complexity problems of free partially commutative inverse monoids. The word problem was shown to be decidable for these monoids in the thesis of Veloso da Costa. The present authors show that the complexity of the word problem is in \(O(n\log(n))\) on a random access machine. To obtain this bound the paper gives a new construction of free partially commutative inverse monoids by considering closed subsets for a closure operation on subsets of graph groups (or free partially commutative groups, or right-angled Artin groups). The submonoid membership problem asks whether an element of the monoid is in a given f.g.~submonoid. This problem is shown to be NP-hard for 2-generator free inverse monoid. In the latter part of the paper the authors study free partially commutative inverse monoids modulo finite idempotent presentations (a set of relations involving only idempotent elements). It is shown that the resulting quotient monoid has decidable word problem if and only if the dependence relation, associated to the partial commutation relation, is transitive. Finally, complexity bounds are considered in the transitive case.
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 20M18
Mathematics Subject Classification ID: 20M35
zbMATH DE Number: 5377128
zbMATH Keywords: inverse monoids
zbMATH Keywords: free partially commutative monoids
zbMATH Keywords: word problem
zbMATH Keywords: rational sets
zbMATH Keywords: membership problem
zbMATH Keywords: idempotent presentations
zbMATH Keywords: algorithms
zbMATH Keywords: finite presentations
reviewed by: Tero Harju
MaRDI profile type: Publication
full work available at URL: s00233-008-9060-x
OpenAlex ID: W1972682040
cites work: Rudiments of \(\mu\)-calculus
cites work: Almost finite expansions of arbitrary semigroups
cites work: Confluent and Other Types of Thue Systems
cites work: Q4364501
cites work: Complexity results for 1-safe nets
cites work: Combinatorics on traces
cites work: SOLVABILITY OF EQUATIONS IN GRAPH GROUPS IS DECIDABLE
cites work: Partially Commutative Inverse Monoids
cites work: ALGORITHMIC PROBLEMS ON INVERSE MONOIDS OVER VIRTUALLY FREE GROUPS
cites work: Graph groups, coherence, and three-manifolds
cites work: Subgroups of graph groups
cites work: Q4258575
cites work: On the rational subset problem for groups.
cites work: Q2754072
cites work: Word Problems Solvable in Logspace
cites work: Q2778879
cites work: Inverse monoids: decidability and complexity of algebraic questions.
cites work: E-unitary inverse monoids and the Cayley graph of a group presentation
cites work: Inverse Monoids, Trees, and Context-Free Languages
cites work: Q3123636
cites work: An Algorithm for the General Petri Net Reachability Problem
cites work: The Word Problem in the Variety of Inverse Semigroups with Abélian Covers
cites work: Q5545557
cites work: The theory of ends, pushdown automata, and second-order logic
cites work: Free Inverse Semigroups
cites work: Q4298260
cites work: Q3337662
cites work: Decidability of Second-Order Theories and Automata on Infinite Trees
cites work: Q3219122
cites work: Presentations of inverse monoids
cites work: Pushdown processes: Games and model-checking
cites work: The word problem for free partially commutative groups
DOI: 10.1007/S00233-008-9060-X
description: scientific article; zbMATH DE number 5377128