Authors:Luís Cruz-Filipe; Graça Gaspar; Isabel Nunes; Peter Schneider-Kamp Pages: 213 - 246 Abstract: Abstract In the database world, integrity constraints are essential to guarantee database integrity. The related problem of database repair deals with finding the best way to change a database so that it satisfies its integrity constraints. These two topics have been studied intensively since the 1980s. The formalism of active integrity constraints, proposed in 2004, aims at addressing them jointly, by providing a syntax whereby a particular subclass of integrity constraints can be specified together with preferred ways to repair inconsistency. In the last decade, several authors have proposed adaptations of the notion of integrity constraints to other reasoning frameworks than relational databases. In this article, we extend this line of work in two ways. First, we target multi-context systems, a general-purpose framework for combining heterogeneous reasoning systems, able to model most other reasoning frameworks, as we demonstrate. Second, we extend the notions of active integrity constraints and grounded repairs to this generalized setting. This way of including repair suggestions inside integrity constraints, subject to a validity check, enables us to define simple iterative algorithms to find all possible grounded repairs for an inconsistent multi-context system, avoiding the need to solve complex or undecidable problems. PubDate: 2018-08-01 DOI: 10.1007/s10472-018-9577-y Issue No:Vol. 83, No. 3-4 (2018)

Authors:Christoph Beierle; Christian Eichhorn; Gabriele Kern-Isberner; Steven Kutsch Pages: 247 - 275 Abstract: Abstract While the axiomatic system P is an important standard for plausible, nonmonotonic inferences from conditional knowledge bases, it is known to be too weak to solve benchmark problems like Irrelevance or Subclass Inheritance. Ordinal conditional functions provide a semantic base for system P and have often been used to design stronger inference relations, like Pearl’s system Z, or c-representations. While each c-representation shows excellent inference properties and handles particularly Irrelevance and Subclass Inheritance properly, it is still an open problem which c-representation is the best. In this paper, we consider the skeptical inference relation, called c-inference, that is obtained by taking all c-representations of a given knowledge base into account. We study properties of c-inference and show in particular that it preserves the properties of solving Irrelevance and Subclass Inheritance. Based on a characterization of c-representations as solutions of a Constraint Satisfaction Problem (CSP), we also model skeptical c-inference as a CSP and prove soundness and completeness of the modelling, ensuring that constraint solvers can be used for implementing c-inference. PubDate: 2018-08-01 DOI: 10.1007/s10472-017-9571-9 Issue No:Vol. 83, No. 3-4 (2018)

Authors:Bernhard Bliem; Stefan Woltran Pages: 277 - 295 Abstract: Abstract Answer Set Programming has become an increasingly popular formalism for declarative problem solving. Among the huge body of theoretical results, investigations of different equivalence notions between logic programs play a fundamental role for understanding modularity and optimization. While strong equivalence between two programs holds if they can be faithfully replaced by each other in any context (facts and rules), uniform equivalence amounts to equivalent behavior of programs under any set of facts. Both notions (as well as several variants thereof) have been extensively studied. However, the somewhat reverse notion of equivalence which holds if two programs are equivalent under the addition of any set of proper rules (i.e., all rules except facts) has not been investigated yet. In this paper, we close this gap and give a thorough study of this notion, which we call rule equivalence , and its parameterized version where we allow facts over a given restricted alphabet to appear in the context. This notion of equivalence is thus a relationship between two programs whose input is (partially) fixed but where additional proper rules might still be added. Such a notion might be helpful in debugging of programs. We give full characterization results and a complexity analysis for the propositional case of rule equivalence and its relativized versions. Moreover, we address the problem of program simplification under rule equivalence. Finally, we show that rule equivalence is decidable in the non-ground case. PubDate: 2018-08-01 DOI: 10.1007/s10472-017-9567-5 Issue No:Vol. 83, No. 3-4 (2018)

Authors:Arnaud Durand; Miika Hannula; Juha Kontinen; Arne Meier; Jonni Virtema Pages: 297 - 320 Abstract: Abstract We define a variant of team semantics called multiteam semantics based on multisets and study the properties of various logics in this framework. In particular, we define natural probabilistic versions of inclusion and independence atoms and certain approximation operators motivated by approximate dependence atoms of Väänänen. PubDate: 2018-08-01 DOI: 10.1007/s10472-017-9568-4 Issue No:Vol. 83, No. 3-4 (2018)

Authors:Flavio Ferrarotti; Klaus-Dieter Schewe; Loredana Tec; Qing Wang Pages: 321 - 349 Abstract: Abstract We develop a logic which enables reasoning about single steps of non-deterministic and parallel Abstract State Machines (ASMs). Our logic builds upon the unifying logic introduced by Nanchen and Stärk for reasoning about hierarchical (parallel) ASMs. Our main contribution is the handling of non-determinism within the logical formalism. We do this without sacrificing the completeness of the logic for statements about single steps of non-deterministic and parallel ASMs, such as invariants of rules, consistency conditions for rules, or step-by-step equivalence of rules. Moreover, we show that the proposed one-step logic can be easily extended to a multiple-step logic which enables reasoning about concurrent ASMs. PubDate: 2018-08-01 DOI: 10.1007/s10472-017-9569-3 Issue No:Vol. 83, No. 3-4 (2018)

