Detail publikačního výsledku

A Note on Scattered Context Grammars with Non-Context-Free Components

TECHET, J.

Originální název

A Note on Scattered Context Grammars with Non-Context-Free Components

Anglický název

A Note on Scattered Context Grammars with Non-Context-Free Components

Druh

Stať ve sborníku mimo WoS a Scopus

Originální abstrakt

Scattered context grammars, introduced as a straightforward generalization of context-free grammars, apply n context-free productions in parallel to generate their sentences. This paper discusses their restricted versions in which all components of scattered context productions are either linear or right-linear. We prove that the families of languages generated by these grammars are equivalent to the families generated by linear and right-linear simple matrix grammars. Finally, we mention the generative power of scattered context grammars with context-sensitive and unrestricted productions and discuss some open problems.

Anglický abstrakt

Scattered context grammars, introduced as a straightforward generalization of context-free grammars, apply n context-free productions in parallel to generate their sentences. This paper discusses their restricted versions in which all components of scattered context productions are either linear or right-linear. We prove that the families of languages generated by these grammars are equivalent to the families generated by linear and right-linear simple matrix grammars. Finally, we mention the generative power of scattered context grammars with context-sensitive and unrestricted productions and discuss some open problems.

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

TECHET, J.

Vydáno

26.10.2007

Nakladatel

Ing. Zdeněk Novotný, CSc.

Místo

Znojmo

ISBN

978-80-7355-077-6

Kniha

MEMICS 2007 Proceedings

Strany od

225

Strany do

232

Strany počet

8

BibTex

@inproceedings{BUT25334,
  author="Jiří {Techet}",
  title="A Note on Scattered Context Grammars with Non-Context-Free Components",
  booktitle="MEMICS 2007 Proceedings",
  year="2007",
  pages="225--232",
  publisher="Ing. Zdeněk Novotný, CSc.",
  address="Znojmo",
  isbn="978-80-7355-077-6"
}