Galois Connections for Flow Algebras

Piotr Filipiuk, Michal Tomasz Terepeta, Hanne Riis Nielson, Flemming Nielson

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

    Abstract

    We generalise Galois connections from complete lattices to flow algebras. Flow algebras are algebraic structures that are less restrictive than idempotent semirings in that they replace distributivity with monotonicity and dispense with the annihilation property; therefore they are closer to the approach taken by Monotone Frameworks and other classical analyses. We present a generic framework for static analysis based on flow algebras and program graphs. Program graphs are often used in Model Checking to model concurrent and distributed systems. The framework allows to induce new flow algebras using Galois connections such that correctness of the analyses is preserved. The approach is illustrated for a mutual exclusion algorithm.
    Original languageEnglish
    Title of host publicationFormal Techniques for Distributed Systems : Joint 13th IFIP WG 6.1 International Conference, FMOODS 2011 and 30th IFIP WG 6.1 International Conference, FORTE 2011 Reykjavik, Iceland, June 6-9, 2011 Proceedings
    PublisherSpringer
    Publication date2011
    Pages138-152
    ISBN (Print)978-3-642-21460-8
    ISBN (Electronic)978-3-642-21461-5
    DOIs
    Publication statusPublished - 2011
    EventIFIP International Conference on Formal Methods for Open Object-based Distributed Systems & IFIP International Conference on FORmal TEchniques for Networked and Distributed Systems - Reykjavik, Iceland
    Duration: 1 Jan 2011 → …
    Conference number: 13 & 31

    Conference

    ConferenceIFIP International Conference on Formal Methods for Open Object-based Distributed Systems & IFIP International Conference on FORmal TEchniques for Networked and Distributed Systems
    Number13 & 31
    CityReykjavik, Iceland
    Period01/01/2011 → …
    SeriesLecture Notes in Computer Science
    Number6722
    ISSN0302-9743

    Cite this

    Filipiuk, P., Terepeta, M. T., Nielson, H. R., & Nielson, F. (2011). Galois Connections for Flow Algebras. In Formal Techniques for Distributed Systems: Joint 13th IFIP WG 6.1 International Conference, FMOODS 2011 and 30th IFIP WG 6.1 International Conference, FORTE 2011 Reykjavik, Iceland, June 6-9, 2011 Proceedings (pp. 138-152). Springer. Lecture Notes in Computer Science, No. 6722 https://doi.org/10.1007/978-3-642-21461-5