Volume 15, Issue 4

2019

1. $\aleph_1$ and the modal $\mu$-calculus

Gouveia, Maria João ; Santocanale, Luigi.
For a regular cardinal $\kappa$, a formula of the modal $\mu$-calculus is $\kappa$-continuous in a variable x if, on every model, its interpretation as a unary function of x is monotone and preserves unions of $\kappa$-directed sets. We define the fragment $C_{\aleph_1}(x)$ of the modal $\mu$-calculus and prove that all the formulas in this fragment are $\aleph_1$-continuous. For each formula $\phi(x)$ of the modal $\mu$-calculus, we construct a formula $\psi(x) \in C_{\aleph_1 }(x)$ such that $\phi(x)$ is $\kappa$-continuous, for some $\kappa$, if and only if $\phi(x)$ is equivalent to $\psi(x)$. Consequently, we prove that (i) the problem whether a formula is $\kappa$-continuous for some $\kappa$ is decidable, (ii) up to equivalence, there are only two fragments determined by continuity at some regular cardinal: the fragment $C_{\aleph_0}(x)$ studied by Fontaine and the fragment $C_{\aleph_1}(x)$. We apply our considerations to the problem of characterizing closure ordinals […]

2. Rule Formats for Nominal Process Calculi

Aceto, Luca ; Fábregas, Ignacio ; García-Pérez, Álvaro ; Ingólfsdóttir, Anna ; Ortega-Mallén, Yolanda.
The nominal transition systems (NTSs) of Parrow et al. describe the operational semantics of nominal process calculi. We study NTSs in terms of the nominal residual transition systems (NRTSs) that we introduce. We provide rule formats for the specifications of NRTSs that ensure that the associated NRTS is an NTS and apply them to the operational specifications of the early and late pi-calculus. We also explore alternative specifications of the NTSs in which we allow residuals of abstraction sort, and introduce translations between the systems with and without residuals of abstraction sort. Our study stems from the Nominal SOS of Cimini et al. and from earlier works in nominal sets and nominal logic by Gabbay, Pitts and their collaborators.

3. On the enumeration of closures and environments with an application to random generation

Bendkowski, Maciej ; Lescanne, Pierre.
Environments and closures are two of the main ingredients of evaluation in lambda-calculus. A closure is a pair consisting of a lambda-term and an environment, whereas an environment is a list of lambda-terms assigned to free variables. In this paper we investigate some dynamic aspects of evaluation in lambda-calculus considering the quantitative, combinatorial properties of environments and closures. Focusing on two classes of environments and closures, namely the so-called plain and closed ones, we consider the problem of their asymptotic counting and effective random generation. We provide an asymptotic approximation of the number of both plain environments and closures of size $n$. Using the associated generating functions, we construct effective samplers for both classes of combinatorial structures. Finally, we discuss the related problem of asymptotic counting and random generation of closed environemnts and closures.

4. On Free $\omega$-Continuous and Regular Ordered Algebras

Esik, Zoltan ; Kozen, Dexter.
We study varieties of certain ordered $\Sigma$-algebras with restricted completeness and continuity properties. We give a general characterization of their free algebras in terms of submonads of the monad of $\Sigma$-coterms. Varieties of this form are called \emph{quasi-regular}. For example, we show that if $E$ is a set of inequalities between finite $\Sigma$-terms, and if $\mathcal{V}_\omega$ and $\mathcal{V}_\mathrm{reg}$ denote the varieties of all $\omega$-continuous ordered $\Sigma$-algebras and regular ordered $\Sigma$-algebras satisfying $E$, respectively, then the free $\mathcal{V}_\mathrm{reg}$-algebra $F_\mathrm{reg}(X)$ on generators $X$ is the subalgebra of the corresponding free $\mathcal{V}_\omega$-algebra $F_\omega(X)$ determined by those elements of $F_\omega(X)$ denoted by the regular $\Sigma$-coterms. This is a special case of a more general construction that applies to any quasi-regular family. Examples include the *-continuous Kleene algebras, context-free […]

