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

Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
Techet Jiří, Ing., Ph.D. (DIFS FIT BUT)

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