Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages
From MaRDI portal
Publication:1120292
DOI10.1016/0890-5401(89)90032-1zbMath0672.68040OpenAlexW2105006916MaRDI QIDQ1120292
Publication date: 1989
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0890-5401(89)90032-1
Related Items (6)
Deterministic pushdown-CD-systems of stateless deterministic R(1)-automata ⋮ Some decision problems about controlled rewriting systems ⋮ About the descriptive power of certain classes of finite string-rewriting systems ⋮ A characterisation of deterministic context-free languages by means of right-congruences ⋮ A polynomial algorithm testing partial confluence of basic semi-Thue systems ⋮ \(L(A)=L(B)\)? decidability results from complete formal systems
Cites Work
- Finite complete rewriting systems and the complexity of word problem
- Remarques sur les langages de parenthèses
- The equivalence and inclusion problems for NTS languages
- NTS languages are deterministic and congruential
- The equivalence problem for two dpda's, one of which is a finite-turn or one-counter machine
- Monadic Thue systems
- Deterministic one-counter automata
- An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
- Undecidable questions related to Church-Rosser Thue systems
- The equivalence problem for real-time DPDAs
- Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
- The equivalence problem for deterministic finite-turn pushdown automata
- Deterministic context free languages
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages
