Finite canonical rewriting systems for congruences generated by concurrency relations
From MaRDI portal
Publication:3779772
DOI10.1007/BF01692068zbMath0638.68085MaRDI QIDQ3779772
Publication date: 1987
Published in: Mathematical Systems Theory (Search for Journal in Brave)
polynomial timealphabetfree partially commutative monoiddecidabiltyconcurrency relationfinite canonical rewriting system
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)
Related Items
Weights for total division orderings on strings, Restrictions of congruences generated by finite canonical string-rewriting systems, On deciding the confluence of a finite string-rewriting system on a given congruence class, Möbius functions and confluent semi-commutations, On deciding confluence of finite string-rewriting systems modulo partial commutativity
Cites Work
- Unnamed Item
- Unnamed Item
- Finite complete rewriting systems and the complexity of word problem
- A note on a special one-rule semi-Thue system
- A finite Thue system with decidable word problem and without equivalent finite canonical system
- Complete semi-Thue systems for abelian groups
- On lexicographic semi-commutations
- Combinatorial problems of commutation and rearrangements
- On theories with a combinatorial definition of 'equivalence'
- A note on thue systems with a single defining relation
- Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
- Confluent and Other Types of Thue Systems
- A note on special thue systems with a single defining relation
- Tree-Manipulating Systems and Church-Rosser Theorems
