Paper Info
Title
Reachability of hennessy-milner properties for weakly extended PRS
Abstract
We examine the problem whether a given weakly extended process rewrite system (wPRS) contains a reachable state satisfying a given formula of Hennessy–Milner logic. We show that this problem is decidable. As a corollary we observe that the problem of strong bisimilarity between wPRS and finite-state systems is decidable. Decidability of the same problem for wPRS subclasses, namely PAN and PRS, has been formulated as an open question, see e.g. [Srb02]. We also strengthen some related undecidability results on some PRS subclasses.
Year
DOI
Venue
2005
10.1007/11590156_17
FSTTCS
Keywords
Field
DocType
reachability,satisfiability
Discrete mathematics,Combinatorics,Finite-state machine,Reachability,Decidability,Corollary,Mathematics
Conference
Volume
ISSN
ISBN
3821
0302-9743
3-540-30495-9
Citations 
PageRank 
References 
6
0.41
22
Authors
3
Name
Order
Citations
PageRank
Mojmír Křetínský1563.62
Vojtěch Řehák2685.99
Jan Strejcek39913.83