Modal Process Rewrite Systems

Investor logo

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

BENEŠ Nikola KŘETÍNSKÝ Jan

Year of publication 2012
Type Article in Proceedings
Conference Theoretical Aspects of Computing - ICTAC 2012
MU Faculty or unit

Faculty of Informatics

Citation
Doi http://dx.doi.org/10.1007/978-3-642-32943-2_9
Field Informatics
Keywords modal transition systems; rewriting; infinite state systems
Attached files
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.