Finite canonical rewriting systems for congruences generated by concurrency relations

DOI10.1007/BF01692068MaRDI QIDQ3779772zbMATH OpenFDO

Authors Friedrich Otto

Publication date 1987

Published in Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

polynomial timealphabetfree partially commutative monoiddecidabiltyconcurrency relationfinite canonical rewriting system

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)

Recommendations

• Restrictions of congruences generated by finite canonical string-rewriting systems
• The problems of cyclic equality and conjugacy for finite complete rewriting systems
• On deciding confluence of finite string-rewriting systems modulo partial commutativity
• FINITENESS CONDITIONS FOR REWRITING SYSTEMS
• Term Rewriting and Applications
• Confluence of algebraic rewriting systems
• A finiteness condition for rewriting systems
• Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems
• scientific article; zbMATH DE number 794237
• scientific article; zbMATH DE number 1419256

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3811849 (Why is no real title available?)
• A finite Thue system with decidable word problem and without equivalent finite canonical system
• A note on a special one-rule semi-Thue system
• A note on special thue systems with a single defining relation
• A note on thue systems with a single defining relation
• Combinatorial problems of commutation and rearrangements
• Complete semi-Thue systems for abelian groups
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Confluent and Other Types of Thue Systems
• Finite complete rewriting systems and the complexity of word problem
• On lexicographic semi-commutations
• On theories with a combinatorial definition of 'equivalence'
• Tree-Manipulating Systems and Church-Rosser Theorems

Cited in

(10)

• On deciding confluence of finite string-rewriting systems modulo partial commutativity
• A finiteness condition for rewriting systems
• Canonized Rewriting and Ground AC Completion Modulo Shostak Theories
• scientific article; zbMATH DE number 794242 (Why is no real title available?)
• On deciding the confluence of a finite string-rewriting system on a given congruence class
• Möbius functions and confluent semi-commutations
• Weights for total division orderings on strings
• The problems of cyclic equality and conjugacy for finite complete rewriting systems
• Restrictions of congruences generated by finite canonical string-rewriting systems
• scientific article; zbMATH DE number 4080962 (Why is no real title available?)

This page was built for publication: Finite canonical rewriting systems for congruences generated by concurrency relations

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