Publication result detail

Maximal and Minimal Scattered Context Rewriting

MEDUNA, A.; TECHET, J.

Original Title

Maximal and Minimal Scattered Context Rewriting

English Title

Maximal and Minimal Scattered Context Rewriting

Type

Paper in proceedings outside WoS and Scopus

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.

English 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

Key words in English

formal languages, scattered context grammars, generative power

Authors

MEDUNA, A.; TECHET, J.

Released

30.08.2007

Publisher

Springer Verlag

Location

Budapest

Book

FCT 2007 Proceedings

ISBN

0302-9743

Periodical

Lecture Notes in Computer Science

Volume

2007

Number

4639

State

Federal Republic of Germany

Pages from

412

Pages to

423

Pages count

12

Full text in the Digital Library

http://hdl.handle.net/

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