Some decision problems about controlled rewriting systems

DOI10.1016/0304-3975(90)90048-MzbMath0695.68056MaRDI QIDQ910246

Géraud Sénizergues

Publication date: 1990

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

class equivalence problempartial confluence problemword problem for the syntactic congruence of one class

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Abstract data types; algebraic specification (68Q65) Thue and Post systems, etc. (03D03)

Related Items

On rationally controlled one-rule insertion systems ⋮ Term Rewriting with Prefix Context Constraints and Bottom-Up Strategies ⋮ Rational subsets of partially reversible monoids ⋮ Deterministic pushdown-CD-systems of stateless deterministic R(1)-automata ⋮ A polynomial algorithm testing partial confluence of basic semi-Thue systems ⋮ On the rational subsets of the monogenic free inverse monoid ⋮ A characterisation of deterministic context-free languages by means of right-congruences ⋮ A polynomial algorithm testing partial confluence of basic semi-Thue systems ⋮ INFINITE WORDS AND CONFLUENT REWRITING SYSTEMS: ENDOMORPHISM EXTENSIONS ⋮ Some undecidability results concerning the property of preserving regularity ⋮ On prefixal one-rule string rewrite systems ⋮ \(L(A)=L(B)\)? decidability results from complete formal systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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