Volume 12, Issue 4

2016


1. Extending Unification in $\mathcal{EL}$ to Disunification: The Case of Dismatching and Local Disunification

Baader, Franz ; Borgwardt, Stefan ; Morawska, Barbara.
Unification in Description Logics has been introduced as a means to detect redundancies in ontologies. We try to extend the known decidability results for unification in the Description Logic $\mathcal{EL}$ to disunification since negative constraints can be used to avoid unwanted unifiers. While […]

2. Model Checking Spatial Logics for Closure Spaces

Ciancia, Vincenzo ; Latella, Diego ; Loreti, Michele ; Massink, Mieke.
Spatial aspects of computation are becoming increasingly relevant in Computer Science, especially in the field of collective adaptive systems and when dealing with systems distributed in physical space. Traditional formal verification techniques are well suited to analyse the temporal evolution […]

3. Some theorems on passing from local to global presence of properties of functions

Skordev, Dimiter.
When given a class of functions and a finite collection of sets, one might be interested whether the class in question contains any function whose domain is a subset of the union of the sets of the given collection and whose restrictions to all of them belong to this class. The collections with […]

4. Borel-piecewise continuous reducibility for uniformization problems

Kihara, Takayuki.
We study a fine hierarchy of Borel-piecewise continuous functions, especially, between closed-piecewise continuity and $G_\delta$-piecewise continuity. Our aim is to understand how a priority argument in computability theory is connected to the notion of $G_\delta$-piecewise continuity, and then we […]

5. Discovering, quantifying, and displaying attacks

Vigo, Roberto ; Nielson, Flemming ; Nielson, Hanne Riis.
In the design of software and cyber-physical systems, security is often perceived as a qualitative need, but can only be attained quantitatively. Especially when distributed components are involved, it is hard to predict and confront all possible attacks. A main challenge in the development of […]

6. Automata for Specifying and Orchestrating Service Contracts

Basile, Davide ; Degano, Pierpaolo ; Ferrari, Gian-Luigi.
An approach to the formal description of service contracts is presented in terms of automata. We focus on the basic property of guaranteeing that in the multi-party composition of principals each of them gets his requests satisfied, so that the overall composition reaches its goal. Depending on […]

7. Honesty by Typing

Bartoletti, Massimo ; Scalas, Alceste ; Tuosto, Emilio ; Zunino, Roberto.
We propose a type system for a calculus of contracting processes. Processes can establish sessions by stipulating contracts, and then can interact either by keeping the promises made, or not. Type safety guarantees that a typeable process is honest - that is, it abides by the contracts it has […]

8. On the locality of arb-invariant first-order formulas with modulo counting quantifiers

Harwath, Frederik ; Schweikardt, Nicole.
We study Gaifman locality and Hanf locality of an extension of first-order logic with modulo p counting quantifiers (FO+MOD_p, for short) with arbitrary numerical predicates. We require that the validity of formulas is independent of the particular interpretation of the numerical predicates and […]

9. On linear rewriting systems for Boolean logic and some applications to proof theory

Das, Anupam ; Straßburger, Lutz.
Linear rules have played an increasing role in structural proof theory in recent years. It has been observed that the set of all sound linear inference rules in Boolean logic is already coNP-complete, i.e. that every Boolean tautology can be written as a (left- and right-)linear rewrite rule. In […]

10. Coalgebraic trace semantics via forgetful logics

Klin, Bartek ; Rot, Jurriaan.
We use modal logic as a framework for coalgebraic trace semantics, and show the flexibility of the approach with concrete examples such as the language semantics of weighted, alternating and tree automata, and the trace semantics of generative probabilistic systems. We provide a sufficient condition […]

11. On the Mints Hierarchy in First-Order Intuitionistic Logic

Schubert, Aleksy ; Urzyczyn, Paweł ; Zdanowski, Konrad.
We stratify intuitionistic first-order logic over $(\forall,\to)$ into fragments determined by the alternation of positive and negative occurrences of quantifiers (Mints hierarchy). We study the decidability and complexity of these fragments. We prove that even the $\Delta_2$ level is undecidable […]

12. Compositional bisimulation metric reasoning with Probabilistic Process Calculi

Gebler, Daniel ; Larsen, Kim G. ; Tini, Simone.
We study which standard operators of probabilistic process calculi allow for compositional reasoning with respect to bisimulation metric semantics. We argue that uniform continuity (generalizing the earlier proposed property of non-expansiveness) captures the essential nature of compositional […]

13. Encoding Monomorphic and Polymorphic Types

Blanchette, Jasmin Christian ; Böhme, Sascha ; Popescu, Andrei ; Smallbone, Nicholas.
Many automatic theorem provers are restricted to untyped logics, and existing translations from typed logics are bulky or unsound. Recent research proposes monotonicity as a means to remove some clutter when translating monomorphic to untyped first-order logic. Here we pursue this approach […]