Terminating left-hand sides of scattered context productions M. Nivat
type: Item
instance of: scholarly article
title: Terminating left-hand sides of scattered context productions M. Nivat
zbMATH Open document ID: 0943.68085
DOI: 10.1016/S0304-3975(99)00292-3
published in: Theoretical Computer Science
publication date: 2000-06-04T00:00:00Z
review text: The left-hand side of a scattered context production, \((A_{1},A_{2},\ldots,A_{n})\rightarrow (x_{1},x_{2},\ldots,x_{n})\), is terminating if \(A_{1}A_{2}\ldots A_{n}\) derives a terminal word. This paper discusses scattered context grammars whose sentential forms contain sequences of nonterminals formed by shuffling the terminating left-hand sides of productions. It proves that these grammars do not generate some context-sensitive languages, so they are less powerful than the scattered context grammars whose sentential forms are unrestricted. In its conclusion, this paper demonstrates the impact of this result and discusses open problems.
Mathematics Subject Classification ID: 68Q42
zbMATH DE Number: 1454572
zbMATH Keywords: scattered context grammars
zbMATH Keywords: generative power
author: Alexander Meduna
MaRDI profile type: Publication
cites work: Scattered context grammars
cites work: Syntactic complexity of scattered context grammars
cites work: Q4436356
cites work: Four-nonterminal scattered context grammars characterize the family of recursively enumerable languages
cites work: Q4742319
cites work: Q4714446
cites work: Q4692941
description: scientific article; zbMATH DE number 1454572