Galois Connections for Flow Algebras
International audience 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 the...
Main Authors: | , , , |
---|---|
Other Authors: | , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2011
|
Subjects: | |
Online Access: | https://hal.inria.fr/hal-01583315 https://hal.inria.fr/hal-01583315/document https://hal.inria.fr/hal-01583315/file/978-3-642-21461-5_9_Chapter.pdf https://doi.org/10.1007/978-3-642-21461-5_9 |
id |
ftifiphal:oai:HAL:hal-01583315v1 |
---|---|
record_format |
openpolar |
spelling |
ftifiphal:oai:HAL:hal-01583315v1 2023-05-15T16:48:56+02:00 Galois Connections for Flow Algebras Filipiuk, Piotr Terepeta, Michał Nielson, Hanne, Nielson, Flemming Danmarks Tekniske Universitet = Technical University of Denmark (DTU) Roberto Bruni Juergen Dingel TC 6 WG 6.1 Reykjavik,, Iceland 2011-06-06 https://hal.inria.fr/hal-01583315 https://hal.inria.fr/hal-01583315/document https://hal.inria.fr/hal-01583315/file/978-3-642-21461-5_9_Chapter.pdf https://doi.org/10.1007/978-3-642-21461-5_9 en eng HAL CCSD Springer info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-642-21461-5_9 hal-01583315 https://hal.inria.fr/hal-01583315 https://hal.inria.fr/hal-01583315/document https://hal.inria.fr/hal-01583315/file/978-3-642-21461-5_9_Chapter.pdf doi:10.1007/978-3-642-21461-5_9 http://creativecommons.org/licenses/by/ info:eu-repo/semantics/OpenAccess Lecture Notes in Computer Science 13th Conference on Formal Methods for Open Object-Based Distributed Systems (FMOODS) / 31th International Conference on FORmal TEchniques for Networked and Distributed Systems (FORTE) https://hal.inria.fr/hal-01583315 13th Conference on Formal Methods for Open Object-Based Distributed Systems (FMOODS) / 31th International Conference on FORmal TEchniques for Networked and Distributed Systems (FORTE), Jun 2011, Reykjavik,, Iceland. pp.138-152, ⟨10.1007/978-3-642-21461-5_9⟩ [INFO]Computer Science [cs] [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] info:eu-repo/semantics/conferenceObject Conference papers 2011 ftifiphal https://doi.org/10.1007/978-3-642-21461-5_9 2023-03-21T20:40:06Z International audience 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. Conference Object Iceland IFIP Open Digital Library (International Federation for Information Processing) 138 152 |
institution |
Open Polar |
collection |
IFIP Open Digital Library (International Federation for Information Processing) |
op_collection_id |
ftifiphal |
language |
English |
topic |
[INFO]Computer Science [cs] [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] |
spellingShingle |
[INFO]Computer Science [cs] [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] Filipiuk, Piotr Terepeta, Michał Nielson, Hanne, Nielson, Flemming Galois Connections for Flow Algebras |
topic_facet |
[INFO]Computer Science [cs] [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] |
description |
International audience 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. |
author2 |
Danmarks Tekniske Universitet = Technical University of Denmark (DTU) Roberto Bruni Juergen Dingel TC 6 WG 6.1 |
format |
Conference Object |
author |
Filipiuk, Piotr Terepeta, Michał Nielson, Hanne, Nielson, Flemming |
author_facet |
Filipiuk, Piotr Terepeta, Michał Nielson, Hanne, Nielson, Flemming |
author_sort |
Filipiuk, Piotr |
title |
Galois Connections for Flow Algebras |
title_short |
Galois Connections for Flow Algebras |
title_full |
Galois Connections for Flow Algebras |
title_fullStr |
Galois Connections for Flow Algebras |
title_full_unstemmed |
Galois Connections for Flow Algebras |
title_sort |
galois connections for flow algebras |
publisher |
HAL CCSD |
publishDate |
2011 |
url |
https://hal.inria.fr/hal-01583315 https://hal.inria.fr/hal-01583315/document https://hal.inria.fr/hal-01583315/file/978-3-642-21461-5_9_Chapter.pdf https://doi.org/10.1007/978-3-642-21461-5_9 |
op_coverage |
Reykjavik,, Iceland |
genre |
Iceland |
genre_facet |
Iceland |
op_source |
Lecture Notes in Computer Science 13th Conference on Formal Methods for Open Object-Based Distributed Systems (FMOODS) / 31th International Conference on FORmal TEchniques for Networked and Distributed Systems (FORTE) https://hal.inria.fr/hal-01583315 13th Conference on Formal Methods for Open Object-Based Distributed Systems (FMOODS) / 31th International Conference on FORmal TEchniques for Networked and Distributed Systems (FORTE), Jun 2011, Reykjavik,, Iceland. pp.138-152, ⟨10.1007/978-3-642-21461-5_9⟩ |
op_relation |
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-642-21461-5_9 hal-01583315 https://hal.inria.fr/hal-01583315 https://hal.inria.fr/hal-01583315/document https://hal.inria.fr/hal-01583315/file/978-3-642-21461-5_9_Chapter.pdf doi:10.1007/978-3-642-21461-5_9 |
op_rights |
http://creativecommons.org/licenses/by/ info:eu-repo/semantics/OpenAccess |
op_doi |
https://doi.org/10.1007/978-3-642-21461-5_9 |
container_start_page |
138 |
op_container_end_page |
152 |
_version_ |
1766039020715900928 |