Logotyp: till Uppsala universitets webbplats

uu.sePublikationer från Uppsala universitet
Ändra sökning
Länk till posten
Permanent länk

Direktlänk
Parrow, Joachim
Publikationer (10 of 54) Visa alla publikationer
Parrow, J., Borgström, J., Eriksson, L.-H., Forsberg Gutkovas, R. & Weber, T. (2021). Modal Logics for Nominal Transition Systems. Logical Methods in Computer Science, 17(1), Article ID 5353.
Öppna denna publikation i ny flik eller fönster >>Modal Logics for Nominal Transition Systems
Visa övriga...
2021 (Engelska)Ingår i: Logical Methods in Computer Science, E-ISSN 1860-5974, Vol. 17, nr 1, artikel-id 5353Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We define a general notion of transition system where states and action labels can be from arbitrary nominal sets, actions may bind names, and state predicates from an arbitrary logic define properties of states. A Hennessy-Milner logic for these systems is introduced, and proved adequate and expressively complete for bisimulation equivalence. A main technical novelty is the use of finitely supported infinite conjunctions. We show how to treat different bisimulation variants such as early, late, open and weak in a systematic way, explore the folklore theorem that state predicates can be replaced by actions, and make substantial comparisons with related work. The main definitions and theorems have been formalised in Nominal Isabelle.

Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
Datavetenskap
Identifikatorer
urn:nbn:se:uu:diva-383314 (URN)10.23638/LMCS-17(1:6)2021 (DOI)000658724600006 ()
Tillgänglig från: 2019-05-13 Skapad: 2019-05-13 Senast uppdaterad: 2024-07-04Bibliografiskt granskad
Parrow, J., Weber, T., Borgström, J. & Eriksson, L.-H. (2017). Weak Nominal Modal Logic. In: Formal Techniques for Distributed Objects, Components, and Systems: . Paper presented at FORTE 2017 (pp. 179-193). Springer
Öppna denna publikation i ny flik eller fönster >>Weak Nominal Modal Logic
2017 (Engelska)Ingår i: Formal Techniques for Distributed Objects, Components, and Systems, Springer, 2017, s. 179-193Konferensbidrag, Publicerat paper (Refereegranskat)
Ort, förlag, år, upplaga, sidor
Springer, 2017
Serie
Lecture Notes in Computer Science, ISSN 0302-9743 ; 10321
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
Datavetenskap
Identifikatorer
urn:nbn:se:uu:diva-334579 (URN)10.1007/978-3-319-60225-7_13 (DOI)978-3-319-60224-0 (ISBN)
Konferens
FORTE 2017
Forskningsfinansiär
Vetenskapsrådet, 2013-4853
Tillgänglig från: 2017-05-28 Skapad: 2017-11-24 Senast uppdaterad: 2018-01-19Bibliografiskt granskad
Borgström, J., Gutkovas, R., Parrow, J., Victor, B. & Åman Pohjola, J. (2016). A Sorted Semantic Framework for Applied Process Calculi. Logical Methods in Computer Science, 12(1), 1-49, Article ID 8.
Öppna denna publikation i ny flik eller fönster >>A Sorted Semantic Framework for Applied Process Calculi
Visa övriga...
2016 (Engelska)Ingår i: Logical Methods in Computer Science, E-ISSN 1860-5974, Vol. 12, nr 1, s. 1-49, artikel-id 8Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

Applied process calculi include advanced programming constructs such as type systems, communication with pattern matching, encryption primitives, concurrent constraints, nondeterminism, process creation, and dynamic connection topologies. Several such formalisms, e.g. the applied pi calculus, are extensions of the the pi-calculus; a growing number is geared towards particular applications or computational paradigms.

Our goal is a unified framework to represent different process calculi and notions of computation. To this end, we extend our previous work on psi-calculi with novel abstract patterns and pattern matching, and add sorts to the data term language, giving sufficient criteria for subject reduction to hold. Our framework can directly represent several existing process calculi; the resulting transition systems are isomorphic to the originals up to strong bisimulation. We also demonstrate different notions of computation on data terms, including cryptographic primitives and a lambda-calculus with erratic choice. Finally, we prove standard congruence and structural properties of bisimulation; the proof has been machine-checked using Nominal Isabelle in the case of a single name sort.

