Volume 11, Issue 3

2015


1. Deciding definability in FO2(<h,<v) on trees

Place, Thomas ; Segoufin, Luc.
We provide a decidable characterization of regular forest languages definable in FO2(<h,<v). By FO2(<h,<v) we refer to the two variable fragment of first order logic built from the descendant relation and the following sibling relation. In terms of expressive power it corresponds to a […]

2. Constructing Fully Complete Models of Multiplicative Linear Logic

Schalk, Andrea ; Steele, Hugh Paul.
The multiplicative fragment of Linear Logic is the formal system in this family with the best understood proof theory, and the categorical models which best capture this theory are the fully complete ones. We demonstrate how the Hyland-Tan double glueing construction produces such categories, either […]

3. On Nested Sequents for Constructive Modal Logics

Strassburger, Lutz ; Das, Anupam ; Arisaka, Ryuta.
We present deductive systems for various modal logics that can be obtained from the constructive variant of the normal modal logic CK by adding combinations of the axioms d, t, b, 4, and 5. This includes the constructive variants of the standard modal logics K4, S4, and S5. We use for […]

4. Quantitative Approximation of the Probability Distribution of a Markov Process by Formal Abstractions

Soudjani, Sadegh Esmaeil Zadeh ; Abate, Alessandro.
The goal of this work is to formally abstract a Markov process evolving in discrete time over a general state space as a finite-state Markov chain, with the objective of precisely approximating its state probability distribution in time, which allows for its approximate, faster computation by that […]

5. Quantified Constraints and Containment Problems

Martin, Barnaby D. ; Chen, Hubie ; Madelaine, Florent R..
The quantified constraint satisfaction problem $\mathrm{QCSP}(\mathcal{A})$ is the problem to decide whether a positive Horn sentence, involving nothing more than the two quantifiers and conjunction, is true on some fixed structure $\mathcal{A}$. We study two containment problems related to the […]

6. Logics with rigidly guarded data tests

Puppis, Gabriele ; Colcombet, Thomas ; Ley, Clemens.
The notion of orbit finite data monoid was recently introduced by Bojanczyk as an algebraic object for defining recognizable languages of data words. Following Buchi's approach, we introduce a variant of monadic second-order logic with data equality tests that captures precisely the data […]

7. Abstract Model Repair

Chatzieleftheriou, George ; Bonakdarpour, Borzoo ; Katsaros, Panagiotis ; Smolka, Scott A..
Given a Kripke structure M and CTL formula $\varphi$, where M does not satisfy $\varphi$, the problem of Model Repair is to obtain a new model M' such that M' satisfies $\varphi$. Moreover, the changes made to M to derive M' should be minimum with respect to all such M'. As in model checking, […]

8. Detecting Unrealizability of Distributed Fault-tolerant Systems

Finkbeiner, Bernd ; Tentrup, Leander.
Writing formal specifications for distributed systems is difficult. Even simple consistency requirements often turn out to be unrealizable because of the complicated information flow in the distributed system: not all information is available in every component, and information transmitted from […]

9. Learning Regular Languages over Large Ordered Alphabets

Mens, Irini-Eleftheria ; Maler, Oded.
This work is concerned with regular languages defined over large alphabets, either infinite or just too large to be expressed enumeratively. We define a generic model where transitions are labeled by elements of a finite partition of the alphabet. We then extend Angluin's L* algorithm for learning […]

10. Quantitative Languages Defined by Functional Automata

Filiot, Emmanuel ; Gentilini, Raffaella ; Raskin, Jean-François.
A weighted automaton is functional if any two accepting runs on the same finite word have the same value. In this paper, we investigate functional weighted automata for four different measures: the sum, the mean, the discounted sum of weights along edges and the ratio between rewards and costs. On […]

11. Compositional Verification for Timed Systems Based on Automatic Invariant Generation

Astefanoaei, Lacramioara ; Rayana, Souha Ben ; Bensalem, Saddek ; Bozga, Marius ; Combaz, Jacques.
We propose a method for compositional verification to address the state space explosion problem inherent to model-checking timed systems with a large number of components. The main challenge is to obtain pertinent global timing constraints from the timings in the components alone. To this end, we […]

12. Partial functions and domination

Chong, C. T. ; Hoi, Gordon ; Stephan, Frank ; Turetsky, Daniel.
The current work introduces the notion of pdominant sets and studies their recursion-theoretic properties. Here a set A is called pdominant iff there is a partial A-recursive function {\psi} such that for every partial recursive function {\phi} and almost every x in the domain of {\phi} there is a y […]

