On deciding confluence of finite string-rewriting systems modulo partial commutativity

DOI10.1016/0304-3975(89)90019-4zbMath0686.68027OpenAlexW1984954584MaRDI QIDQ1262758

Friedrich Otto

Publication date: 1989

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(89)90019-4

zbMATH Keywords

confluencestring rewritingcommutativity

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Abstract data types; algebraic specification (68Q65) Word problems, etc. in computability and recursion theory (03D40) Thue and Post systems, etc. (03D03)

Related Items

On confluence of one-rule trace-rewriting systems, One-rule trace-rewriting systems and confluence

Cites Work

• The undecidability of the preperfectness of Thue systems
• Rewriting systems and word problems in a free partially commutative monoid
• Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule
• New decision algorithms for finitely presented commutative semigroups
• Presentations of groups and monoids
• Finite canonical rewriting systems for congruences generated by concurrency relations
• Completion of a Set of Rules Modulo a Set of Equations
• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item