One of the most studied behavioural equivalences is bisimilarity. Its success is much due to the associated bisimulation proof method, which can be further enhanced by means of “bisimulation up-to” techniques such as “up-to context.” A different proof method is discussed, based on a unique solution of special forms of inequations called contractions and inspired by Milner’s theorem on unique solution of equations. The method is as powerful as the bisimulation proof method and its “up-to context” enhancements. The definition of contraction can be transferred onto other behavioural equivalences, possibly contextual and non-coinductive. This enables a coinductive reasoning style on such equivalences, either by applying the method based on unique solution of contractions or by injecting appropriate contraction preorders into the bisimulation game. PubDate: Thu, 16 Mar 2017 00:00:00 GMT

Abstract: Adrian Haret, Stefan Rümmele, Stefan Woltran

Belief merging is a central operation within the field of belief change and addresses the problem of combining multiple, possibly mutually inconsistent knowledge bases into a single, consistent one. A current research trend in belief change is concerned with representation theorems tailored to fragments of logic, in particular Horn logic. Hereby, the goal is to guarantee that the result of the change operations stays within the fragment under consideration. While several such results have been obtained for Horn revision and Horn contraction, merging of Horn theories has been neglected so far. In this article, we provide a novel representation theorem for Horn merging by strengthening the standard merging postulates. PubDate: Thu, 16 Mar 2017 00:00:00 GMT

We study a Hoare Logic to reason about parallel programs executed on graphics processing units (GPUs), called GPU kernels. During the execution of GPU kernels, multiple threads execute in lockstep, that is, execute the same instruction simultaneously. When the control branches, the two branches are executed sequentially, but during the execution of each branch only those threads that take it are enabled; after the control converges, all the threads are enabled and again execute in lockstep. In this article, we first consider a semantics in which all threads execute in lockstep (this semantics simplifies the actual execution model of GPUs) and adapt Hoare Logic to this setting by augmenting the usual Hoare triples with an additional component representing the set of enabled threads. PubDate: Wed, 22 Feb 2017 00:00:00 GMT

Abstract: Tom J. Ameloot, Bas Ketsman, Frank Neven, Daniel Zinn

We investigate the class D of queries that distribute over components. These are the queries that can be evaluated by taking the union of the query results over the connected components of the database instance. We show that it is undecidable whether a (positive) Datalog program distributes over components. Additionally, we show that connected Datalog¬ (the fragment of Datalog¬ where all rules are connected) provides an effective syntax for Datalog¬ programs that distribute over components under the stratified as well as under the well-founded semantics. As a corollary, we obtain a simple proof for one of the main results in previous work [Zinn et al. PubDate: Wed, 22 Feb 2017 00:00:00 GMT

In the present article, we formally define the notion of abstract program slicing, a general form of program slicing where properties of data are considered instead of their exact value. This approach is applied to a language with numeric and reference values and relies on the notion of abstract dependencies between program statements. The different forms of (backward) abstract slicing are added to an existing formal framework where traditional, nonabstract forms of slicing could be compared. The extended framework allows us to appreciate that abstract slicing is a generalization of traditional slicing, since each form of traditional slicing (dealing with syntactic dependencies) is generalized by a semantic (nonabstract) form of slicing, which is actually equivalent to an abstract form where the identity abstraction is performed on data. PubDate: Wed, 22 Feb 2017 00:00:00 GMT

Abstract: Martin Lück, Arne Meier, Irena Schindler

We apply the concept of formula treewidth and pathwidth to computation tree logic, linear temporal logic, and the full branching time logic. Several representations of formulas as graphlike structures are discussed, and corresponding notions of treewidth and pathwidth are introduced. As an application for such structures, we present a classification in terms of parametrised complexity of the satisfiability problem, where we make use of Courcelle’s famous theorem for recognition of certain classes of structures. Our classification shows a dichotomy between W[1]-hard and fixed-parameter tractable operator fragments almost independently of the chosen graph representation. The only fragments that are proven to be fixed-parameter tractable (FPT) are those that are restricted to the X operator. PubDate: Fri, 20 Jan 2017 00:00:00 GMT