Dvousměrné lineární PC gramatické systémy a jejich popisná složitost
Popis výsledku
Kromě derivačních a komunikačních kroků dvousměrný PC gramatický systém vykonává také krok redukční, během kterého se nahrazuje pravá strana bezkontextového pravidla stranou levou. Článek dokazuje, že každý neunární rekurzivně spočetný jazyk může být popsán úsporným způsobem centralizovaným dvousměrným PC gramatickým systémem, Γ, s pěti komponentami. Přičemž hlavní komponenta obsahuje pouze tři nontermilány a jediné pravidlo obsahující komunikační symbol. Dále Γ během každého výpočtu pprovede jediný komunikační krok a všechny větné formy obsahují maximálně dva výskyty nonterminálních symbolů.
Klíčová slova
Context-free grammarleft-linear grammarright-linear grammargrammar systemcommunication steptwo-way PC grammar systemsderivationproductionsentential formnonterminalterminal
Identifikátory výsledku
Kód výsledku v IS VaVaI
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Two-Way Linear PC Grammar Systems and Their Descriptional Complexity
Popis výsledku v původním jazyce
Besides derivation and communication steps, a two-way PC grammar system can make a reduction step during which it reduces the right-hand side of a context-free production to its left hand-side. This paper proves that every non-unary recursively enumerable language is defined by a centralized two-way grammar system, Γ, with five components in a very economical way. Indeed, Γ's master has only three nonterminals and one communication production; furthermore, it produces all sentential foorms with no more than two occurrences of nonterminals. In addition, during every computation, Γ makes a single communication step.
Název v anglickém jazyce
Two-Way Linear PC Grammar Systems and Their Descriptional Complexity
Popis výsledku anglicky
Besides derivation and communication steps, a two-way PC grammar system can make a reduction step during which it reduces the right-hand side of a context-free production to its left hand-side. This paper proves that every non-unary recursively enumerable language is defined by a centralized two-way grammar system, Γ, with five components in a very economical way. Indeed, Γ's master has only three nonterminals and one communication production; furthermore, it produces all sentential foorms with no more than two occurrences of nonterminals. In addition, during every computation, Γ makes a single communication step.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
JC - Počítačový hardware a software
OECD FORD obor
—
Návaznosti výsledku
Projekt
GA201/04/0441: Vhodně sloučené modely pro moderní informační technologie
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2005
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
Proceedings of the 11th Conference Student EEICT 2005
ISBN
80-214-2890-2
ISSN
—
e-ISSN
—
Počet stran výsledku
5
Strana od-do
546-550
Název nakladatele
Publishing house of Brno University of Technology VUTIUM
Místo vydání
Brno
Místo konání akce
Brno
Datum konání akce
28. 4. 2005
Typ akce podle státní příslušnosti
CST - Celostátní akce
Kód UT WoS článku
—
Základní informace
Druh výsledku
D - Stať ve sborníku
CEP
JC - Počítačový hardware a software
Rok uplatnění
2005