Vylepšení popisné složitosti gramatik regulovaných kontextovými podmínkami
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F06%3APU67018" target="_blank" >RIV/00216305:26230/06:PU67018 - 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 Improvement of the Descriptional Complexity of Grammars Regulated by Context Conditions
Popis výsledku v původním jazyce
This paper improves some well-known results concerning the descriptional complexity of grammars regulated by context conditions. Specifically, it proves that every recursively enumerable language is generated by a generalized forbidding grammar of degreetwo with no more than eight conditional productions and ten nonterminals, or by a simple semi-conditional grammar of degree (2,1) with no more than nine conditional productions and ten nonterminals.
Název v anglickém jazyce
An Improvement of the Descriptional Complexity of Grammars Regulated by Context Conditions
Popis výsledku anglicky
This paper improves some well-known results concerning the descriptional complexity of grammars regulated by context conditions. Specifically, it proves that every recursively enumerable language is generated by a generalized forbidding grammar of degreetwo with no more than eight conditional productions and ten nonterminals, or by a simple semi-conditional grammar of degree (2,1) with no more than nine conditional productions and ten nonterminals.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
JC - Počítačový hardware a software
OECD FORD obor
—
Návaznosti výsledku
Projekt
<a href="/cs/project/GD102%2F05%2FH050" target="_blank" >GD102/05/H050: Integrovaný přístup k výchově studentů DSP v oblasti paralelních a distribuovaných systémů</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2006
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 statě ve sborníku
Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2006)
ISBN
80-214-3287-X
ISSN
—
e-ISSN
—
Počet stran výsledku
8
Strana od-do
105-112
Název nakladatele
NEUVEDEN
Místo vydání
Mikulov
Místo konání akce
Mikulov
Datum konání akce
27. 10. 2006
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—