Some decision problems about controlled rewriting systems
From MaRDI portal
Publication:910246
DOI10.1016/0304-3975(90)90048-MzbMath0695.68056MaRDI QIDQ910246
Publication date: 1990
Published in: Theoretical Computer Science (Search for Journal in Brave)
class equivalence problem; partial confluence problem; word problem for the syntactic congruence of one class
68Q45: Formal languages and automata
03D05: Automata and formal grammars in connection with logical questions
68Q65: Abstract data types; algebraic specification
03D03: Thue and Post systems, etc.
Related Items
A characterisation of deterministic context-free languages by means of right-congruences, A polynomial algorithm testing partial confluence of basic semi-Thue systems, Some undecidability results concerning the property of preserving regularity, \(L(A)=L(B)\)? decidability results from complete formal systems, Rational subsets of partially reversible monoids, Deterministic pushdown-CD-systems of stateless deterministic R(1)-automata, Term Rewriting with Prefix Context Constraints and Bottom-Up Strategies, INFINITE WORDS AND CONFLUENT REWRITING SYSTEMS: ENDOMORPHISM EXTENSIONS
Cites Work
- On the complexity of some extended word problems defined by cancellation rules
- A characterisation of deterministic context-free languages by means of right-congruences
- Some undecidability results for non-monadic Church-Rosser Thue systems
- The equivalence and inclusion problems for NTS languages
- NTS languages are deterministic and congruential
- On the regular equivalence problem for regular Thue systems
- Thue systems as rewriting systems
- On deciding the confluence of a finite string-rewriting system on a given congruence class
- Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages
- Monadic Thue systems
- An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
- Infinite regular Thue systems
- Une généralisation des ensembles de Dyck
- Optimization of LR(k) parsers
- 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
- A Note on Pushdown Store Automata and Regular Systems
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