5. Scalar and Vectorial mu-calculus with Atoms

Klin, Bartek ; Łełyk, Mateusz.
We study an extension of modal $\mu$-calculus to sets with atoms and we study its basic properties. Model checking is decidable on orbit-finite structures, and a correspondence to parity games holds. On the other hand, satisfiability becomes undecidable. We also show expressive limitations of atom-enriched $\mu$-calculi, and explain how their expressive power depends on the structure of atoms used, and on the choice between basic or vectorial syntax.

6. On completeness and parametricity in the realizability semantics of System F

Pistone, Paolo.
We investigate completeness and parametricity for a general class of realizability semantics for System F defined in terms of closure operators over sets of $\lambda$-terms. This class includes most semantics used for normalization theorems, as those arising from Tait's saturated sets and Girard's reducibility candidates. We establish a completeness result for positive types which subsumes those existing in the literature, and we show that closed realizers satisfy parametricity conditions expressed either as invariance with respect to logical relations or as dinaturality. Our results imply that, for positive types, typability, realizability and parametricity are equivalent properties of closed normal $\lambda$-terms.

7. The Dynamic Geometry of Interaction Machine: A Token-Guided Graph Rewriter

Muroya, Koko ; Ghica, Dan R..
In implementing evaluation strategies of the lambda-calculus, both correctness and efficiency of implementation are valid concerns. While the notion of correctness is determined by the evaluation strategy, regarding efficiency there is a larger design space that can be explored, in particular the trade-off between space versus time efficiency. Aiming at a unified framework that would enable the study of this trade-off, we introduce an abstract machine, inspired by Girard's Geometry of Interaction (GoI), a machine combining token passing and graph rewriting. We show soundness and completeness of our abstract machine, called the \emph{Dynamic GoI Machine} (DGoIM), with respect to three evaluations: call-by-need, left-to-right call-by-value, and right-to-left call-by-value. Analysing time cost of its execution classifies the machine as ``efficient'' in Accattoli's taxonomy of abstract machines.

8. Lifting Coalgebra Modalities and $\mathsf{MELL}$ Model Structure to Eilenberg-Moore Categories

Lemay, Jean-Simon Pacaud.
A categorical model of the multiplicative and exponential fragments of intuitionistic linear logic ($\mathsf{MELL}$), known as a \emph{linear category}, is a symmetric monoidal closed category with a monoidal coalgebra modality (also known as a linear exponential comonad). Inspired by Blute and Scott's work on categories of modules of Hopf algebras as models of linear logic, we study categories of algebras of monads (also known as Eilenberg-Moore categories) as models of $\mathsf{MELL}$. We define a $\mathsf{MELL}$ lifting monad on a linear category as a Hopf monad -- in the Brugui{è}res, Lack, and Virelizier sense -- with a special kind of mixed distributive law over the monoidal coalgebra modality. As our main result, we show that the linear category structure lifts to the category of algebras of $\mathsf{MELL}$ lifting monads. We explain how groups in the category of coalgebras of the monoidal coalgebra modality induce $\mathsf{MELL}$ lifting monads and provide a source for such […]

9. Flow Logic

Kupferman, Orna ; Vardi, Gal.
Flow networks have attracted a lot of research in computer science. Indeed, many questions in numerous application areas can be reduced to questions about flow networks. Many of these applications would benefit from a framework in which one can formally reason about properties of flow networks that go beyond their maximal flow. We introduce Flow Logics: modal logics that treat flow functions as explicit first-order objects and enable the specification of rich properties of flow networks. The syntax of our logic BFL* (Branching Flow Logic) is similar to the syntax of the temporal logic CTL*, except that atomic assertions may be flow propositions, like $> \gamma$ or $\geq \gamma$, for $\gamma \in \mathbb{N}$, which refer to the value of the flow in a vertex, and that first-order quantification can be applied both to paths and to flow functions. We present an exhaustive study of the theoretical and practical aspects of BFL*, as well as extensions and fragments of it. Our […]