Parallel communicating grammar systems with regular control and skeleton preserving FRR automata

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F11%3A10104984" target="_blank" >RIV/00216208:11320/11:10104984 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.tcs.2010.10.017" target="_blank" >http://dx.doi.org/10.1016/j.tcs.2010.10.017</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.tcs.2010.10.017" target="_blank" >10.1016/j.tcs.2010.10.017</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Parallel communicating grammar systems with regular control and skeleton preserving FRR automata

Popis výsledku v původním jazyce

Parallel communicating grammar systems with regular control (RPCGS, for short) are introduced, which are obtained from returning regular parallel communicating grammar systems by restricting the derivations that are executed in parallel by the various components through a regular control language. For the class of languages that are generated by RPCGSs with constant communication complexity we derive a characterisation in terms of a restricted type of freely rewriting restarting automaton. From this characterisation we obtain that these languages are semi-linear, and that for RPCGSs with constant communication complexity, the centralised variant has the same generative power as the non-centralised variant.

Název v anglickém jazyce

Parallel communicating grammar systems with regular control and skeleton preserving FRR automata

Popis výsledku anglicky

Parallel communicating grammar systems with regular control (RPCGS, for short) are introduced, which are obtained from returning regular parallel communicating grammar systems by restricting the derivations that are executed in parallel by the various components through a regular control language. For the class of languages that are generated by RPCGSs with constant communication complexity we derive a characterisation in terms of a restricted type of freely rewriting restarting automaton. From this characterisation we obtain that these languages are semi-linear, and that for RPCGSs with constant communication complexity, the centralised variant has the same generative power as the non-centralised variant.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

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í

2011

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 periodika

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

—

Svazek periodika

412

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

19

Strana od-do

458-477

Kód UT WoS článku

000286862100017

EID výsledku v databázi Scopus

—