Rewriting systems and word problems in a free partially commutative monoid

DOI10.1016/0020-0190(87)90032-9MaRDI QIDQ1102124zbMATH OpenOpenAlexFDO

Authors Ronald V. Book, Hai-Ning Liu

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) Thue and Post systems, etc. (03D03) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)

Recommendations

• The word problem for free partially commutative groups
• Publication:3469280
• Efficient solution of some problems in free partially commutative monoids
• On deciding confluence of finite string-rewriting systems modulo partial commutativity
• A decision procedure on partially commutative free monoids

Cites work

• scientific article; zbMATH DE number 3970130 (Why is no real title available?)
• scientific article; zbMATH DE number 3972221 (Why is no real title available?)
• scientific article; zbMATH DE number 3756462 (Why is no real title available?)
• An application of the theory of free partially commutative monoids: Asymptotic densities of trace languages
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Confluent and Other Types of Thue Systems
• Maximal serializability of iterated transactions
• Testing for the Church-Rosser property
• The undecidability of the preperfectness of Thue systems

Cited in

(21)

• Complete rewriting systems and homology of monoid algebras
• Concurrency measure in commutation monoids
• On deciding confluence of finite string-rewriting systems modulo partial commutativity
• Word problems over traces which are solvable in linear time
• Two optimal parallel algorithms on the commutation class of a word
• Efficient solution of some problems in free partially commutative monoids
• The word problem for free partially commutative groups
• Monomial orderings, rewriting systems, and Gröbner bases for the commutator ideal of a free algebra
• A polynomial algorithm testing partial confluence of basic semi-Thue systems
• scientific article; zbMATH DE number 4136215 (Why is no real title available?)
• scientific article; zbMATH DE number 4003548 (Why is no real title available?)
• Trace monoids with some invertible generators: Two decision problems
• Word problems over traces which are solvable in linear time
• On the Knuth-Bendix completion for concurrent processes
• Parabolic and quasiparabolic subgroups of free partially commutative groups.
• scientific article; zbMATH DE number 4030960 (Why is no real title available?)
• Overlaps in free partially commutative monoids
• scientific article; zbMATH DE number 4033664 (Why is no real title available?)
• Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule
• On confluence of one-rule trace-rewriting systems
• Partial monoids: associativity and confluence.

This page was built for publication: Rewriting systems and word problems in a free partially commutative monoid

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1102124)