Nyckelord
Expressiveness, Pattern matching, Type systems, Theorem proving, pi-calculus, Nominal sets
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
Datavetenskap
Identifikatorer
urn:nbn:se:uu:diva-262199 (URN)10.2168/LMCS-12(1:8)2016 (DOI)000374769600004 ()
Projekt
UPMARC
Forskningsfinansiär
Vetenskapsrådet, 2013-4853
Tillgänglig från: 2016-03-31 Skapad: 2015-09-09 Senast uppdaterad: 2024-07-04Bibliografiskt granskad
Åman Pohjola, J. & Parrow, J. (2016). Bisimulation up-to techniques for psi-calculi. In: Avigad, J; Chlipala, A (Ed.), Proc. 5th ACM SIGPLAN Conference on Certified Programs and Proofs: . Paper presented at CPP 2016, January 18–19, Saint Petersburg, FL (pp. 142-153). New York: ACM Press
Öppna denna publikation i ny flik eller fönster >>Bisimulation up-to techniques for psi-calculi
2016 (Engelska)Ingår i: Proc. 5th ACM SIGPLAN Conference on Certified Programs and Proofs / [ed] Avigad, J; Chlipala, A, New York: ACM Press, 2016, s. 142-153Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

Psi-calculi is a parametric framework for process calculi similar to popular pi-calculus extensions such as the explicit fusion calculus, the applied pi-calculus and the spi calculus. Remarkably, machine-checked proofs of standard algebraic and congruence properties of bisimilarity apply to all calculi within the framework. Bisimulation up-to techniques are methods for reducing the size of relations needed in bisimulation proofs. In this paper, we show how these bisimulation proof methods can be adapted to psi-calculi. We formalise all our definitions and theorems in Nominal Isabelle, and show examples where the use of up to-techniques yields drastically simplified proofs of known results. We also prove new structural laws about the replication operator.

Ort, förlag, år, upplaga, sidor
New York: ACM Press, 2016
Nyckelord
Bisimulation up-to, process calculus, psi-calculi, Isabelle, Nominal Isabelle, nominal logic
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
urn:nbn:se:uu:diva-229008 (URN)10.1145/2854065.2854080 (DOI)000389021600016 ()9781450341271 (ISBN)
Konferens
CPP 2016, January 18–19, Saint Petersburg, FL
Tillgänglig från: 2016-01-18 Skapad: 2014-07-25 Senast uppdaterad: 2018-01-11Bibliografiskt granskad
Parrow, J. (2016). General conditions for full abstraction. Mathematical Structures in Computer Science, 26(4), 655-657
Öppna denna publikation i ny flik eller fönster >>General conditions for full abstraction
2016 (Engelska)Ingår i: Mathematical Structures in Computer Science, ISSN 0960-1295, E-ISSN 1469-8072, Vol. 26, nr 4, s. 655-657Artikel i tidskrift (Refereegranskat) Published
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
urn:nbn:se:uu:diva-300298 (URN)10.1017/S0960129514000280 (DOI)000374148200003 ()
Tillgänglig från: 2014-11-10 Skapad: 2016-08-08 Senast uppdaterad: 2018-01-10Bibliografiskt granskad
Weber, T., Eriksson, L.-H., Parrow, J., Borgström, J. & Gutkovas, R. (2016). Modal Logics for Nominal Transition Systems. Archive of Formal Proofs
Öppna denna publikation i ny flik eller fönster >>Modal Logics for Nominal Transition Systems
Visa övriga...
2016 (Engelska)Ingår i: Archive of Formal Proofs, ISSN 2150-914xArtikel i tidskrift (Refereegranskat) Published
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
urn:nbn:se:uu:diva-300027 (URN)
Projekt
UPMARC
Forskningsfinansiär
Vetenskapsrådet, 2013-4853
Tillgänglig från: 2016-10-25 Skapad: 2016-08-01 Senast uppdaterad: 2019-02-25
Bengtson, J., Parrow, J. & Weber, T. (2016). Psi-Calculi in Isabelle. Journal of automated reasoning, 56(1), 1-47
Öppna denna publikation i ny flik eller fönster >>Psi-Calculi in Isabelle
2016 (Engelska)Ingår i: Journal of automated reasoning, ISSN 0168-7433, E-ISSN 1573-0670, Vol. 56, nr 1, s. 1-47Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

This paper presents a mechanisation of psi-calculi, a parametric framework for modelling various dialects of process calculi including (but not limited to) the pi-calculus, the applied pi-calculus, and the spi calculus. psi-calculi are significantly more expressive, yet their semantics is as simple in structure as the semantics of the original pi-calculus. Proofs of meta-theoretic properties for psi-calculi are more involved, however, not least because psi-calculi (unlike simpler calculi) utilise binders that bind multiple names at once. The mechanisation is carried out in the Nominal Isabelle framework, an interactive proof assistant designed to facilitate formal reasoning about calculi with binders. Our main contributions are twofold. First, we have developed techniques that allow efficient reasoning about calculi that bind multiple names in Nominal Isabelle. Second, we have adopted these techniques to mechanise substantial results from the meta-theory of psi-calculi, including congruence properties of bisimilarity and the laws of structural congruence. To our knowledge, this is the most extensive formalisation of process calculi mechanised in a proof assistant to date.

