The word problem for free partially commutative groups

DOI10.1016/S0747-7171(88)80024-5zbMath0655.20027MaRDI QIDQ1109139

S. H. Smith

Publication date: 1988

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

zbMATH Keywords

algorithmword problemfree partially commutative groupspreperfect Thue system

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items (14)

Graph groups are biautomatic ⋮ Geometry and Combinatorics via Right-Angled Artin Groups ⋮ Security analysis of word problem-based cryptosystems ⋮ Intersection problem for Droms RAAGs ⋮ The power word problem in graph products ⋮ Word problems over traces which are solvable in linear time ⋮ Finding k Partially Disjoint Paths in a Directed Planar Graph ⋮ Trace monoids with some invertible generators: Two decision problems ⋮ COMPRESSED DECISION PROBLEMS FOR GRAPH PRODUCTS AND APPLICATIONS TO (OUTER) AUTOMORPHISM GROUPS ⋮ The submonoid and rational subset membership problems for graph groups. ⋮ Partially commutative inverse monoids. ⋮ On properties not inherited by monoids from their Schützenberger groups. ⋮ On the Knuth-Bendix completion for concurrent processes ⋮ Word problems over traces which are solvable in linear time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The undecidability of the preperfectness of Thue systems
• Some properties of commutation in free partially commutative monoids
• On some equations in free partially commutative monoids
• Rewriting systems and word problems in a free partially commutative monoid
• Une généralisation des ensembles de Dyck
• Confluent and Other Types of Thue Systems

This page was built for publication: The word problem for free partially commutative groups