A Note on Scattered Context Grammars with Non-Context-Free Components
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F07%3APU70878" target="_blank" >RIV/00216305:26230/07:PU70878 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
A Note on Scattered Context Grammars with Non-Context-Free Components
Original language description
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 generativepower of scattered context grammars with context-sensitive and unrestricted productions and discuss some open problems.<br><br>
Czech name
O gramatikách s rozptýleným kontextem s jinými než bezkontextovými komponentami
Czech description
Gramatiky s rozptýlemým kontextem, zavedené jako přímočaré rozšíření bezkontextových gramatik, aplikují při generování svých vět paralelně n bezkontextoých pravidel. Tato práce diskutuje jejich omezení, ve kterých jsou všechny komponenty pravidel gramatik s rozptýleným kontextem buď lineární nebo pravě lineární. Je ukázáno, že rodiny jazyků generovaných těmito gramatikami jsou ekvivalentní rodinám generovaným lineárními a pravě lineárními jednoduchými maticovými gramatikami. Nakonec je zmíněna síla gramatik s rozptýleným kontextem s kontextovými a neomezenými pravidly a jsou diskutovány některé otevřené problémy.<br>
Classification
Type
D - Article in proceedings
CEP classification
BD - Information theory
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GD102%2F05%2FH050" target="_blank" >GD102/05/H050: Integrated Approach to Education of PhD Students in the Area of Parallel and Distributed Systems</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2007
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
MEMICS 2007 Proceedings
ISBN
978-80-7355-077-6
ISSN
—
e-ISSN
—
Number of pages
8
Pages from-to
225-232
Publisher name
Ing. Zdeněk Novotný, CSc.
Place of publication
Znojmo
Event location
Znojmo
Event date
Oct 26, 2007
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—