13. On the Axiomatizability of Impossible Futures

Chen, Taolue ; Fokkink, Wan ; van Glabbeek, Rob.
A general method is established to derive a ground-complete axiomatization for a weak semantics from such an axiomatization for its concrete counterpart, in the context of the process algebra BCCS. This transformation moreover preserves omega-completeness. It is applicable to semantics at least as […]

14. Positive fragments of coalgebraic logics

Balan, Adriana ; Kurz, Alexander ; Velebil, Jiří.
Positive modal logic was introduced in an influential 1995 paper of Dunn as the positive fragment of standard modal logic. His completeness result consists of an axiomatization that derives all modal formulas that are valid on all Kripke frames and are built only from atomic propositions, […]

15. Featherweight VeriFast

Jacobs, Bart ; Vogels, Frédéric ; Piessens, Frank.
VeriFast is a leading research prototype tool for the sound modular verification of safety and correctness properties of single-threaded and multithreaded C and Java programs. It has been used as a vehicle for exploration and validation of novel program verification techniques and for industrial […]

16. Verification for Timed Automata extended with Unbounded Discrete Data Structures

Quaas, Karin.
We study decidability of verification problems for timed automata extended with unbounded discrete data structures. More detailed, we extend timed automata with a pushdown stack. In this way, we obtain a strong model that may for instance be used to model real-time programs with procedure calls. It […]

17. Weak upper topologies and duality for cones

Keimel, Klaus.
In functional analysis it is well known that every linear functional defined on the dual of a locally convex vector space which is continuous for the weak topology is the evaluation at a uniquely determined point of the given vector space. M. Schroeder and A. Simpson have obtained a similar result […]

18. A correspondence between rooted planar maps and normal planar lambda terms

Zeilberger, Noam ; Giorgetti, Alain.
A rooted planar map is a connected graph embedded in the 2-sphere, with one edge marked and assigned an orientation. A term of the pure lambda calculus is said to be linear if every variable is used exactly once, normal if it contains no beta-redexes, and planar if it is linear and the use of […]

19. Exact Unification and Admissibility

Metcalfe, George ; Cabrer, Leonardo.
A new hierarchy of "exact" unification types is introduced, motivated by the study of admissible rules for equational classes and non-classical logics. In this setting, unifiers of identities in an equational class are preordered, not by instantiation, but rather by inclusion over the […]

20. New Directions in Categorical Logic, for Classical, Probabilistic and Quantum Logic

Jacobs, Bart.
Intuitionistic logic, in which the double negation law not-not-P = P fails, is dominant in categorical logic, notably in topos theory. This paper follows a different direction in which double negation does hold. The algebraic notions of effect algebra/module that emerged in theoretical physics form […]

21. Ellipses and Lambda Definability

Goldberg, Mayer.
Ellipses are a meta-linguistic notation for denoting terms the size of which are specified by a meta-variable that ranges over the natural numbers. In this work, we present a systematic approach for encoding such meta-expressions in the \^I-calculus, without ellipses: Terms that are parameterized […]

22. On the system CL12 of computability logic

Japaridze, Giorgi.
Computability logic (see http://www.csc.villanova.edu/~japaridz/CL/) is a long-term project for redeveloping logic on the basis of a constructive game semantics, with games seen as abstract models of interactive computational problems. Among the fragments of this logic successfully axiomatized so […]

23. Presenting Distributive Laws

Bonsangue, Marcello M. ; Hansen, Helle Hvid ; Kurz, Alexander ; Rot, Jurriaan.
Distributive laws of a monad T over a functor F are categorical tools for specifying algebra-coalgebra interaction. They proved to be important for solving systems of corecursive equations, for the specification of well-behaved structural operational semantics and, more recently, also for […]

24. Service-Oriented Logic Programming

Tutu, Ionut ; Fiadeiro, Jose Luiz.
We develop formal foundations for notions and mechanisms needed to support service-oriented computing. Our work builds on recent theoretical advancements in the algebraic structures that capture the way services are orchestrated and in the processes that formalize the discovery and binding of […]

25. Proof Theory of a Multi-Lane Spatial Logic

Linker, Sven ; Hilscher, Martin.
We extend the Multi-lane Spatial Logic MLSL, introduced in previous work for proving the safety (collision freedom) of traffic maneuvers on a multi-lane highway, by length measurement and dynamic modalities. We investigate the proof theory of this extension, called EMLSL. To this end, we prove […]