HOπ in Coq
OA Location
Author(s)
Ambal, Guillaume
Lenglet, Sergueï
Schmitt, Alan
Type
Journal Article
Abstract
We present a formalization of HOπ
in Coq, a process calculus where messages carry processes. Such a higher-order calculus features two very different kinds of binder: process input, similar to λ
-abstraction, and name restriction, whose scope can be expanded by communication. For the latter, we compare four approaches to represent binders: locally nameless, de Bruijn indices, nominal, and Higher-Order Abstract Syntax. In each case, we formalize strong context bisimilarity and prove it is compatible, i.e., closed under every context, using Howe’s method, based on several proof schemes we developed in a previous paper.
in Coq, a process calculus where messages carry processes. Such a higher-order calculus features two very different kinds of binder: process input, similar to λ
-abstraction, and name restriction, whose scope can be expanded by communication. For the latter, we compare four approaches to represent binders: locally nameless, de Bruijn indices, nominal, and Higher-Order Abstract Syntax. In each case, we formalize strong context bisimilarity and prove it is compatible, i.e., closed under every context, using Howe’s method, based on several proof schemes we developed in a previous paper.
Date Issued
2021-01
Date Acceptance
2020-04-10
Citation
Journal of Automated Reasoning, 2021, 65 (1), pp.75-124
ISSN
0168-7433
Publisher
Springer Science and Business Media LLC
Start Page
75
End Page
124
Journal / Book Title
Journal of Automated Reasoning
Volume
65
Issue
1
Copyright Statement
© Springer Nature B.V. 2020
Identifier
https://link.springer.com/article/10.1007/s10817-020-09553-0
Subjects
0801 Artificial Intelligence and Image Processing
0802 Computation Theory and Mathematics
1702 Cognitive Sciences
Computation Theory & Mathematics
Publication Status
Published
Date Publish Online
2020-09-14