The equivalence and inclusion problems for NTS languages

DOI10.1016/0022-0000(85)90055-8zbMath0604.68086OpenAlexW1997305350MaRDI QIDQ1083219

Géraud Sénizergues

Publication date: 1985

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(85)90055-8

zbMATH Keywords

context-free grammardecidable equivalence problemNTS grammarsundecidable inclusion problem

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

NTS languages are deterministic and congruential ⋮ On the generating power of regularly controlled bidirectional grammars ⋮ Rational subsets of partially reversible monoids ⋮ Thue systems as rewriting systems ⋮ The equivalence of pre-NTS grammars is decidable ⋮ A formal specification of document processing ⋮ Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages ⋮ It is decidable whether a monadic thue system is canonical over a regular set ⋮ A polynomial algorithm testing partial confluence of basic semi-Thue systems ⋮ Deciding the NTS property of context-free grammars ⋮ Distributional Learning of Context-Free and Multiple Context-Free Grammars ⋮ Synchronizing deterministic push-down automata can be really hard ⋮ Some decision problems about controlled rewriting systems ⋮ A characterisation of deterministic context-free languages by means of right-congruences ⋮ Identification in the Limit of k,l-Substitutable Context-Free Languages ⋮ The inclusion problem for some subclasses of context-free languages ⋮ The pre-NTS property is undecidable for context-free grammars ⋮ A polynomial algorithm testing partial confluence of basic semi-Thue systems ⋮ Unnamed Item ⋮ Probabilistic learnability of context-free grammars with basic distributional properties from positive examples

Cites Work

• Remarques sur les langages de parenthèses
• NTS languages are deterministic and congruential
• NTS grammars and Church-Rosser systems
• Nest sets and relativized closure properties
• Deterministic one-counter automata
• Infinite regular Thue systems
• Une généralisation des ensembles de Dyck
• The equivalence problem for real-time strict deterministic languages
• Confluent and Other Types of Thue Systems
• Generalizations of regular sets and their application to a study of context-free languages
• The equivalence problem for deterministic finite-turn pushdown automata
• Parenthesis Grammars
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item