On Parallel Communicating Grammar Systems and Correctness Preserving Restarting Automata

Result code in 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>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
On Parallel Communicating Grammar Systems and Correctness Preserving Restarting Automata
Original language description
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
Czech name
—
Czech description
—

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2009
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS - THIRD INTERNATIONAL CONFERENCE, LATA 2009
ISBN
978-3-642-00981-5
ISSN
—
e-ISSN
—
Number of pages
12
Pages from-to
—
Publisher name
Springer Verlag
Place of publication
Berlin
Event location
Berlin
Event date
Jan 1, 2009
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000265784300056

Similar results(10)