The pre-NTS property is undecidable for context-free grammars
A grammar \(G\) is called non-terminal separable (NTS) (respectively, pre- NTS) if the set of sentential forms (respectively, the language) it generates is unchanged when the rules in \(G\) are used both ways. Such grammars were introduced by \textit{L. Boasson} and \textit{G. Senizergues} in [J. Comput. Syst. Sci., 31, 332-342 (1985; Zbl 0604.68087)]. The NTS property is decidable [\textit{F. Otto}, J. Comput. Syst. Sci. 35, 285-310 (1987; Zbl 0645.03033) and \textit{G. Senizergues}, J. Comput. Syst. Sci., 31, 303-331 (1985; Zbl 0604.68086)] in polynomial time [\textit{K. Madlener}, \textit{P. Narandran}, \textit{F. Otto} and \textit{L. Zhang}, Theoret. Comput. Sci. (1993)]. In the present note one proves that the pre-NTS property is undecidable. The use technique is the simulation of a Turing machine through a finite monadic string-rewriting system.
- scientific article; zbMATH DE number 3131080 (Why is no real title available?)
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- NTS languages are deterministic and congruential
- On deciding the confluence of a finite string-rewriting system on a given congruence class
- On weakly confluent monadic string-rewriting systems
- The equivalence and inclusion problems for NTS languages
- The equivalence of pre-NTS grammars is decidable
- Thue systems as rewriting systems
This page was built for publication: The pre-NTS property is undecidable for context-free grammars
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1208437)
