The pre-NTS property is undecidable for context-free grammars
type: Item
instance of: scholarly article
title: The pre-NTS property is undecidable for context-free grammars
zbMATH Open document ID: 0779.68054
DOI: 10.1016/0020-0190(92)90082-7
author: Louxin Zhang
published in: Information Processing Letters
publication date: 1993-05-16T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q42
zbMATH DE Number: 166442
reviewed by: Gheorghe Păun
MaRDI profile type: Publication
full work available at URL: 0020-0190(92)90082-7
OpenAlex ID: W2093306186
cites work: The equivalence of pre-NTS grammars is decidable
cites work: NTS languages are deterministic and congruential
cites work: Thue systems as rewriting systems
cites work: Q3247126
cites work: Q3862379
cites work: On weakly confluent monadic string-rewriting systems
cites work: On deciding the confluence of a finite string-rewriting system on a given congruence class
cites work: The equivalence and inclusion problems for NTS languages
description: scientific article; zbMATH DE number 166442