Detail publikace

Maximal and Minimal Scattered Context Rewriting

MEDUNA, A. TECHET, J.

Originální název

Maximal and Minimal Scattered Context Rewriting

Typ

článek ve sborníku ve WoS nebo Scopus

Jazyk

angličtina

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.

Klíčová slova

formal languages, scattered context grammars, generative power

Autoři

MEDUNA, A.; TECHET, J.

Rok RIV

2007

Vydáno

30. 8. 2007

Nakladatel

Springer Verlag

Místo

Budapest

ISSN

0302-9743

Periodikum

Lecture Notes in Computer Science

Ročník

2007

Číslo

4639

Stát

Spolková republika Německo

Strany od

412

Strany do

423

Strany počet

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