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"
}