NTS languages are deterministic and congruential
type: Item
instance of: scholarly article
title: NTS languages are deterministic and congruential
zbMATH Open document ID: 0604.68087
DOI: 10.1016/0022-0000(85)90056-X
published in: Journal of Computer and System Sciences
publication date: 1985-01-01T00:00:00Z
review text: A context-free grammar is said to be NTS if the set of sentential forms it generates is unchanged when the rules are used both ways. We prove here that such grammars generate deterministic languages which are finite unions of congruence classes. Moreover, we show that this family of languages is closed under reversal and intersection with regular sets. A forthcoming paper will prove that, for this class, the equivalence problem is decidable.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3976373
zbMATH Keywords: NTS grammars
zbMATH Keywords: context-free grammar
zbMATH Keywords: deterministic languages
zbMATH Keywords: congruence classes
author: Luc Boasson
author: Géraud Sénizergues
MaRDI profile type: Publication
cites work: Optimization of LR(k) parsers
cites work: NTS grammars and Church-Rosser systems
cites work: A Transformation System for Developing Recursive Programs
cites work: Q5181346
cites work: Une généralisation des ensembles de Dyck
cites work: Q4192941
cites work: Parenthesis Grammars
cites work: The equivalence problem for real-time strict deterministic languages
cites work: The equivalence and inclusion problems for NTS languages
description: scientific article; zbMATH DE number 3976373