Authors:Ofri Keidar; Noa Agmon Pages: 121 - 164 Abstract: Abstract This work deals with the problem of navigation while avoiding detection by a mobile adversary, featuring adversarial modeling. In this problem, an evading agent is placed on a graph, where one or more nodes are defined as safehouses. The agent’s goal is to find a path from its current location to a safehouse, while minimizing the probability of meeting a mobile adversarial agent at a node along its path (i.e., being captured). We examine several models of this problem, where each one has different assumptions on what the agents know about their opponent, all using a framework for computing node utility, introduced herein. Using risk attitudes for computing the utility values, their impact on the constructed strategies is analyzed both theoretically and empirically. Furthermore, we allow the agents to use information gained along their movement, in order to efficiently update their motion strategies on-the-fly. Theoretical and empirical analysis shows the importance of using this information and these on-the-fly strategy updates. PubDate: 2018-06-01 DOI: 10.1007/s10472-018-9591-0 Issue No:Vol. 83, No. 2 (2018)

Authors:Imen Zghidi; Brahim Hnich; Abdelwaheb Rebai Pages: 165 - 181 Abstract: Abstract In this paper, we propose a novel notion of statistical consistency for single-stage Stochastic Constraint Satisfaction Problems (SCSPs) in which some of the random variables’ support set is infinite. The essence of this novel notion of local consistency is to be able to make an inference in the presence of infinite scenarios in an uncertain environment. This inference would be based on a restricted finite subset of scenarios with a certain confidence level and a threshold tolerance error. The confidence level is the probability that characterizes the extend to which our inference — based on a subset of scenarios — is correct. The threshold tolerance error is the error range that we can tolerate while making such an inference. We propose a novel statistical consistency enforcing algorithm that is based on sound statistical inference; and experimentally show how to prune inconsistent values in the presence of an infinite set of scenarios. PubDate: 2018-06-01 DOI: 10.1007/s10472-018-9572-3 Issue No:Vol. 83, No. 2 (2018)

Authors:Wafa Jguirim; Wady Naanaa; Martin C. Cooper Pages: 1 - 20 Abstract: Abstract Finding a solution to a constraint satisfaction problem (CSP) is known to be an NP-hard task. Considerable effort has been spent on identifying tractable classes of CSP, in other words, classes of constraint satisfaction problems for which there are polynomial time recognition and resolution algorithms. In this article, we present a relational tractable class of binary CSP. Our key contribution is a new ternary operation that we name mjx. We first characterize mjx-closed relations which leads to an optimal algorithm to recognize such relations. To reduce space and time complexity, we define a new storage technique for these relations which reduces the complexity of establishing a form of strong directional path consistency, the consistency level that solves all instances of the proposed class (and, indeed, of all relational classes closed under a majority polymorphism). PubDate: 2018-05-01 DOI: 10.1007/s10472-017-9566-6 Issue No:Vol. 83, No. 1 (2018)

Authors:Subhrajit Bhattacharya; Robert Ghrist Abstract: Abstract We consider the problem of optimal path planning in different homotopy classes in a given environment. Though important in robotics applications, path-planning with reasoning about homotopy classes of trajectories has typically focused on subsets of the Euclidean plane in the robotics literature. The problem of finding optimal trajectories in different homotopy classes in more general configuration spaces (or even characterizing the homotopy classes of such trajectories) can be difficult. In this paper we propose automated solutions to this problem in several general classes of configuration spaces by constructing presentations of fundamental groups and giving algorithms for solving the word problem in such groups. We present explicit results that apply to knot and link complements in 3-space, discuss how to extend to cylindrically-deleted coordination spaces of arbitrary dimension, and also present results in the coordination space of robots navigating on an Euclidean plane. PubDate: 2018-07-31 DOI: 10.1007/s10472-018-9596-8

