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?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Note on Pushdown Store Automata and Regular Systems
- A characterisation of deterministic context-free languages by means of right-congruences
- An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
- Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages
- Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
- Infinite regular Thue systems
- Monadic Thue systems
- NTS languages are deterministic and congruential
- On deciding the confluence of a finite string-rewriting system on a given congruence class
- On the complexity of some extended word problems defined by cancellation rules
- On the regular equivalence problem for regular Thue systems
- Optimization of LR(k) parsers
- Some undecidability results for non-monadic Church-Rosser Thue systems
- The equivalence and inclusion problems for NTS languages
- The equivalence problem for deterministic finite-turn pushdown automata
- The equivalence problem for real-time DPDAs
- Thue systems as rewriting systems
- Une généralisation des ensembles de Dyck
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
- Term rewriting with prefix context constraints and bottom-up strategies
- 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
- 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)
