Publication Details

Terminating Left-Hand Sides of Scattered Context Grammars

MEDUNA Alexander. Terminating Left-Hand Sides of Scattered Context Grammars. Theoretical Computer Science, vol. 2000, no. 237, pp. 424-427. ISSN 0304-3975.
Czech title
Terminální pravé strany pravidel gramatik s roztroušeným kontextem
Type
journal article
Language
english
Authors
Keywords

scattered context grammars, left-hand sides of productions, context-sensitive languages

Abstract

This paper discusses scattered context grammars whose sentential forms contain sequences of nonterminals formed by shuffling the terminating left-hand sides of productions.

Annotation

The left-hand side of a scattered context production, (A_1, A_2, \ldots, A_n) \to (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 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.

Published
2000
Pages
424-427
Journal
Theoretical Computer Science, vol. 2000, no. 237, ISSN 0304-3975
Book
Theoretical Computer Science
Publisher
Elsevier Science
Place
Amsterdam, NL
BibTeX
@ARTICLE{FITPUB6181,
   author = "Alexander Meduna",
   title = "Terminating Left-Hand Sides of Scattered Context Grammars",
   pages = "424--427",
   booktitle = "Theoretical Computer Science",
   journal = "Theoretical Computer Science",
   volume = 2000,
   number = 237,
   year = 2000,
   location = "Amsterdam, NL",
   ISSN = "0304-3975",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/6181"
}
Back to top