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 problem; partial confluence problem; word problem for the syntactic congruence of one class

Mathematics Subject Classification ID

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 polynomial algorithm testing partial confluence of basic semi-Thue systems, On rationally controlled one-rule insertion systems, 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, On prefixal one-rule string rewrite systems, Rational subsets of partially reversible monoids, Deterministic pushdown-CD-systems of stateless deterministic R(1)-automata, On the rational subsets of the monogenic free inverse monoid, Term Rewriting with Prefix Context Constraints and Bottom-Up Strategies, INFINITE WORDS AND CONFLUENT REWRITING SYSTEMS: ENDOMORPHISM EXTENSIONS

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