Nyckelord
Psi-calculi, Process calculi, Proof assistants, Nominal logic, Mechanisation
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
urn:nbn:se:uu:diva-275571 (URN)10.1007/s10817-015-9336-2 (DOI)000367884100001 ()
Tillgänglig från: 2016-02-04 Skapad: 2016-02-04 Senast uppdaterad: 2018-01-10Bibliografiskt granskad
Åman Pohjola, J. & Parrow, J. (2016). The Expressive Power of Monotonic Parallel Composition. In: Programming Languages and Systems: . Paper presented at ESOP 2016, April 3–7, Eindhoven, The Netherlands (pp. 780-803). Berlin: Springer
Öppna denna publikation i ny flik eller fönster >>The Expressive Power of Monotonic Parallel Composition
2016 (Engelska)Ingår i: Programming Languages and Systems, Berlin: Springer, 2016, s. 780-803Konferensbidrag, Publicerat paper (Refereegranskat)
Ort, förlag, år, upplaga, sidor
Berlin: Springer, 2016
Serie
Lecture Notes in Computer Science, ISSN 0302-9743 ; 9632
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
urn:nbn:se:uu:diva-297465 (URN)10.1007/978-3-662-49498-1_30 (DOI)000401936100030 ()978-3-662-49497-4 (ISBN)
Konferens
ESOP 2016, April 3–7, Eindhoven, The Netherlands
Tillgänglig från: 2016-03-22 Skapad: 2016-06-23 Senast uppdaterad: 2018-01-10Bibliografiskt granskad
Borgström, J., Huang, S., Johansson, M., Raabjerg, P., Victor, B., Åman Pohjola, J. & Parrow, J. (2015). Broadcast psi-calculi with an application to wireless protocols. Software and Systems Modeling, 14(1), 201-216
Öppna denna publikation i ny flik eller fönster >>Broadcast psi-calculi with an application to wireless protocols
Visa övriga...
2015 (Engelska)Ingår i: Software and Systems Modeling, ISSN 1619-1366, E-ISSN 1619-1374, Vol. 14, nr 1, s. 201-216Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

Psi-calculi is a parametric framework for extensions of the pi-calculus, with arbitrary data structures and logical assertions for facts about data. In this paper we add primitives for broadcast communication in order to model wireless protocols. The additions preserve the purity of the psi-calculi semantics, and we formally prove the standard congruence and structural properties of bisimilarity. We demonstrate the expressive power of broadcast psi-calculi by modelling the wireless ad-hoc routing protocol LUNAR and verifying a basic reachability property.

Ort, förlag, år, upplaga, sidor
Springer, 2015
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
urn:nbn:se:uu:diva-205258 (URN)10.1007/s10270-013-0375-z (DOI)000349026100012 ()
Projekt
UPMARCProFuN
Forskningsfinansiär
Vetenskapsrådet, 2013-4853
Tillgänglig från: 2013-11-08 Skapad: 2013-08-15 Senast uppdaterad: 2024-01-17Bibliografiskt granskad
Parrow, J., Borgström, J., Eriksson, L.-H., Gutkovas, R. & Weber, T. (2015). Modal Logics for Nominal Transition Systems. In: 26th International Conference on Concurrency Theory: CONCUR 2015. Paper presented at CONCUR 2015, September 1–4, Madrid, Spain (pp. 198-211). Dagstuhl, Germany: Leibniz-Zentrum für Informatik
Öppna denna publikation i ny flik eller fönster >>Modal Logics for Nominal Transition Systems
Visa övriga...
2015 (Engelska)Ingår i: 26th International Conference on Concurrency Theory: CONCUR 2015, Dagstuhl, Germany: Leibniz-Zentrum für Informatik , 2015, s. 198-211Konferensbidrag, Publicerat paper (Refereegranskat)
Ort, förlag, år, upplaga, sidor
Dagstuhl, Germany: Leibniz-Zentrum für Informatik, 2015
Serie
Leibniz International Proceedings in Informatics (LIPIcs), ISSN 1868-8969 ; 42
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
urn:nbn:se:uu:diva-267935 (URN)10.4230/LIPIcs.CONCUR.2015.198 (DOI)978-3-939897-91-0 (ISBN)
Konferens
CONCUR 2015, September 1–4, Madrid, Spain
Projekt
UPMARC
Forskningsfinansiär
Vetenskapsrådet, 2014-5478Stiftelsen för strategisk forskning (SSF)
Tillgänglig från: 2015-12-14 Skapad: 2015-11-30 Senast uppdaterad: 2018-01-19Bibliografiskt granskad
Organisationer

Sök vidare i DiVA

Visa alla publikationer