Rewriting systems and word problems in a free partially commutative monoid

DOI10.1016/0020-0190(87)90032-9zbMath0643.68101OpenAlexW2072390086MaRDI QIDQ1102124

Hai-Ning Liu, Ronald V. Book

Publication date: 1987

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(87)90032-9

zbMATH Keywords

rewriting systemsfree partially commutative monoiddecidable word problemfinite Thue systems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Thue and Post systems, etc. (03D03)

Related Items

Overlaps in free partially commutative monoids ⋮ Efficient solution of some problems in free partially commutative monoids ⋮ Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule ⋮ The word problem for free partially commutative groups ⋮ On confluence of one-rule trace-rewriting systems ⋮ Word problems over traces which are solvable in linear time ⋮ Trace monoids with some invertible generators: Two decision problems ⋮ Parabolic and quasiparabolic subgroups of free partially commutative groups. ⋮ On the Knuth-Bendix completion for concurrent processes ⋮ On deciding confluence of finite string-rewriting systems modulo partial commutativity ⋮ Word problems over traces which are solvable in linear time

Cites Work

• The undecidability of the preperfectness of Thue systems
• Maximal serializability of iterated transactions
• Testing for the Church-Rosser property
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• An application of the theory of free partially commutative monoids: Asymptotic densities of trace languages
• Confluent and Other Types of Thue Systems
• Unnamed Item
• Unnamed Item
• Unnamed Item