On Parallel Communicating Grammar Systems and Correctness Preserving Restarting Automata

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F09%3A00206379" target="_blank" >RIV/00216208:11320/09:00206379 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

On Parallel Communicating Grammar Systems and Correctness Preserving Restarting Automata

Popis výsledku v původním jazyce

This paper contributes to the study of Freely Rewriting Restarting Automata (FRR-automata) and Parallel Communicating Grammar Systems (PCGS) as formalizations of the linguistic method of analysis by reduction. For PCGS we study two complexity measures called generation complexity and distribution complexity, and we prove that a PCGS Pi, for which both these complexity measures are bounded by constants, can be simulated by a freely rewriting restarting automaton of a very restricted form. From this, characterization it follows that the language L(Pi) is semi- linear, that its characteristic analysis is of polynomial size, and that this analysis can be computed in polynomial time

Název v anglickém jazyce

On Parallel Communicating Grammar Systems and Correctness Preserving Restarting Automata

Popis výsledku anglicky

This paper contributes to the study of Freely Rewriting Restarting Automata (FRR-automata) and Parallel Communicating Grammar Systems (PCGS) as formalizations of the linguistic method of analysis by reduction. For PCGS we study two complexity measures called generation complexity and distribution complexity, and we prove that a PCGS Pi, for which both these complexity measures are bounded by constants, can be simulated by a freely rewriting restarting automaton of a very restricted form. From this, characterization it follows that the language L(Pi) is semi- linear, that its characteristic analysis is of polynomial size, and that this analysis can be computed in polynomial time

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

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)

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ů

Název statě ve sborníku

LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS - THIRD INTERNATIONAL CONFERENCE, LATA 2009

ISBN

978-3-642-00981-5

ISSN

—

e-ISSN

—

Počet stran výsledku

12

Strana od-do

—

Název nakladatele

Springer Verlag

Místo vydání

Berlin

Místo konání akce

Berlin

Datum konání akce

1. 1. 2009

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000265784300056