Detail výsledku

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

TECHET, J. A Note on Scattered Context Grammars with Non-Context-Free Components. MEMICS 2007 Proceedings. Znojmo: Ing. Zdeněk Novotný, CSc., 2007. p. 225-232. ISBN: 978-80-7355-077-6.
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Techet Jiří, Ing., Ph.D., FIT (FIT), UIFS (FIT)
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

Rok
2007
Strany
225–232
Sborník
MEMICS 2007 Proceedings
Konference
MEMICS'07 -- 3rd Doctoral Workshop on Mathematical and Engineering Methods in Computer Science
ISBN
978-80-7355-077-6
Vydavatel
Ing. Zdeněk Novotný, CSc.
Místo
Znojmo
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"
}
Projekty
Integrovaný přístup k výchově studentů DSP v oblasti paralelních a distribuovaných systémů, GAČR, Doktorské granty, GD102/05/H050, zahájení: 2005-01-01, ukončení: 2008-12-31, ukončen
Výzkumné skupiny
Výzkumná skupina formálních modelů (VZ FM)
Pracoviště
Ústav informačních systémů (UIFS)
Nahoru