Journal article

MEDUNA Alexander. Terminating Left-Hand Sides of Scattered Context Grammars. Theoretical Computer Science. Paris: Elsevier Science, 2000, vol. 2000, no. 237, pp. 424-427. ISSN 0304-3975.
Publication language:english
Original title:Terminating Left-Hand Sides of Scattered Context Grammars
Title (cs):Terminální pravé strany pravidel gramatik s roztroušeným kontextem
Pages:424-427
Book:Theoretical Computer Science
Place:Amsterdam, NL
Year:2000
Journal:Theoretical Computer Science, Vol. 2000, No. 237, Paris, FR
ISSN:0304-3975
Keywords
scattered context grammars, left-hand sides of productions, context-sensitive languages
Annotation
This paper discusses scattered context grammars whose sentential forms contain sequences of nonterminals formed by shuffling the terminating left-hand sides of productions.
Abstract
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.
BibTeX:
@ARTICLE{
   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 = {http://www.fit.vutbr.cz/research/view_pub.php?id=6181}
}

Your IPv4 address: 54.82.56.95
Switch to IPv6 connection

DNSSEC [dnssec]