BENEŠ, Nikola and Jan KŘETÍNSKÝ. Modal Process Rewrite Systems. In Theoretical Aspects of Computing - ICTAC 2012. Berlin Heidelberg: Springer, 2012. p. 120-135. ISBN 978-3-642-32942-5. doi:10.1007/978-3-642-32943-2_9.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Modal Process Rewrite Systems
Authors BENEŠ, Nikola (203 Czech Republic, belonging to the institution) and Jan KŘETÍNSKÝ (203 Czech Republic, guarantor, belonging to the institution).
Edition Berlin Heidelberg, Theoretical Aspects of Computing - ICTAC 2012, p. 120-135, 16 pp. 2012.
Publisher Springer
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Germany
Confidentiality degree is not subject to a state or trade secret
Publication form printed version "print"
Impact factor Impact factor: 0.402 in 2005
RIV identification code RIV/00216224:14330/12:00057564
Organization unit Faculty of Informatics
ISBN 978-3-642-32942-5
ISSN 0302-9743
Doi http://dx.doi.org/10.1007/978-3-642-32943-2_9
Keywords in English modal transition systems; rewriting; infinite state systems
Tags International impact, Reviewed
Changed by Changed by: RNDr. Nikola Beneš, Ph.D., učo 72525. Changed: 24. 10. 2013 16:17.
Abstract
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.
Links
GAP202/11/0312, research and development projectName: Vývoj a verifikace softwarových komponent v zapouzdřených systémech (Acronym: Components in Embedded Systems)
Investor: Czech Science Foundation
MUNI/A/0914/2009, interní kód MUName: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace (Acronym: SV-FI MAV)
Investor: Masaryk University, Category A
PrintDisplayed: 12. 8. 2022 16:55