NTS languages are deterministic and congruential

DOI10.1016/0022-0000(85)90056-XzbMath0604.68087MaRDI QIDQ1083220

Luc Boasson, Géraud Sénizergues

Publication date: 1985

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

zbMATH Keywords

context-free grammarcongruence classesdeterministic languagesNTS grammars

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (23)

The equivalence and inclusion problems for NTS languages ⋮ On the generating power of regularly controlled bidirectional grammars ⋮ Thue systems as rewriting systems ⋮ Learning deterministic context free grammars: the Omphalos competition ⋮ The equivalence of pre-NTS grammars is decidable ⋮ A formal specification of document processing ⋮ Time-bounded controlled bidirectional grammars ⋮ Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages ⋮ A polynomial algorithm testing partial confluence of basic semi-Thue systems ⋮ Locally Chain-Parsable Languages ⋮ McNaughton families of languages. ⋮ 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 ⋮ About the descriptive power of certain classes of finite string-rewriting systems ⋮ 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 ⋮ Groups and NTS languages ⋮ Toward a theory of input-driven locally parsable languages ⋮ Probabilistic learnability of context-free grammars with basic distributional properties from positive examples

Cites Work

• Unnamed Item
• Unnamed Item
• The equivalence and inclusion problems for NTS languages
• NTS grammars and Church-Rosser systems
• Une généralisation des ensembles de Dyck
• Optimization of LR(k) parsers
• The equivalence problem for real-time strict deterministic languages
• A Transformation System for Developing Recursive Programs
• Parenthesis Grammars

This page was built for publication: NTS languages are deterministic and congruential