The equivalence of pre-NTS grammars is decidable

DOI10.1007/BF01368784zbMath0766.68085MaRDI QIDQ3992022

Jean-Michel Autebert, Luc Boasson

Publication date: 28 June 1992

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

decidable equivalence problempre-NTS grammars

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (3)

A polynomial algorithm testing partial confluence of basic semi-Thue systems ⋮ The pre-NTS property is undecidable for context-free grammars ⋮ A polynomial algorithm testing partial confluence of basic semi-Thue systems

Cites Work

• Unnamed Item
• Unnamed Item
• The equivalence and inclusion problems for NTS languages
• NTS languages are deterministic and congruential
• A new class of C.F.L. for which the equivalence is decidable
• The equivalence problem for deterministic finite-turn pushdown automata

This page was built for publication: The equivalence of pre-NTS grammars is decidable