Abstract
We present a general framework for the synthesis of the constraints under which the selected properties hold in a class of models with discrete transitions, together with Boolean encoding - based method of implementing the theory. We introduce notions of parametric image and preimage, and show how to use them to build fixed-point algorithms for parametric model checking of reachability and deadlock freedom. An outline of how the ideas shown in this paper were specialized for an extension of Computation Tree Logic is given together with some experimental results.
Work partially funded by DEC − 2012/07/N/ST6/03426 NCN Preludium grant.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alur, R., Etessami, K., Torre, S.L., Peled, D.: Parametric Temporal Logic for “Model Measuring”. ACM Trans. Comput. Log. 2(3), 388–407 (2001)
Alur, R., Henzinger, T., Vardi, M.: Parametric real-time reasoning. In: Proc. of the 25th Ann. Symp. on Theory of Computing (STOC 1993), pp. 592–601. ACM (1993)
Belardinelli, F., Jones, A.V., Lomuscio, A.: Model checking temporal-epistemic logic using alternating tree automata. Fundam. Inform. 112(1), 19–37 (2011)
Bozzelli, L., La Torre, S.: Decision problems for lower/upper bound parametric timed automata. Form. Methods Syst. Des. 35(2), 121–151 (2009)
Bruyère, V., Dall’Olio, E., Raskin, J.F.: Durations, parametric model-checking in timed automata with presburger arithmetic. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 687–698. Springer, Heidelberg (2003)
Burch, J.R., Clarke, E., McMillan, K.L., Dill, D.L., Hwang, L.J.: Symbolic model checking: 1020 states and beyond. Information and Computation 98(2), 142–170 (1990)
Clarke, E.M.: The birth of model checking. In: Grumberg, O., Veith, H. (eds.) 25 Years of Model Checking. LNCS, vol. 5000, pp. 1–26. Springer, Heidelberg (2008)
Classen, A., Heymans, P., Schobbens, P.Y., Legay, A.: Symbolic model checking of software product lines. In: Proc. of the 33rd Int. Conf. on Software Engineering, ICSE 2011, pp. 321–330. ACM, New York (2011)
Emerson, E.A., Trefler, R.: Parametric quantitative temporal reasoning. In: Proc. of the 14th Symp. on Logic in Computer Science (LICS 1999), pp. 336–343. IEEE Computer Society (July 1999)
Ghallab, M., Nau, D.S., Traverso, P.: Automated planning - theory and practice. Elsevier (2004)
Di Giampaolo, B., La Torre, S., Napoli, M.: Parametric metric interval temporal logic. In: Dediu, A.-H., Fernau, H., Martín-Vide, C. (eds.) LATA 2010. LNCS, vol. 6031, pp. 249–260. Springer, Heidelberg (2010)
Holzmann, G.J.: Protocol design: Redefining the state of the art. IEEE Software 9(1), 17–22 (1992)
Jensen, K., Donatelli, S., Koutny, M. (eds.): Transactions on Petri Nets and Other Models of Concurrency IV. LNCS, vol. 6550. Springer, Heidelberg (2010)
Jones, A.V., Knapik, M., Penczek, W., Lomuscio, A.: Parametric computation tree logic with knowledge. In: Proc. of the Int. Workshop on Concurrency, Specification and Programming (CS&P 2011), pp. 286–300. Białystok University of Technology (2011)
Knapik, M., https://michalknapik.github.io/spatula
Knapik, M., Penczek, W., Szreter, M., Pólrola, A.: Bounded parametric verification for distributed time Petri nets with discrete-time semantics. Fundam. Inform. 101(1-2), 9–27 (2010)
Knapik, M., Męski, A., Penczek, W.: Action synthesis for branching time logic: Theory and applications. In: Proc. of the 14th Int. Conf. on Application of Concurrency to System Design. IEEE Computer Society (to appear, 2014)
Knapik, M., Szreter, M., Penczek, W.: Bounded parametric model checking for elementary net systems. In: T. Petri Nets and Other Models of Concurrency [13], pp. 42–71
Lin, F.J., Chu, P.M., Liu, M.T.: Protocol verification using reachability analysis: The state space explosion problem and relief strategies. SIGCOMM Comput. Commun. Rev. 17(5), 126–135 (1987)
Pecheur, C., Raimondi, F.: Symbolic model checking of logics with actions. In: Edelkamp, S., Lomuscio, A. (eds.) MoChArt IV. LNCS (LNAI), vol. 4428, pp. 113–128. Springer, Heidelberg (2007)
Peled, D.: All From One, One For All: On Model Checking Using Representatives. In: Courcoubetis, C. (ed.) CAV 1993. LNCS, vol. 697, pp. 409–423. Springer, Heidelberg (1993)
Penczek, W., Pólrola, A., Zbrzezny, A.: Sat-based (parametric) reachability for a class of distributed time petri nets. In: T. Petri Nets and Other Models of Concurrency [13], pp. 72–97
Somenzi, F.: CUDD: CU decision diagram package - release 2.3.1., http://vlsi.colorado.edu/~fabio/CUDD/cuddIntro.html
Wang, F.: Parametric timing analysis for real-time systems. Inf. Comput. 130(2), 131–150 (1996)
Wang, F.: Parametric analysis of computer systems. Formal Methods in System Design 17(1), 39–60 (2000)
Xie, Y., Aiken, A.: Scalable error detection using boolean satisfiability. SIGPLAN Not. 40(1), 351–363 (2005)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Knapik, M., Penczek, W. (2015). Fixed-Point Methods in Parametric Model Checking. In: Angelov, P., et al. Intelligent Systems'2014. Advances in Intelligent Systems and Computing, vol 322. Springer, Cham. https://doi.org/10.1007/978-3-319-11313-5_22
Download citation
DOI: https://doi.org/10.1007/978-3-319-11313-5_22
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-11312-8
Online ISBN: 978-3-319-11313-5
eBook Packages: EngineeringEngineering (R0)