2012
Modal Process Rewrite Systems
BENEŠ, Nikola a Jan KŘETÍNSKÝZákladní údaje
Originální název
Modal Process Rewrite Systems
Autoři
BENEŠ, Nikola (203 Česká republika, domácí) a Jan KŘETÍNSKÝ (203 Česká republika, garant, domácí)
Vydání
Berlin Heidelberg, Theoretical Aspects of Computing - ICTAC 2012, od s. 120-135, 16 s. 2012
Nakladatel
Springer
Další údaje
Jazyk
angličtina
Typ výsledku
Stať ve sborníku
Obor
10201 Computer sciences, information science, bioinformatics
Stát vydavatele
Německo
Utajení
není předmětem státního či obchodního tajemství
Forma vydání
tištěná verze "print"
Impakt faktor
Impact factor: 0.402 v roce 2005
Kód RIV
RIV/00216224:14330/12:00057564
Organizační jednotka
Fakulta informatiky
ISBN
978-3-642-32942-5
ISSN
Klíčová slova anglicky
modal transition systems; rewriting; infinite state systems
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 24. 10. 2013 16:17, RNDr. Nikola Beneš, Ph.D.
Anotace
V originále
We consider modal transition systems with infinite state space generated by finite sets of rules. In particular, we extend process rewrite systems to the modal setting and investigate decidability of the modal refinement relation between systems from various subclasses. Since already simulation is undecidable for most of the cases, we focus on the case where either the refined or the refining process is finite. Namely, we show decidability for pushdown automata extending the non-modal case and surprising undecidability for basic parallel processes. Further, we prove decidability when both systems are visibly pushdown automata. For the decidable cases, we also provide complexities. Finally, we discuss a notion of bisimulation over MTS.
Návaznosti
| GAP202/11/0312, projekt VaV |
| ||
| MUNI/A/0914/2009, interní kód MU |
|