Authors:Tobias Ahlbrecht; Jürgen Dix; Niklas Fiekas Abstract: Abstract We present the twelfth edition of the Multi-Agent Programming Contest (https://multiagentcontest.org), an annual, community-serving competition that attracts groups from all over the world. Our contest facilitates comparison of multi-agent systems and provides a concrete problem that is interesting in itself and well-suited to be tackled in educational environments. This time, seven teams competed using strictly agent-based as well as traditional programming approaches. PubDate: 2018-07-10 DOI: 10.1007/s10472-018-9594-x

Authors:Ioannis Kokkinis Abstract: Abstract Let L be some extension of classical propositional logic. The non-iterated probabilistic logic over L is the logic PL that is defined by adding non-nested probabilistic operators in the language of L. For example, in PL we can express a statement like “the probability of truthfulness of A is at least 0.3” where A is a formula of L. The iterated probabilistic logic over L is the logic PPL, where the probabilistic operators may be iterated (nested). For example, in PPL we can express a statement like “this coin is counterfeit with probability 0.6”. In this paper we investigate the influence of probabilistic operators in the complexity of satisfiability in PL and PPL. We obtain complexity bounds, for the aforementioned satisfiability problem, which are parameterized in the complexity of satisfiability of conjunctions of positive and negative formulas that have neither a probabilistic nor a classical operator as a top-connective. As an application of our results we obtain tight complexity bounds for the satisfiability problem in PL and PPL when L is classical propositional logic or justification logic. PubDate: 2018-07-06 DOI: 10.1007/s10472-018-9593-y

Authors:Zuoquan Lin; Chen Chen Abstract: Abstract In nonmonotonic reasoning there are the problems of inconsistency and incoherence in general, and in default reasoning there may be only one trivial extension or no extension in special. We propose the restricted semantics of four-valued logic for default reasoning to resolve the problems of inconsistency and incoherence and in the meantime retain classical extensions in the presence of consistency and coherency. The restricted semantics can maintain both the expressiveness and reasoning ability of default logic. We provide a transformation approach to compute the restricted extensions by reducing them into classical ones. PubDate: 2018-06-18 DOI: 10.1007/s10472-018-9592-z

Authors:Jonathan Pieper Abstract: Abstract This paper describes the team BusyBeaver, that participated in and won the Multi-Agent Programming Contest 2017. Its strategy is based on dividing agents into three static groups modeling the work chain of buying, assembling and delivering items. The team is coordinated by a centralized agent doing most of the high-level planning, usually using greedy algorithms and specialized heuristics. There is a heavy focus on proactively buying and assembling some items, in order to quickly complete upcoming jobs. PubDate: 2018-06-09 DOI: 10.1007/s10472-018-9589-7

Authors:Z. Kovács; T. Recio; C. Sólyom-Gecse Abstract: Abstract We present an algorithm to help converting expressions having non-negative quantities (like distances) in Euclidean geometry theorems to be usable in a complex algebraic geometry prover. The algorithm helps in refining the output of an existing prover, therefore it supports immediate deployment in high level prover systems. We prove that the algorithm may take doubly exponential time to produce the output in polynomial form, but in many cases it is still computable and useful. PubDate: 2018-06-04 DOI: 10.1007/s10472-018-9590-1

Authors:Evangelos I. Sarmas Abstract: Abstract This paper presents the workings of the Flisvos-2017 multi-agent system that participated in the Multi-Agent Programming Contest MAPC 2017 of Clausthal TU. PubDate: 2018-06-02 DOI: 10.1007/s10472-018-9587-9

Authors:Jørgen Villadsen; Oliver Fleckenstein; Helge Hatteland; John Bruntse Larsen Abstract: Abstract This paper presents the overall strategy utilized by Jason-DTU to achieve a shared second place in the annual Multi-Agent Programming Contest. It provides an overview of the implementation details considering perception, task handling, agent logic and more. The paper analyzes the team’s results in each match, and is summarized by evaluating strengths and weaknesses of the proposed multi-agent system. PubDate: 2018-06-01 DOI: 10.1007/s10472-018-9588-8

Authors:Christopher-Eyk Hrabia; Patrick Marvin Lehmann; Nabil Battjbuer; Axel Hessler; Sahin Albayrak Abstract: Abstract In the Multi-Agent Programming Contest 2017 the TUBDAI team of the Technische Universität Berlin is using the complex multi-agent scenario to evaluate the application of two frameworks from the field (multi-)robot systems. In particular the task-level decision-making and planning framework ROS Hybrid Behaviour Planner (RHBP) is used to implement the execution and decision-making for single agents. The RHBP framework builds on top of the framework Robot Operating System (ROS) that is used to implement the communication and scenario specific coordination strategy of the agents. The united team for the official contest is formed by volunteering students from a project course and their supervisors. PubDate: 2018-05-07 DOI: 10.1007/s10472-018-9586-x

Authors:Imen Zghidi; Brahim Hnich; Abdelwaheb Rebai Abstract: The original version of this article unfortunately contained a mistake. The name “Abdelwahad Rebaii” should be corrected to “Abdelwaheb Rebai”. PubDate: 2018-05-05 DOI: 10.1007/s10472-018-9583-0

Authors:Lorenz Demey; Hans Smessaert Abstract: Abstract Aristotelian diagrams are used extensively in contemporary research in artificial intelligence. The present paper investigates the geometric and cognitive differences between two types of Aristotelian diagrams for the Boolean algebra \(\mathbb {B}_{4}\) . Within the class of 3D visualizations, the main geometric distinction is that between the cube-based diagrams (such as the rhombic dodecahedron) and the tetrahedron-based diagrams. Geometric properties such as collinearity, central symmetry and distance are examined from a cognitive perspective, focusing on diagram design principles such as congruence/isomorphism and apprehension. The cognitive effectiveness of the different visualizations is compared for the representation of implication versus opposition relations, and for subdiagram embeddings. PubDate: 2018-05-02 DOI: 10.1007/s10472-018-9585-y