Testing for the Church-Rosser property
From MaRDI portal
Publication:1162144
DOI10.1016/0304-3975(81)90078-5zbMath0479.68035OpenAlexW2071219059MaRDI QIDQ1162144
Ronald V. Book, Colm P. O'Dunlaing
Publication date: 1981
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(81)90078-5
Related Items
Reductions in tree replacement systems, Thue systems as rewriting systems, Rewriting systems and word problems in a free partially commutative monoid, On deciding the confluence of a finite string-rewriting system on a given congruence class, Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule, A note on thue systems with a single defining relation, Decidable sentences of Church-Rosser congruences, The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems, It is decidable whether a monadic thue system is canonical over a regular set, On confluence of one-rule trace-rewriting systems, A note on confluent Thue systems, Confluence of one-rule Thue systems, Equational Theorem Proving for Clauses over Strings, Decision problems for finite special string-rewriting systems that are confluent on some congruence class, NTS grammars and Church-Rosser systems, Monadic Thue systems, When is a monoid a group? The Church-Rosser case is tractable, Church-Rosser systems with respect to formal languages, Contributions of Ronald V. Book to the theory of string-rewriting systems, Finite complete rewriting systems for the Jantzen monoid and the Greendlinger group, Cancellativity in finitely presented semigroups, A note on special thue systems with a single defining relation, Infinite regular Thue systems, Undecidable questions related to Church-Rosser Thue systems, An \(O(| T| ^ 3)\) algorithm for testing the Church-Rosser property of Thue systems, The undecidability of the preperfectness of Thue systems, Homogeneous Thue systems and the Church-Rosser property, Confluence problems for trace rewriting systems, The Church-Rosser property and special Thue systems
Cites Work
- Monadic Thue systems
- Une généralisation des ensembles de Dyck
- On theories with a combinatorial definition of 'equivalence'
- Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
- Confluent and Other Types of Thue Systems
- Tree-Manipulating Systems and Church-Rosser Theorems
- Unnamed Item
- Unnamed Item
- Unnamed Item
