The word problem for free partially commutative groups
From MaRDI portal
The aim of this paper is to prove the two following facts: every free partially commutative group can be considered as a monoid given by a preperfect Thue system and there exists a linear time consuming algorithm solving the word problem in the free partially commutative groups.
Recommendations
Cites work
- Automata and partial commutations
- Confluent and Other Types of Thue Systems
- scientific article; zbMATH DE number 4030960 (Why is no real title available?)
- scientific article; zbMATH DE number 3528212 (Why is no real title available?)
- On some equations in free partially commutative monoids
- Rewriting systems and word problems in a free partially commutative monoid
- Some properties of commutation in free partially commutative monoids
- The undecidability of the preperfectness of Thue systems
- Une généralisation des ensembles de Dyck
Cited in
(26)- Rewriting systems and word problems in a free partially commutative monoid
- On the word problem for free bands of groups and for free objects in some other varieties of completely regular semigroups
- Trace monoids with some invertible generators: Two decision problems
- On the Knuth-Bendix completion for concurrent processes
- The word problem for free partially commutative, partially associative groupoids
- Graph groups are biautomatic
- The power word problem in graph products
- The Quotient of a Free Product of Groups by a Single High-Powered Relator. III. The Word Problem
- Finding \(k\) partially disjoint paths in a directed planar graph
- scientific article; zbMATH DE number 4136215 (Why is no real title available?)
- Cubical homology and the Leech dimension of free partially commutative monoids
- SIMPLE ORDERINGS FOR FREE PARTIALLY COMMUTATIVE GROUPS
- Intersection problem for Droms RAAGs
- Compressed decision problems for graph products and applications to (outer) automorphism groups.
- Geometry and Combinatorics via Right-Angled Artin Groups
- Word problems over traces which are solvable in linear time
- The equation x^2y^2=g in partially commutative groups.
- The equation \([x,y]=g\) in partially commutative groups.
- On properties not inherited by monoids from their Schützenberger groups.
- scientific article; zbMATH DE number 2221703 (Why is no real title available?)
- Partially Commutative Inverse Monoids
- The power word problem in graph products
- Security analysis of word problem-based cryptosystems
- Word problems over traces which are solvable in linear time
- The submonoid and rational subset membership problems for graph groups.
- Partially commutative inverse monoids.
This page was built for publication: The word problem for free partially commutative groups
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1109139)