Some decision problems about controlled rewriting systems
DOI10.1016/0304-3975(90)90048-MzbMATH Open0695.68056MaRDI QIDQ910246FDOQ910246
Authors: Géraud Sénizergues 
Publication date: 1990
Published in: Theoretical Computer Science (Search for Journal in Brave)
Recommendations
- A characterisation of deterministic context-free languages by means of right-congruences
- Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages
- Complexity of certain decision problems about congruential languages
- Decision problems for finite special string-rewriting systems that are confluent on some congruence class
- Church-Rosser systems with respect to formal languages
class equivalence problempartial confluence problemword problem for the syntactic congruence of one class
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Thue and Post systems, etc. (03D03) Abstract data types; algebraic specification (68Q65)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Optimization of LR(k) parsers
- 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
- NTS languages are deterministic and congruential
- On deciding the confluence of a finite string-rewriting system on a given congruence class
- Une généralisation des ensembles de Dyck
- On the complexity of some extended word problems defined by cancellation rules
- Monadic Thue systems
- Infinite regular Thue systems
- Title not available (Why is that?)
- Some undecidability results for non-monadic Church-Rosser Thue systems
- Thue systems as rewriting systems
- An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
- Title not available (Why is that?)
- On the regular equivalence problem for regular Thue systems
- The equivalence and inclusion problems for NTS languages
- Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages
- The equivalence problem for real-time DPDAs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A characterisation of deterministic context-free languages by means of right-congruences
Cited In (17)
- On prefixal one-rule string rewrite systems
- \(L(A)=L(B)\)? decidability results from complete formal systems
- Some undecidability results concerning the property of preserving regularity
- A polynomial algorithm testing partial confluence of basic semi-Thue systems
- A polynomial algorithm testing partial confluence of basic semi-Thue systems
- Complexity of certain decision problems about congruential languages
- INFINITE WORDS AND CONFLUENT REWRITING SYSTEMS: ENDOMORPHISM EXTENSIONS
- Title not available (Why is that?)
- Title not available (Why is that?)
- On rationally controlled one-rule insertion systems
- Deterministic pushdown-CD-systems of stateless deterministic R(1)-automata
- A characterisation of deterministic context-free languages by means of right-congruences
- Term Rewriting with Prefix Context Constraints and Bottom-Up Strategies
- On the rational subsets of the monogenic free inverse monoid
- Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages
- On DOS languages and DOS mappings
- Rational subsets of partially reversible monoids
This page was built for publication: Some decision problems about controlled rewriting systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q910246)
