An Infinite Hierarchy of Language Families Generated by Scattered Context Grammars with n-Limited Derivations
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F09%3APU82559" target="_blank" >RIV/00216305:26230/09:PU82559 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
An Infinite Hierarchy of Language Families Generated by Scattered Context Grammars with n-Limited Derivations
Popis výsledku v původním jazyce
This paper introduces scattered context grammars without erasing productions, in which an application of a production always occurs within the first n nonterminals of the current sentential form. It demonstrates that this restriction gives rise to an infinite hierarchy of language families each of which is properly included in the family of context-sensitive languages. In addition, it proves analogous results for unordered scattered context grammars. Some consequences of these results are derived and open problems formulated.<br>
Název v anglickém jazyce
An Infinite Hierarchy of Language Families Generated by Scattered Context Grammars with n-Limited Derivations
Popis výsledku anglicky
This paper introduces scattered context grammars without erasing productions, in which an application of a production always occurs within the first n nonterminals of the current sentential form. It demonstrates that this restriction gives rise to an infinite hierarchy of language families each of which is properly included in the family of context-sensitive languages. In addition, it proves analogous results for unordered scattered context grammars. Some consequences of these results are derived and open problems formulated.<br>
Klasifikace
Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
BD - Teorie informace
OECD FORD obor
—
Návaznosti výsledku
Projekt
Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)
Ostatní
Rok uplatnění
2009
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
Theoretical Computer Science
ISSN
0304-3975
e-ISSN
—
Svazek periodika
410
Číslo periodika v rámci svazku
21
Stát vydavatele periodika
FR - Francouzská republika
Počet stran výsledku
9
Strana od-do
—
Kód UT WoS článku
—
EID výsledku v databázi Scopus
—