Detail publikace

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

Typ

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

Jazyk

angličtina

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.

Klíčová slova

formal languages, scattered context grammars, generative power

Autoři

TECHET, J.

Rok RIV

2007

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