Detail publikace
Maximal and Minimal Scattered Context Rewriting
MEDUNA, A. TECHET, J.
Originální název
Maximal and Minimal Scattered Context Rewriting
Anglický název
Maximal and Minimal Scattered Context Rewriting
Jazyk
en
Originální abstrakt
As their name suggest, during a maximal derivation step, a scattered context grammar G rewrites the maximal number of nonterminals while during a minimal derivation step, G rewrites the minimal number of nonterminals. This paper demonstrates that if the propagating scattered context grammars derive their sentences by making either of these two derivation steps, then they characterize the family of context sensitive languages.
Anglický abstrakt
As their name suggest, during a maximal derivation step, a scattered context grammar G rewrites the maximal number of nonterminals while during a minimal derivation step, G rewrites the minimal number of nonterminals. This paper demonstrates that if the propagating scattered context grammars derive their sentences by making either of these two derivation steps, then they characterize the family of context sensitive languages.
Dokumenty
BibTex
@inproceedings{BUT28796,
author="Alexandr {Meduna} and Jiří {Techet}",
title="Maximal and Minimal Scattered Context Rewriting",
annote="As their name suggest, during a maximal derivation step, a scattered context
grammar G rewrites the maximal number of nonterminals while during a minimal
derivation step, G rewrites the minimal number of nonterminals. This paper
demonstrates that if the propagating scattered context grammars derive their
sentences by making either of these two derivation steps, then they characterize
the family of context sensitive languages.",
address="Springer Verlag",
booktitle="FCT 2007 Proceedings",
chapter="28796",
howpublished="print",
institution="Springer Verlag",
journal="Lecture Notes in Computer Science (IF 0,513)",
number="4639",
year="2007",
month="august",
pages="412--423",
publisher="Springer Verlag",
type="conference paper"
}