A characterisation of deterministic context-free languages by means of right-congruences

DOI10.1016/0304-3975(90)90123-YzbMath0699.68099OpenAlexW2040948474MaRDI QIDQ913524

Géraud Sénizergues

Publication date: 1990

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

Full work available at URL: https://doi.org/10.1016/0304-3975(90)90123-y

zbMATH Keywords

congruencesdeterministic context-free languagescontrolled rewriting systems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Thue and Post systems, etc. (03D03)

Related Items (3)

A polynomial algorithm testing partial confluence of basic semi-Thue systems ⋮ Some decision problems about controlled rewriting systems ⋮ A polynomial algorithm testing partial confluence of basic semi-Thue systems

Cites Work

• Some decision problems about controlled rewriting systems
• Fundamental properties of infinite trees
• The equivalence and inclusion problems for NTS languages
• Thue systems as rewriting systems
• Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages
• Monadic Thue systems
• Infinite regular Thue systems
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• On jump-deterministic 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

This page was built for publication: A characterisation of deterministic context-free languages by means of right-congruences