Publication Details

Maximal and Minimal Scattered Context Rewriting

MEDUNA Alexander and TECHET Jiří. Maximal and Minimal Scattered Context Rewriting. In: FCT 2007 Proceedings. Budapest: Springer Verlag, 2007, pp. 412-423. ISSN 0302-9743.
Czech title
Maximální a minimální přepisování gramatikami s rozptýleným kontextem
Type
conference paper
Language
english
Authors
Keywords

formal languages, scattered context grammars, generative power

Abstract

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.

Published
2007
Pages
412-423
Journal
Lecture Notes in Computer Science, vol. 2007, no. 4639, ISSN 0302-9743
Proceedings
FCT 2007 Proceedings
Conference
16th International Symposium on Fundamentals of Computation Theory, Budapest, HU
Publisher
Springer Verlag
Place
Budapest, HU
BibTeX
@INPROCEEDINGS{FITPUB8360,
   author = "Alexander Meduna and Ji\v{r}\'{i} Techet",
   title = "Maximal and Minimal Scattered Context Rewriting",
   pages = "412--423",
   booktitle = "FCT 2007 Proceedings",
   journal = "Lecture Notes in Computer Science",
   volume = 2007,
   number = 4639,
   year = 2007,
   location = "Budapest, HU",
   publisher = "Springer Verlag",
   ISSN = "0302-9743",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8360"
}
Back to top