Publication detail

Maximal and Minimal Scattered Context Rewriting

MEDUNA, A. TECHET, J.

Original Title

Maximal and Minimal Scattered Context Rewriting

Type

article in a collection out of WoS and Scopus

Language

English

Original 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.

Keywords

formal languages, scattered context grammars, generative power

Authors

MEDUNA, A.; TECHET, J.

RIV year

2007

Released

30. 8. 2007

Publisher

Springer Verlag

Location

Budapest

ISBN

0302-9743

Periodical

Lecture Notes in Computer Science

Year of study

2007

Number

4639

State

Federal Republic of Germany

Pages from

412

Pages to

423

Pages count

12

BibTex

@inproceedings{BUT28796,
  author="Alexandr {Meduna} and Jiří {Techet}",
  title="Maximal and Minimal Scattered Context Rewriting",
  booktitle="FCT 2007 Proceedings",
  year="2007",
  journal="Lecture Notes in Computer Science",
  volume="2007",
  number="4639",
  pages="412--423",
  publisher="Springer Verlag",
  address="Budapest",
  issn="0302-9743"
}