Nothing Special   »   [go: up one dir, main page]

skip to main content
10.5555/2018285.2018299guideproceedingsArticle/Chapter ViewAbstractPublication PagesConference Proceedingsacm-pubtype
Article

Using bisimulations for optimality problems in model refinement

Published: 30 May 2011 Publication History

Abstract

A known generic strategy for handling large transition systems is the combined use of bisimulations and refinement. The idea is to reduce a large system by means of a bisimulation quotient into a smaller one, then to refine the smaller one in such way that it fulfils a desired property, and then to expand this refined system back into a submodel of the original one. This generic algorithm is not guaranteed to work correctly for every desired property; here we show its correctness for a class of optimality problems which can be described in the framework of dioids.

References

[1]
Ahuja, R.K., Magnati, T.L., Orlin, J.B.: Network Flows. Prentice-Hall, Englewood Cliffs (1993)
[2]
Baier, C., Katoen, J.-P.: Principles of Model Checking. MIT Press, Cambridge (2008)
[3]
Billings, J.N., Griffin, T.G.: A model of internet routing using semi-modules. In: Berghammer, R., Jaoua, A.M., Möller, B. (eds.) RelMiCS 2009. LNCS, vol. 5827, pp. 29-43. Springer, Heidelberg (2009)
[4]
Esparza, J., Kiefer, S., Luttenberger, M.: Derivation tree analysis for accelerated fixed-point computation. In: Ito, M., Toyama, M. (eds.) DLT 2008. LNCS, vol. 5257, pp. 301-313. Springer, Heidelberg (2008)
[5]
Glück, R., Möller, B., Sintzoff, M.: A semiring approach to equivalences, bisimulations and control. In: Berghammer, R., Jaoua, A.M., Möller, B. (eds.) RelMiCS 2009. LNCS, vol. 5827, pp. 134-149. Springer, Heidelberg (2009)
[6]
Glück, R., Möller, B., Sintzoff, M.: Model refinement using bisimulation quotients. In: Johnson, M., Pavlovic, D. (eds.) AMAST 2010. LNCS, vol. 6486, pp. 76-91. Springer, Heidelberg (2011)
[7]
Gondran, M., Minoux, M.: Graphs, Dioids and Semirings. Springer, Heidelberg (2008)
[8]
Höfner, P., Struth, G.: Automated reasoning in kleene algebra. In: Pfenning, F. (ed.) CADE 2007. LNCS (LNAI), vol. 4603, pp. 279-294. Springer, Heidelberg (2007)
[9]
Jungnickel, D.: Graphs, Networks and Algorithms, 2nd edn. Springer, Heidelberg (2005)
[10]
Kawahara, Y.: On the cardinality of relations. In: Schmidt, R.A. (ed.) RelMiCS/AKA 2006. LNCS, vol. 4136, pp. 251-265. Springer, Heidelberg (2006)
[11]
Myhill, J.: Finite automata and the representation of events. WADD TR-57-624, 112-137 (1957)
[12]
Nerode, A.: Linear automaton transformations. Proceedings of the American Mathematical Society 9, 541-544 (1958)
[13]
Paige, R., Tarjan, R.: Three partition refinement algorithms. SIAM Journal for Computing 16(6)
[14]
Sintzoff, M.: Synthesis of optimal control policies for some infinite-state transition systems. In: Audebaud, P., Paulin-Mohring, C. (eds.) MPC 2008. LNCS, vol. 5133, pp. 336-359. Springer, Heidelberg (2008)
[15]
Winter, M.: A relation-algebraic theory of bisimulations. Fundam. Inf. 83(4), 429-449 (2008)

Cited By

View all
  • (2012)Two observations in dioid based model refinementProceedings of the 13th international conference on Relational and Algebraic Methods in Computer Science10.1007/978-3-642-33314-9_16(235-247)Online publication date: 17-Sep-2012

Index Terms

  1. Using bisimulations for optimality problems in model refinement
    Index terms have been assigned to the content through auto-classification.

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image Guide Proceedings
    RAMICS'11: Proceedings of the 12th international conference on Relational and algebraic methods in computer science
    May 2011
    361 pages
    ISBN:9783642210693
    • Editor:
    • Harrie de Swart

    Sponsors

    • Erasmus University: Erasmus University
    • ESF: European Science Foundation
    • ERASMUS TRUST FUND: Erasmus Trust Fund

    Publisher

    Springer-Verlag

    Berlin, Heidelberg

    Publication History

    Published: 30 May 2011

    Qualifiers

    • Article

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)0
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 26 Sep 2024

    Other Metrics

    Citations

    Cited By

    View all
    • (2012)Two observations in dioid based model refinementProceedings of the 13th international conference on Relational and Algebraic Methods in Computer Science10.1007/978-3-642-33314-9_16(235-247)Online publication date: 17-Sep-2012

    View Options

    View options

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media