Detail publikačního výsledku

Maximal and Minimal Scattered Context Rewriting

MEDUNA, A.; TECHET, J.

Originální název

Maximal and Minimal Scattered Context Rewriting

Anglický název

Maximal and Minimal Scattered Context Rewriting

Druh

Stať ve sborníku mimo WoS a Scopus

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.

Anglický 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

Klíčová slova v angličtině

formal languages, scattered context grammars, generative power

Autoři

MEDUNA, A.; TECHET, J.

Vydáno

30.08.2007

Nakladatel

Springer Verlag

Místo

Budapest

Kniha

FCT 2007 Proceedings

ISSN

0302-9743

Periodikum

Lecture Notes in Computer Science

Svazek

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