Rewriting systems and word problems in a free partially commutative monoid
DOI10.1016/0020-0190(87)90032-9zbMATH Open0643.68101OpenAlexW2072390086MaRDI QIDQ1102124FDOQ1102124
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
Recommendations
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)
Cites Work
- Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
- Title not available (Why is that?)
- An application of the theory of free partially commutative monoids: Asymptotic densities of trace languages
- Confluent and Other Types of Thue Systems
- Testing for the Church-Rosser property
- The undecidability of the preperfectness of Thue systems
- Maximal serializability of iterated transactions
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (21)
- Complete rewriting systems and homology of monoid algebras
- Concurrency measure in commutation monoids
- Word problems over traces which are solvable in linear time
- On deciding confluence of finite string-rewriting systems modulo partial commutativity
- 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
- A polynomial algorithm testing partial confluence of basic semi-Thue systems
- Monomial orderings, rewriting systems, and Gröbner bases for the commutator ideal of a free algebra
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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.
- Title not available (Why is that?)
- Overlaps in free partially commutative monoids
- Title not available (Why is that?)
- 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)
