Skip to main content
Springer Nature Link
Log in

On the Expressiveness of Refinement Settings

  • Conference paper
Fundamentals of Software Engineering (FSEN 2009)

Part of the book series: Lecture Notes in Computer Science ((LNPSE,volume 5961))

Included in the following conference series:

  • 491 Accesses

Abstract

Embedded-systems designers often use transition system-based notations for specifying, with respect to some refinement preorder, sets of deterministic implementations. This paper compares popular such refinement settings — ranging from transition systems equipped with failure-pair inclusion to disjunctive modal transition systems — regarding the sets of implementations they are able to express. The paper’s main result is an expressiveness hierarchy, as well as language-preserving transformations between various settings. In addition to system designers, the main beneficiaries of this work are tool builders who wish to reuse refinement checkers or model checkers across different settings.

Research support provided by DFG (FE 942/2-1, RO 1122/12-2), EPSRC (EP/E034853/1) and MEC (TIN2006-15660-C02-01, TIN2006-15578-C02-01).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Baeten, J., Bergstra, J., Klop, J.: Ready-trace semantics for concrete process algebra with the priority operator. Computer J. 30(6), 498–506 (1987)

    MATH  MathSciNet  Google Scholar 

  2. Bloom, B., Istrail, S., Meyer, A.: Bisimulation can’t be traced. J. ACM 42(1), 232–268 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  3. Boudol, G., Larsen, K.G.: Graphical vs. logical specifications. Theoretical Computer Science 106(1), 3–20 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  4. Brookes, S., Hoare, C., Roscoe, A.: A theory of communicating sequential processes. J. ACM 31(3), 560–599 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  5. Cleaveland, R., Hennessy, M.: Testing equivalence as a bisimulation equivalence. Formal Aspects of Computing 5(1), 1–20 (1993)

    Article  MATH  Google Scholar 

  6. Cleaveland, R., Sokolsky, O.: Equivalence and preorder checking for finite-state systems. In: Handbook of Process Algebra, pp. 391–424. North-Holland, Amsterdam (2001)

    Chapter  Google Scholar 

  7. Dams, D., Gerth, R., Grumberg, O.: Abstract interpretation of reactive systems. ACM TOPLAS 19(2), 253–291 (1997)

    Article  Google Scholar 

  8. Dams, D., Namjoshi, K.S.: The existence of finite abstractions for branching time model checking. In: LICS, pp. 335–344. IEEE, Los Alamitos (2004)

    Google Scholar 

  9. Dams, D., Namjoshi, K.S.: Automata as abstractions. In: Cousot, R. (ed.) VMCAI 2005. LNCS, vol. 3385, pp. 216–232. Springer, Heidelberg (2005)

    Google Scholar 

  10. Engelfriet, J.: Determinacy → (observation equivalence = trace equivalence). Theoretical Computer Science 36, 21–25 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  11. Eshuis, R., Fokkinga, M.M.: Comparing refinements for failure and bisimulation semantics. Fundam. Inf. 52(4), 297–321 (2002)

    MATH  MathSciNet  Google Scholar 

  12. Fecher, H., Grabe, I.: Finite abstract models for deterministic transition systems: Fair parallel composition and refinement-preserving logic. In: Arbab, F., Sirjani, M. (eds.) FSEN 2007. LNCS, vol. 4767, pp. 1–16. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  13. Fecher, H., Huth, M.: Ranked predicate abstraction for branching time: Complete, incremental, and precise. In: Graf, S., Zhang, W. (eds.) ATVA 2006. LNCS, vol. 4218, pp. 322–336. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  14. Fecher, H., Huth, M., Schmidt, H., Schönborn, J.: Refinement sensitive formal semantics of state machines with persistent choice. In: AVoCS. ENTCS (2007) (to appear)

    Google Scholar 

  15. Fecher, H., Schmidt, H.: Comparing disjunctive modal transition systems with an one-selecting variant. J. Logic and Algebraic Programming 77, 20–39 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  16. Fecher, H., Steffen, M.: Characteristic μ-calculus formula for an underspecified transition system. In: EXPRESS 2004. ENTCS, vol. 128, pp. 103–116 (2005)

    Google Scholar 

  17. Glabbeek, R.v.: The linear time–branching time spectrum I. The semantics of concrete, sequential processes. In: Handbook of Process Algebra, pp. 3–99. North-Holland, Amsterdam (2001)

    Chapter  Google Scholar 

  18. Godefroid, P., Jagadeesan, R.: On the expressiveness of 3-valued models. In: Zuck, L.D., Attie, P.C., Cortesi, A., Mukhopadhyay, S. (eds.) VMCAI 2003. LNCS, vol. 2575, pp. 206–222. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  19. Grädel, E., Thomas, W., Wilke, T. (eds.): Automata, Logics, and Infinite Games. LNCS, vol. 2500. Springer, Heidelberg (2002)

    MATH  Google Scholar 

  20. Hennessy, M., Milner, R.: Algebraic laws for nondeterminism and concurrency. J. ACM 32(1), 137–161 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  21. Hussain, A., Huth, M.: Automata games for multiple-model checking. ENTCS 155, 401–421 (2006)

    Google Scholar 

  22. Janin, D., Walukiewicz, I.: Automata for the modal mu-calculus and related results. In: Hájek, P., Wiedermann, J. (eds.) MFCS 1995. LNCS, vol. 969, pp. 552–562. Springer, Heidelberg (1995)

    Google Scholar 

  23. Larsen, K.G., Nyman, U., Wasowski, A.: On modal refinement and consistency. In: Caires, L., Vasconcelos, V.T. (eds.) CONCUR 2007. LNCS, vol. 4703, pp. 105–119. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  24. Larsen, K.G., Skou, A.: Bisimulation through probabilistic testing. Inf. Comput. 94(1), 1–28 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  25. Larsen, K.G., Thomsen, B.: A modal process logic. In: LICS, pp. 203–210. IEEE, Los Alamitos (1988)

    Google Scholar 

  26. Larsen, K.G., Xinxin, L.: Equation solving using modal transition systems. In: LICS, pp. 108–117. IEEE, Los Alamitos (1990)

    Google Scholar 

  27. Olderog, E., Hoare, C.: Specification-oriented semantics for communicating processes. Acta Informatica 23(1), 9–66 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  28. Park, D.: Concurrency and automata on infinite sequences. In: Deussen, P. (ed.) GI-TCS 1981. LNCS, vol. 104, pp. 167–183. Springer, Heidelberg (1981)

    Chapter  Google Scholar 

  29. Phillips, I.: Refusal testing. Theoretical Computer Science 50(3), 241–284 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  30. Shoham, S., Grumberg, O.: 3-valued abstraction: More precision at less cost. In: LICS, pp. 399–410. IEEE, Los Alamitos (2006)

    Google Scholar 

  31. Shukla, S., Hunt, H., Rosenkrantz, D., Stearns, R.: On the complexity of relational problems for finite state processes. In: Meyer auf der Heide, F., Monien, B. (eds.) ICALP 1996. LNCS, vol. 1099, pp. 466–477. Springer, Heidelberg (1996)

    Google Scholar 

  32. Veglioni, S., de Nicola, R.: Possible worlds for process algebras. In: Sangiorgi, D., de Simone, R. (eds.) CONCUR 1998. LNCS, vol. 1466, pp. 179–193. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Albert-Ludwigs-Universität Freiburg, Germany

    Harald Fecher

  2. Universidad Complutense Madrid, Spain

    David de Frutos-Escrig

  3. University of York, U.K.

    Gerald Lüttgen

  4. Christian-Albrechts-Universität Kiel, Germany

    Heiko Schmidt

Authors
  1. Harald Fecher
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. David de Frutos-Escrig
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Gerald Lüttgen
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Heiko Schmidt
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Center for Mathematics and Computer Science (CWI), Science Park 123, 1098 XG, Amsterdam, The Netherlands

    Farhad Arbab

  2. Reykjavik University, School of Computer Science, Kringlan 1, 103, Reykjavik, Iceland

    Marjan Sirjani

Rights and permissions

Reprints and permissions

Copyright information

© 2010 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Fecher, H., de Frutos-Escrig, D., Lüttgen, G., Schmidt, H. (2010). On the Expressiveness of Refinement Settings. In: Arbab, F., Sirjani, M. (eds) Fundamentals of Software Engineering. FSEN 2009. Lecture Notes in Computer Science, vol 5961. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11623-0_16

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-11623-0_16

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-11622-3

  • Online ISBN: 978-3-642-11623-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation

  NODES
INTERN 1
Note 2