O PCGS a FRR-automatech
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F08%3A00101160" target="_blank" >RIV/00216208:11320/08:00101160 - 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
On PCGS and FRR-automata
Popis výsledku v původním jazyce
Abstract. This paper presents the second part of the technical report [7] in which the study of the relation between Parallel Communicating Grammar Systems (PCGS) and Freely Rewriting Restarting Automata (FRR) has been initiated. The first part of [7] ispresented in [6]. Here, the distribution and generation complexity for PCGS are introduced and studied. It is shown that analysis by reduction for PCGS with distribution complexity bounded by a constant k and generation complexity bounded by some otherconstant j can be implemented by strongly linearized deterministic FRR-automata with k rewrites per cycle. We show infinite hierarchies of classes of languages based on the parameters k; j and on the notion of skeleton.
Název v anglickém jazyce
On PCGS and FRR-automata
Popis výsledku anglicky
Abstract. This paper presents the second part of the technical report [7] in which the study of the relation between Parallel Communicating Grammar Systems (PCGS) and Freely Rewriting Restarting Automata (FRR) has been initiated. The first part of [7] ispresented in [6]. Here, the distribution and generation complexity for PCGS are introduced and studied. It is shown that analysis by reduction for PCGS with distribution complexity bounded by a constant k and generation complexity bounded by some otherconstant j can be implemented by strongly linearized deterministic FRR-automata with k rewrites per cycle. We show infinite hierarchies of classes of languages based on the parameters k; j and on the notion of skeleton.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
BA - Obecná matematika
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
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)
Ostatní
Rok uplatnění
2008
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
CEUR-workshop proceedings, ITAT 2008, Information Technologies - Applications and Theory
ISBN
978-80-969184-9-2
ISSN
—
e-ISSN
—
Počet stran výsledku
8
Strana od-do
—
Název nakladatele
Institute of computer science, Faculty of science, P. J. Šafárik university, Košice, Slovakia
Místo vydání
Košice
Místo konání akce
Košice
Datum konání akce
1. 1. 2008
Typ akce podle státní příslušnosti
EUR - Evropská akce
Kód UT WoS článku
—