Arrow Research search

Author name cluster

Thomas Eiter

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

164 papers
2 author rows

Possible papers

164

NAI Journal 2026 Journal Article

Leveraging Neurosymbolic AI for Slice Discovery

  • Michele Collevati
  • Thomas Eiter
  • Nelson Higuera

While remarkable recent developments in deep neural networks have significantly contributed to advancing the state-of-the-art in computer vision (CV), several studies have also shown their limitations and defects. In particular, CV models often make systematic errors on important subsets of data called slices, which are groups of data sharing a set of attributes. A slice discovery method (SDM) is meant to detect semantically meaningful slices on which the model performs poorly, called rare slices. We propose a modular neurosymbolic SDM whose distinctive advantage is the extraction via inductive logic programming of human-readable logical rules describing rare slices, and thus enhancing the explainability of CV models. To this end, a methodology for inducing the occurrence of rare slices in a model is presented. We validate the SDM approach on both the synthetic Super-CLEVR and real-world ImageNet datasets. Our experiments demonstrate the complete pipeline: first, we successfully induce targeted rare slices using our taxonomy-based heuristic; second, our neurosymbolic SDM correctly identifies these slices and produces precise, human-readable logical rules to describe them; and finally, these rules are used to guide a data augmentation process that successfully mends model behaviour and improves its predictive performance. 1

IJCAI Conference 2025 Conference Paper

A Sequent Calculus for Answer Set Entailment

  • Thomas Eiter
  • Tobias Geibinger

Answer Set Programming (ASP) is a popular nonmonotonic formalism used for common-sense reasoning and problem-solving based on stable model semantics. Equilibrium logic is a generalisation of ASP for arbitrary propositional theories and thus provides a logical characterisation of the nonmonotonic stable model semantics. In difference to classical logic, which can be defined via proof or model theory, nonmonotonic reasoning formalisms are defined via their models exclusively. Equilibrium logic is no exception here, as it has no proper proof-theoretic axiomatisation. Besides this being a theoretical imbalance, it also has consequences regarding notions of justification and explainability. In this work, we fill this gap by providing a sequent calculus for answer set entailment. Our calculus builds upon ideas from existing calculi for other nonmonotonic formalisms and utilises calculi for the logic of here and there, which is the underlying base logic of equilibrium logic. We show that the calculus is sound and complete and discuss pitfalls as well as alternative axiomatisations. Finally, we address how our approach can be of use for explainability in ASP.

AAAI Conference 2025 Conference Paper

ASP-Driven Emergency Planning for Norm Violations in Reinforcement Learning

  • Sebastian Adam
  • Thomas Eiter

Reinforcement learning is a widely used approach for training an agent to maximize rewards in a given environment. Action policies learned with this technique see a broad range of applications in practical areas like games, healthcare, robotics, or autonomous driving. However, enforcing ethical behavior or norms based on deontic constraints that the agent should adhere to during policy execution remains a complex challenge. Especially constraints that emerge after the training can necessitate to redo policy learning, which can be costly and, more critically, time-intense. In order to mitigate this problem, we present a framework for policy fixing in case of a norm violation, which allows the agent to stay operational. Based on answer set programming (ASP), emergency plans are generated that exclude or minimize cost of norm violations by future actions in a horizon of interest. By combining and developing optimization techniques, efficient policy fixing under real-time constraints can be achieved.

NeSy Conference 2025 Conference Paper

Explainable Zero-Shot Visual Question Answering via Logic-Based Reasoning

  • Thomas Eiter
  • Jan Hadl
  • Nelson Higuera Ruiz
  • Lukas Lange
  • Johannes Oetsch
  • Bileam Scheuvens
  • Jannik Strötgen

Visual Question Answering (VQA) is the task of answering natural language questions about images, which is a challenge for AI systems. To enhance adaptability and reduce training overhead, we address VQA in a zero-shot setting by leveraging pre-trained neural modules without additional fine-tuning. Our proposed hybrid neurosymbolic framework, whose capabilities are demonstrated on the challenging GQA dataset, integrates neural and symbolic components through logic-based reasoning via Answer-Set Programming. Specifically, our pipeline employs large language models for semantic parsing of input questions, followed by the generation of a scene graph that captures relevant visual content. Interpretable rules then operate on the symbolic representations of both the question and the scene graph to derive an answer. Our framework provides a key advantage: it enables full transparency into the reasoning process. Using an existing explanation tool, we illustrate how our method fosters trust by making decisions interpretable and facilitates error analysis when predictions are incorrect. Beyond explaining its own reasoning, our framework can also explain answers from more opaque models by integrating their answers into our system, enabling broader interpretability in VQA.

ECAI Conference 2025 Conference Paper

OFTEN-DEEPRL: On-the-Fly Teaching of Ethical Norms to Deep Reinforcement Learning Agents

  • Ignacio D. Lopez-Miguel
  • Sebastian P. Adam
  • Ezio Bartocci
  • Thomas Eiter
  • Martin Tappler

AI agents trained with reinforcement learning (RL) usually focus on completing their intended tasks without detours, as doing so typically maximizes their reward. However, real-world deployment requires agents that not only achieve their goals but also comply with ethical and societal norms that may conflict with their learned behavior. In this work, we present OFTEN-DEEPRL, an approach to integrate ethical norms into agents trained with deep reinforcement learning. The approach starts by training an RL policy focused on task performance. Building upon such a pre-trained policy, OFTEN-DEEPRL adapts the policy through norm-guided training. For a combination of observations and domain knowledge, we employ a logic program that generates norm-compliant plans for the agent using answer set programming (ASP) within a given planning horizon. These plans serve as demonstrations for fine-tuning the agent’s policy in the norm-guided training phase, guiding it toward behavior that remains effective while respecting the specified norms. We validate our approach with three types of scenarios: Pac-Man, a gardener simulation, and a SUMO-RL traffic control scenario. In all settings, agents fine-tuned with OFTEN-DEEPRL achieve comparable task performance while significantly reducing norm violations.

IJCAI Conference 2025 Conference Paper

On Temporal ASP with Eager Unfoldable Operators

  • Thomas Eiter
  • Davide Soldà

Temporal Equilibrium Logic (TEL) extends Answer Set Programming (ASP) with linear-time temporal operators (LTL), enabling reasoning about dynamic systems. However, TEL enforces strong minimization criteria that may preclude intuitive models. Liveness formulas, for instance, tend to fail to have infinite equilibrium models, as TEL minimization postpones satisfaction forever. We address this limitation by introducing eager temporal operators (eager Until, eager Release, etc. ), and present non-disjunctive temporal programs (NDTP) as a framework for modeling dependencies, inertia, and non-determinism. The fragment of tight temporal programs (TTP), which can be recognized efficiently based on automata techniques for loop detections, guarantees polynomial encodability into LTL. Practical examples, such as request-grant protocols and user permissions in distributed systems, illustrate the applicability of our approach.

NeurIPS Conference 2025 Conference Paper

T-norm Selection for Object Detection in Autonomous Driving with Logical Constraints

  • Thomas Eiter
  • Katsumi Inoue
  • Nelson Higuera
  • Sota Moriyama

Integrating logical constraints into object detection models for autonomous driving (AD) is a promising way to enhance their compliance with rules and thereby increase the safety of the system. T-norms have been utilized to calculate the constrained loss, i. e. , the violations of logical constraints as losses. While prior works have statically selected a few t-norms, we conduct an extensive experimental study to identify the most effective choices, as suboptimal t-norms can lead to undesired model behavior. To this end, we present MOD-ECL, a neurosymbolic framework that implements a wide range of t-norms and applies them in an adaptive manner. It includes an algorithm that selects well-performing t-norms during training and a scheduler that regulates the impact of the constrained loss. We evaluate its effectiveness on the ROAD-R and ROAD-Waymo-R datasets for object detection in AD, using attached common-sense constraints. Our results show that careful selection of parameters is crucial for effective constrained loss behavior. Moreover, our framework not only reduces constraint violations but also, in some cases, improves detection performance. Additionally, our methods offer fine-grained control over the trade-off between accuracy and constraint violation.

IJCAI Conference 2025 Conference Paper

Witnesses for Answer Sets of Basic Logic Programs

  • Yisong Wang
  • Xianglong Wang
  • Zhongtao Xie
  • Thomas Eiter

Explanation plays an important role in the decisions of both symbolic and neural network-based AI systems. Logic programs under answer set semantics (ASP) have been a typical declarative reasoning and problem-solving paradigm that has extensive applications in various AI domains. In this paper, we consider the issue of explanation for logic programs with abstract constraint atoms (c-atoms) under SPT-answer set semantics. Such c-atoms are general enough to capture complex constructors of logic programs, including aggregates, and the SPT-answer sets exclude circular justifications that other semantics have. We propose a minimal reduct for logic programs with c-atoms that yields a new semantic characterization of SPT-answer sets, and then introduce an extension of resolution for clauses with c-atoms. As we show, every atom in an SPT-answer set enjoys an extended resolution proof from the minimal reduct of its logic program. Finally, we present minimal sufficient subsets of logic programs (witnesses) to structure such an extended resolution proof for an atom in an SPT-answer set. Our results contribute to the justification of answer sets and provide a basis for explainability of ASP-based applications.

AIJ Journal 2024 Journal Article

Adaptive large-neighbourhood search for optimisation in answer-set programming

  • Thomas Eiter
  • Tobias Geibinger
  • Nelson Higuera Ruiz
  • Nysret Musliu
  • Johannes Oetsch
  • Dave Pfliegler
  • Daria Stepanova

Answer-set programming (ASP) is a prominent approach to declarative problem solving that is increasingly used to tackle challenging optimisation problems. We present an approach to leverage ASP optimisation by using large-neighbourhood search (LNS), which is a meta-heuristic where parts of a solution are iteratively destroyed and reconstructed in an attempt to improve an overall objective. In our LNS framework, neighbourhoods can be specified either declaratively as part of the ASP encoding or automatically generated by code. Furthermore, our framework is self-adaptive, i. e. , it also incorporates portfolios for the LNS operators along with selection strategies to adjust search parameters on the fly. The implementation of our framework, the system ALASPO, currently supports the ASP solver clingo, as well as its extensions clingo-dl and clingcon that allow for difference and full integer constraints, respectively. It utilises multi-shot solving to efficiently realise the LNS loop and in this way avoids program regrounding. We describe our LNS framework for ASP as well as its implementation, discuss methodological aspects, and demonstrate the effectiveness of the adaptive LNS approach for ASP on different optimisation benchmarks, some of which are notoriously difficult, as well as real-world applications for shift planning, configuration of railway-safety systems, parallel machine scheduling, and test laboratory scheduling.

AIJ Journal 2024 Journal Article

aspmc: New frontiers of algebraic answer set counting

  • Thomas Eiter
  • Markus Hecher
  • Rafael Kiesel

In the last decade, there has been increasing interest in extensions of answer set programming (ASP) that cater for quantitative information such as weights or probabilities. A wide range of quantitative reasoning tasks for ASP and logic programming, among them probabilistic inference and parameter learning in the neuro-symbolic setting, can be expressed as algebraic answer set counting (AASC) tasks, i. e. , weighted model counting for ASP with weights calculated over some semiring, which makes efficient solvers for AASC desirable. In this article, we present Image 1, a new solver for AASC that pushes the limits of efficient solvability. Notably, Image 1 provides improved performance compared to the state of the art in probabilistic inference by exploiting three insights gained from thorough theoretical investigations in our work. Namely, we consider the knowledge compilation step in the AASC pipeline, where the underlying logical theory specified by the answer set program is converted into a tractable circuit representation, on which AASC is feasible in polynomial time. First, we provide a detailed comparison of different approaches to knowledge compilation for programs, revealing that translation to propositional formulas followed by compilation to sd-DNNF seems favorable. Second, we study how the translation to propositional formulas should proceed to result in efficient compilation. This leads to the second and third insight, namely a novel way of breaking the positive cyclic dependencies in a program, called T P -Unfolding, and an improvement to the Clark Completion, the procedure used to transform programs without positive cyclic dependencies into propositional formulas. Both improvements are tailored towards efficient knowledge compilation. Our empirical evaluation reveals that while all three advancements contribute to the success of Image 1, T P -Unfolding improves performance significantly by allowing us to handle cyclic instances better.

IJCAI Conference 2024 Conference Paper

Computational Aspects of Progression for Temporal Equilibrium Logic

  • Thomas Eiter
  • Davide Soldà

Temporal logic plays a crucial role in specifying and reasoning about dynamic systems, where temporal constraints and properties to be monitored are essential. Traditional approaches like LTL-monitoring assume monotonicity, which limits their applicability to scenarios involving non-monotonic temporal properties. We delve into complexity aspects of monitoring temporal specifications using non-monotonic Temporal Equilibrium Logic (TEL), a temporal extension of Answer Set Programming defined over Temporal Here and There Logic (THT) with a minimality criterion enforcing stable models. Notably, we study the complexity gap between monitoring properties in THT and TEL semantics, and the complexity of monitoring approximations based on progression, which is widely used in verification and in AI. In that, we pay particular attention to the fragment of temporal logic programs.

KR Conference 2024 Conference Paper

Contracted Temporal Equilibrium Logic

  • Pedro Cabalar
  • Thomas Eiter
  • Davide Soldà

The stable model semantics of logic programs has been characterized by Equilibrium Logic, which is a non-monotonic formalism that selects models from the (monotonic) intermediate logic of Here-and-There. It provides stable models for arbitrary propositional formulas and has been fruitfully extended to different modal languages. Among them are theories in the syntax of Linear-Time Temporal Logic (LTL), giving rise to Temporal Equilibrium logic (TEL) based on Temporal Here-and-There (THT). In TEL, models are selected that minimize truth among THT traces of the same length. In this paper, we consider a selection that in addition may reduce the number of transitions in a trace, intuitively forming a contraction of it. We thus introduce contracted THT and contracted TEL on top of a model selection on a logical basis. The resulting c-stable models can be viewed as stable models in TEL that can not be summarized into a smaller trace. We illustrate contraction on several examples related to logic programming and explore several properties, like the relation to TEL and LTL, and in particular the connection to the LTL property of stuttering.

IJCAI Conference 2024 Conference Paper

Epistemic Logic Programs: Non-Ground and Counting Complexity

  • Thomas Eiter
  • Johannes K. Fichte
  • Markus Hecher
  • Stefan Woltran

Answer Set Programming (ASP) is a prominent problem-modeling and solving framework, whose solutions are called answer sets. Epistemic logic programs (ELP) extend ASP to reason about all or some answer sets. Solutions to an ELP can be seen as consequences over multiple collections of answer sets, known as world views. While the complexity of propositional programs is well studied, the non-ground case remains open. This paper establishes the complexity of non-ground ELPs. We provide a comprehensive picture for well-known program fragments, which turns out to be complete for the class NEXPTIME with access to oracles up to SigmaP2. In the quantitative setting, we establish complexity results for counting complexity beyond #EXP. To mitigate high complexity, we establish results in case of bounded predicate arity, reaching up to the fourth level of the polynomial hierarchy. Finally, we provide ETH-tight runtime results for the parameter treewidth, which has applications in quantitative reasoning, where we reason on (marginal) probabilities of epistemic literals.

NeSy Conference 2024 Conference Paper

Leveraging Neurosymbolic AI for Slice Discovery

  • Michele Collevati
  • Thomas Eiter
  • Nelson Higuera Ruiz

Abstract While remarkable recent developments in deep neural networks have significantly contributed to advancing the state-of-the-art in Computer Vision (CV), several studies have also shown their limitations and defects. In particular, CV models often make systematic errors on important subsets of data called slices, which are groups of data sharing a set of attributes. The slice discovery problem involves detecting semantically meaningful slices on which the model performs poorly, called rare slices. We propose a modular Neurosymbolic AI approach whose distinct advantage is the extraction of human-readable logical rules that describe rare slices, and thus enhances explainability of CV models. To this end, we present a methodology to induce rare slice occurrences in a model. Experiments on datasets from our data generator leveraging on Super-CLEVR show that the approach can correctly identify rare slices and produce logical rules describing them. The rules can be fruitfully used to generate new training data to mend model behavior or may be integrated into the model to enhance its inference capabilities. (The code for reproducing our experiments is available as an online repository: https: //gitlab. tuwien. ac. at/kbs/nesy-ai/ilp4sd ).

IJCAI Conference 2023 Conference Paper

A Logic-based Approach to Contrastive Explainability for Neurosymbolic Visual Question Answering

  • Thomas Eiter
  • Tobias Geibinger
  • Nelson Higuera
  • Johannes Oetsch

Visual Question Answering (VQA) is a well-known problem for which deep-learning is key. This poses a challenge for explaining answers to questions, the more if advanced notions like contrastive explanations (CEs) should be provided. The latter explain why an answer has been reached in contrast to a different one and are attractive as they focus on reasons necessary to flip a query answer. We present a CE framework for VQA that uses a neurosymbolic VQA architecture which disentangles perception from reasoning. Once the reasoning part is provided as logical theory, we use answer-set programming, in which CE generation can be framed as an abduction problem. We validate our approach on the CLEVR dataset, which we extend by more sophisticated questions to further demonstrate the robustness of the modular architecture. While we achieve top performance compared to related approaches, we can also produce CEs for explanation, model debugging, and validation tasks, showing the versatility of the declarative approach to reasoning.

NeSy Conference 2023 Conference Paper

A Modular Neurosymbolic Approach for Visual Graph Question Answering

  • Thomas Eiter
  • Nelson Higuera Ruiz
  • Johannes Oetsch

Images containing graph-based structures are a ubiquitous and popular form of data representation that, to the best of our knowledge, have not yet been considered in the domain of Visual Question Answering (VQA). We use CLEGR, a graph question answering dataset with a generator that synthetically produces vertex-labelled graphs that are inspired by metro networks. Structured information about stations and lines is provided, and the task is to answer natural language questions concerning such graphs. While symbolic methods suffice to solve this dataset, we consider the more challenging problem of taking images of the graphs instead of their symbolic representations as input. Our solution takes the form of a modular neurosymbolic model that combines the use of optical graph recognition for graph parsing, a pretrained optical character recognition neural network for parsing node labels, and answer-set programming, a popular logic-based approach to declarative problem solving, for reasoning. The implementation of the model achieves an overall average accuracy of 73% on the dataset, providing further evidence of the potential of modular neurosymbolic systems in solving complex VQA tasks, in particular, the use and control of pretrained models in this architecture.

JELIA Conference 2023 Conference Paper

Contrastive Explanations for Answer-Set Programs

  • Thomas Eiter
  • Tobias Geibinger
  • Johannes Oetsch

Abstract Answer-Set Programming (ASP) is a popular declarative reasoning and problem solving formalism. Due to the increasing interest in explainability, several explanation approaches have been developed for ASP. However, while those formalisms are correct and interesting on their own, most are more technical and less oriented towards philosophical or social concepts of explanation. In this work, we study the notion of contrastive explanation, i. e. , answering questions of the form “Why P instead of Q? ”, in the context of ASP. In particular, we are interested in answering why atoms are included in an answer set, whereas others are not. Contrastive explainability has recently become popular due to its strong support from the philosophical, cognitive, and social sciences and its apparent ability to provide explanations that are concise and intuitive for humans. We formally define contrastive explanations for ASP based on counterfactual reasoning about programs. Furthermore, we demonstrate the usefulness of the concept on example applications and give some complexity results. The latter also provide a guideline as to how the explanations can be computed in practice.

IJCAI Conference 2023 Conference Paper

Explaining Answer-Set Programs with Abstract Constraint Atoms

  • Thomas Eiter
  • Tobias Geibinger

Answer-Set Programming (ASP) is a popular declarative reasoning and problem solving formalism. Due to the increasing interest in explainabilty, several explanation approaches have been developed for ASP. However, support for commonly used advanced language features of ASP, as for example aggregates or choice rules, is still mostly lacking. We deal with explaining ASP programs containing Abstract Constraint Atoms, which encompass the above features and others. We provide justifications for the presence, or absence, of an atom in a given answer-set. To this end, we introduce several formal notions of justification in this setting based on the one hand on a semantic characterisation utilising minimal partial models, and on the other hand on a more ruled-guided approach. We provide complexity results for checking and computing such justifications, and discuss how the semantic and syntactic approaches relate and can be jointly used to offer more insight. Our results contribute to a basis for explaining commonly used language features and thus increase accessibility and usability of ASP as an AI tool.

KR Conference 2023 Conference Paper

Knowledge Compilation and More with SharpSAT-TD

  • Rafael Kiesel
  • Thomas Eiter

SharpSAT-TD is a recently published exact model counter that performed exceptionally well in the recent editions of the Model Counting Competition (https: //mccompetition. org/). Notably, it additionally features *weighted* model counting capabilities over any semiring. In this work, we show how to exploit this fact to use SharpSAT-TD as a knowledge compiler to the class of sd-DNNF circuits. Our experimental evaluation shows that the efficiency of SharpSAT-TD for (weighted) model counting transfers to knowledge compilation, since it outperforms other state of the art knowledge compilers on standard benchmark sets. Additionally, we generalized SharpSAT-TD's preprocessing to support arbitrary semirings and consider the utility of auxiliary variables in this setting.

ECAI Conference 2023 Conference Paper

Progression for Monitoring in Temporal ASP

  • Davide Soldà
  • Ignacio D. Lopez-Miguel
  • Ezio Bartocci
  • Thomas Eiter

In recent years, there has been growing interest in the application of temporal reasoning approaches and non-monotonic logics from artificial intelligence in dynamic systems that generate data. A well-known approach to temporal reasoning is the use of a progression technique, which allows for the online computation of logical consequences of a logical knowledge base over time. We consider a progression technique for Temporal Here and There and Temporal Equilibrium Logic, which is the logic underlying answer programming over linear-temporal logic (LTL). Compared to usual LTL online computation, where the goal is to check whether a trace is compliant with a temporal specification, our approach provides also the means to compute non-monotonic temporal reasoning over a trace of observations. Besides formal notions and results, we also present an algorithm for performing progression to monitor a dynamic system, which has been implemented as a proof of concept and allows for handling expressive application scenarios.

JAIR Journal 2023 Journal Article

Semiring Reasoning Frameworks in AI and Their Computational Complexity

  • Thomas Eiter
  • Rafael Kiesel

Many important problems in AI, among them #SAT, parameter learning and probabilistic inference go beyond the classical satisfiability problem. Here, instead of finding a solution we are interested in a quantity associated with the set of solutions, such as the number of solutions, the optimal solution or the probability that a query holds in a solution. To model such quantitative problems in a uniform manner, a number of frameworks, e.g. Algebraic Model Counting and Semiring-based Constraint Satisfaction Problems, employ what we call the semiring paradigm. In the latter the abstract algebraic structure of the semiring serves as a means of parameterizing the problem definition, thus allowing for different modes of quantitative computations by choosing different semirings. While efficiently solvable cases have been widely studied, a systematic study of the computational complexity of such problems depending on the semiring parameter is missing. In this work, we characterize the latter by NP(R), a novel generalization of NP over semiring R, and obtain NP(R)-completeness results for a selection of semiring frameworks. To obtain more tangible insights into the hardness of NP(R), we link it to well-known complexity classes from the literature. Interestingly, we manage to connect the computational hardness to properties of the semiring. Using this insight, we see that, on the one hand, NP(R) is always at least as hard as NP or ModpP depending on the semiring R and in general unlikely to be in FPSPACEpoly. On the other hand, for broad subclasses of semirings relevant in practice we can employ reductions to NP, ModpP and #P. These results show that in many cases solutions are only mildly harder to compute than functions in NP, ModpP and #P, give us new insights into how problems that involve counting on semirings can be approached, and provide a means of assessing whether an algorithm is appropriate for a given class of problems.

IJCAI Conference 2022 Conference Paper

Abstraction for Non-Ground Answer Set Programs (Extended Abstract)

  • Zeynep G. Saribatur
  • Thomas Eiter
  • Peter Schüller

Abstraction is a powerful technique that has not been considered much for nonmonotonic reasoning formalisms including Answer Set Programming (ASP), apart from related simplification methods. We introduce a notion for abstracting from the domain of an ASP program that shrinks the domain size and over-approximates the set of answer sets, as well as an abstraction-&-refinement methodology that, starting from an initial abstraction, automatically yields an abstraction with an associated answer set matching an answer set of the original program if one exists. Experiments reveal the potential of the approach, by its ability to focus on the program parts that cause unsatisfiability and by achieving concrete abstract answer sets that merely reflect relevant details.

KR Conference 2022 System Paper

ALASPO: An Adaptive Large-Neighbourhood ASP Optimiser

  • Thomas Eiter
  • Tobias Geibinger
  • Nelson Higuera
  • Nysret Musliu
  • Johannes Oetsch
  • Daria Stepanova

We present the system ALASPO which implements Adaptive Large-neighbourhood search for Answer Set Programming (ASP) Optimisation. Large-neighbourhood search (LNS) is a meta-heuristic where parts of a solution are destroyed and reconstructed in an attempt to improve an overall objective. ALASPO currently supports the ASP solver clingo, as well as its extensions clingo-dl and clingcon for difference and full integer constraints, and multi-shot solving for an efficient implementation of the LNS loop. Neighbourhoods can be defined in code or declaratively as part of the ASP encoding. While the method underlying ALASPO has been described in previous work, ALASPO also incorporates portfolios for the LNS operators along with self-adaptive selection strategies as a technical novelty. This improves usability considerably at no loss of solution quality, but on the contrary often yields benefits. To demonstrate this, we evaluate ALASPO on different optimisation benchmarks.

KR Conference 2022 Conference Paper

Chasing Streams with Existential Rules

  • Jacopo Urbani
  • Markus Krötzsch
  • Thomas Eiter

We study reasoning with existential rules to perform query answering over streams of data. On static databases, this problem has been widely studied, but its extension to rapidly changing data has not yet been considered. To bridge this gap, we extend LARS, a well-known framework for rule-based stream reasoning, to support existential rules. For that, we show how to translate LARS with existentials into a semantics-preserving set of existential rules. As query answering with such rules is undecidable in general, we describe how to leverage the temporal nature of streams and present suitable notions of acyclicity that ensure decidability.

IJCAI Conference 2022 Conference Paper

Considering Constraint Monotonicity and Foundedness in Answer Set Programming

  • Yi-Dong Shen
  • Thomas Eiter

Should the properties of constraint monotonicity and foundedness be mandatory requirements that every answer set and world view semantics must satisfy? This question is challenging and has incurred a debate in answer set programming (ASP). In this paper we address the question by introducing natural logic programs whose expected answer sets and world views violate these properties and thus may be viewed as counter-examples to these requirements. Specifically we use instances of the generalized strategic companies problem for ASP benchmark competitions as concrete examples to demonstrate that the requirements of constraint monotonicity and foundedness may exclude expected answer sets for some simple disjunctive programs and world views for some epistemic specifications. In conclusion these properties should not be mandatory conditions for an answer set and world view semantics in general.

NMR Workshop 2022 Invited Paper

Hybrid Answer Set Programming: Opportunities and Challenges

  • Thomas Eiter

In the recent years, the interest in combining symbolic and sub-symbolic AI approaches has been rapidly increasing. In particular neuro-symbolic AI, in which the two approaches have been combined in a number of different ways, is in the center of attention. A natural question in this context is how answer set programs, one of the main non-monotonic rule-based formalisms in use today, may fit into this endeavor. Several authors have considered how to combine answer set programs with subsymbolic AI, specifically with (deep) neural networks, at varying levels of integration in order to facilitate semantics-enhanced applications of AI that build on subsymbolic AI such as scene classification, object tracking, or visual question answering. In this talk, we shall consider hybrid answer set programming approaches and explore opportunities and challenges for them. Notably, combining answer set programs with alternative inference approaches is not novel and has been extensively studied e.g. for logic-based ontologies. We shall also revisit lessons learnt from such work for the ongoing work on hybrid answer set programming.

AAAI Conference 2022 Conference Paper

Large-Neighbourhood Search for Optimisation in Answer-Set Solving

  • Thomas Eiter
  • Tobias Geibinger
  • Nelson Higuera Ruiz
  • Nysret Musliu
  • Johannes Oetsch
  • Daria Stepanova

While Answer-Set Programming (ASP) is a prominent approach to declarative problem solving, optimisation problems can still be a challenge for it. Large-Neighbourhood Search (LNS) is a metaheuristic for optimisation where parts of a solution are alternately destroyed and reconstructed that has high but untapped potential for ASP solving. We present a framework for LNS optimisation in answer-set solving in which neighbourhoods can be specified either declaratively as part of the ASP encoding or automatically generated by code. To effectively explore different neighbourhoods, we focus on multi-shot solving as it allows to avoid program regrounding. We illustrate the framework on different optimisation problems some of which are notoriously difficult, including shift planning and a parallel machine scheduling problem from semi-conductor production, which demonstrate the effectiveness of the LNS approach.

AAAI Conference 2021 Conference Paper

A Scalable Reasoning and Learning Approach for Neural-Symbolic Stream Fusion

  • Danh Le-Phuoc
  • Thomas Eiter
  • Anh Le-Tuan

Drivenbydeepneuralnetworks(DNN), therecentdevelopment of computer vision makes vision sensors such as stereo cameras and Lidars ubiquitous in autonomous cars, robotics and traffic monitoring. However, a traditional DNN-based data fusion pipeline like object tracking has to hard-wire an engineered set of DNN models to a fixed processing logic, which makes it difficult to infuse new models to that pipeline. To overcome this, we propose a novel neural-symbolic stream reasoning approach realised by semantic stream reasoning programs which specify DNN-based data fusion pipelines via logic rules with learnable probabilistic degrees as weights. The reasoning task over this program is governed by a novel incremental reasoning algorithm, which lends itself also as a core building block for a scalable and parallel algorithm to learn the weights for such program. Extensive experiments with our first prototype on multi-object tracking benchmarks for autonomous driving and traffic monitoring show that our flexible approach can considerably improve both accuracy and processing throughput compared to the DNN-based counterparts.

AIJ Journal 2021 Journal Article

Abstraction for non-ground answer set programs

  • Zeynep G. Saribatur
  • Thomas Eiter
  • Peter Schüller

Abstraction is an important technique utilized by humans in model building and problem solving, in order to figure out key elements and relevant details of a world of interest. This naturally has led to investigations of using abstraction in AI and Computer Science to simplify problems, especially in the design of intelligent agents and automated problem solving. By omitting details, scenarios are reduced to ones that are easier to deal with and to understand, where further details are added back only when they matter. Despite the fact that abstraction is a powerful technique, it has not been considered much in the context of nonmonotonic knowledge representation and reasoning, and specifically not in Answer Set Programming (ASP), apart from some related simplification methods. In this work, we introduce a notion for abstracting from the domain of an ASP program such that the domain size shrinks while the set of answer sets (i. e. , models) of the program is over-approximated. To achieve the latter, the program is transformed into an abstract program over the abstract domain while preserving the structure of the rules. We show in elaboration how this can be also achieved for single or multiple sub-domains (sorts) of a domain, and in case of structured domains like grid environments in which structure should be preserved. Furthermore, we introduce an abstraction-&-refinement methodology that makes it possible to start with an initial abstraction and to achieve automatically an abstraction with an associated abstract answer set that matches an answer set of the original program, provided that the program is satisfiable. Experiments based on prototypical implementations reveal the potential of the approach for problem analysis, by its ability to focus on the parts of the program that cause unsatisfiability and by achieving concrete abstract answer sets that merely reflect relevant details. This makes domain abstraction an interesting topic of research whose further use in important areas like Explainable AI remains to be explored.

KR Conference 2021 Conference Paper

Answer-Set Programming for Lexicographical Makespan Optimisation in Parallel Machine Scheduling

  • Thomas Eiter
  • Tobias Geibinger
  • Nysret Musliu
  • Johannes Oetsch
  • Peter Skočovský
  • Daria Stepanova

We deal with a challenging scheduling problem on parallel-machines with sequence-dependent setup times and release dates from a real-world application of semiconductor work-shop production. There, jobs can only be processed by dedicated machines, thus few machines can determine the makespan almost regardless of how jobs are scheduled on the remaining ones. This causes problems when machines fail and jobs need to be rescheduled. Instead of optimising only the makespan, we put the individual machine spans in non-ascending order and lexicographically minimise the resulting tuples. This achieves that all machines complete as early as possible and increases the robustness of the schedule. We study the application of Answer-Set Programming (ASP) to solve this problem. While ASP eases modelling, the combination of timing constraints and the considered objective function challenges current solving technology. The former issue is addressed by using an extension of ASP by difference logic. For the latter, we devise different algorithms that use multi-shot solving. To tackle industrial-sized instances, we study different approximations and heuristics. Our experimental results show that ASP is indeed a promising KRR paradigm for this problem and is competitive with state-of-the-art CP and MIP solvers.

IJCAI Conference 2021 Conference Paper

How Hard to Tell? Complexity of Belief Manipulation Through Propositional Announcements

  • Thomas Eiter
  • Aaron Hunter
  • Francois Schwarzentruber

Consider a set of agents with initial beliefs and a formal operator for incorporating new information. Now suppose that, for each agent, we have a formula that we would like them to believe. Does there exist a single announcement that will lead all agents to believe the corresponding formula? This paper studies the problem of the existence of such an announcement in the context of model-preference definable revision operators. First, we provide two characterisation theorems for the existence of announcements: one in the general case, the other for total partial orderings. Second, we exploit the characterisation theorems to provide upper bound complexity results. Finally, we also provide matching optimal lower bounds for the Dalal and Ginsberg operators.

AAAI Conference 2021 Conference Paper

On the Complexity of Sum-of-Products Problems over Semirings

  • Thomas Eiter
  • Rafael Kiesel

Many important problems in AI, among them SAT, #SAT, and probabilistic inference, amount to Sum-of-Products Problems, i. e. evaluating a sum of products of values from some semiring R. While efficiently solvable cases are known, a systematic study of the complexity of this problem is missing. We characterize the latter by NP(R), a novel generalization of NP over semiring R, and link it to well-known complexity classes. While NP(R) is unlikely to be contained in FPSPACE(POLY) in general, for a wide range of commutative (resp. in addition idempotent) semirings, there are reductions to #P (resp. NP) and solutions are thus only mildly harder to compute. We finally discuss NP(R)-complete reasoning problems in well-known semiring formalisms, among them Semiring-based Constraint Satisfaction Problems, obtaining new insights into their computational properties.

AIJ Journal 2021 Journal Article

Pruning external minimality checking for answer set programs using semantic dependencies

  • Thomas Eiter
  • Tobias Kaminski

Answer set programming (ASP) has become an increasingly popular approach for declarative problem solving. In order to address the needs of applications, ASP has been extended in different approaches with means for interfacing the outside world, of which hex programs are one of the most powerful such extension that provides API-style interfaces to access arbitrary external sources of information and computation, respectively. Adhering to the principle of founded derivation, computing answer sets of hex programs requires an external (e-) minimality check for answer set candidates in order to prevent cyclic justifications via external sources. Due to the generic nature of external sources, the check can be a bottleneck in practice. To mitigate this, various optimizations have been developed previously, including the use of syntactic information about atom dependencies in order to detect cases when an e-minimality check can be avoided. However, the approach largely over-approximates the real dependencies due to the black-box nature of external sources. We thus consider in this work the use of semantic information for achieving better approximations. To this end, we introduce input-output (io-) dependencies for external sources, which intuitively link the occurrence of values in the result of a call to an external source to the occurrence of values in the input provided to this call. It appears that disposing of information about io-dependencies significantly increases the potential for pruning e-minimality checks, and an empirical evaluation exhibits a clear benefit of this approach. Moreover, we study semantic and computational properties of io-dependencies and provide algorithms for constructing and optimizing sets of io-dependencies. Our work aims at laying some foundations for the use of semantic dependency information in external source access from ASP. The results are not limited to hex programs, but may analogously be deployed to other approaches that integrate external sources into ASP, such as clingo or wasp with external propagators. Furthermore, the results may be applied in other parts of the hex program evaluation pipeline as well.

KR Conference 2021 Conference Paper

Treewidth-Aware Cycle Breaking for Algebraic Answer Set Counting

  • Thomas Eiter
  • Markus Hecher
  • Rafael Kiesel

Probabilistic reasoning, parameter learning, and most probable explanation inference for answer set programming have recently received growing attention. They are only some of the problems that can be formulated as Algebraic Answer Set Counting (AASC) problems. The latter are however hard to solve, and efficient evaluation techniques are needed. Inspired by Vlasser et al. 's Tp-compilation (JAR, 2016), we introduce Tp-unfolding, which employs forward reasoning to break the cycles in the positive dependency graph of a program by unfolding them. Tp-unfolding is defined for any normal answer set program and unfolds programs with respect to unfolding sequences, which are akin to elimination orders in SAT-solving. Using "good" unfolding sequences, we can ensure that the increase of the treewidth of the unfolded program is small. Treewidth is a measure adhering to a program's tree-likeness, which gives performance guarantees for AASC. We give sufficient conditions for the existence of good unfolding sequences based on the novel notion of component-boosted backdoor size, which measures the cyclicity of the positive dependencies in a program. The experimental evaluation of a prototype implementation, the AASC solver aspmc, shows promising results.

KR Conference 2020 Conference Paper

A Semantic Perspective on Omission Abstraction in ASP

  • Zeynep G. Saribatur
  • Thomas Eiter

The recently introduced notion of ASP abstraction is on reducing the vocabulary of a program while ensuring over-approximation of its answer sets, with a focus on having a syntactic operator that constructs an abstract program. It has been shown that such a notion has the potential for program analysis at the abstract level by getting rid of irrelevant details to problem solving while preserving the structure, that aids in the explanation of the solutions. We take here a further look on ASP abstraction, focusing on abstraction by omission with the aim to obtain a better understanding of the notion. We distinguish the key conditions for omission abstraction which sheds light on the differences to the well-studied notion of forgetting. We demonstrate how omission abstraction fits into the overall spectrum, by also investigating its behavior in the semantics of a program in the framework of HT logic.

ECAI Conference 2020 Conference Paper

ASP-Based Signal Plan Adjustments for Traffic Flow Optimization

  • Thomas Eiter
  • Andreas A. Falkner
  • Patrik Schneider
  • Peter Schüller

Worldwide, many cities spend considerable effort to reduce traffic and specifically to avoid traffic congestions. Adaptive traffic control systems serve this purpose by dynamically adjusting traffic signals for optimizing the traffic flow on intersections. Systems such as SCOOT are based on an “intelligent” combination of different traffic optimization strategies. However, they miss the possibility (i) to add and change on-demand rules to implement new optimization strategies, and (ii) to simulate the outcome of new strategies on-the-fly which is similar to the capabilities of microscopic traffic simulation tools such as SUMO. In order to overcome the above limitations, we present a novel approach for calculating signal phase plans (SPPs) used for optimizations in traffic control systems. Our approach is based on Answer Set Programming (ASP) and combines ASP encodings of an abstract mesoscopic flow model and a strategy for generating possible SPPs. Experimental results shows that traffic simulation can be well approximated and that the generated SPPs improve the traffic flow effectively.

IJCAI Conference 2020 Conference Paper

Determining Inference Semantics for Disjunctive Logic Programs (Extended Abstract)

  • Yi-Dong Shen
  • Thomas Eiter

[Gelfond and Lifschitz, 1991] introduced simple disjunctive logic programs and defined the answer set semantics called GL-semantics. We observed that the requirement of GL-semantics, i. e. , an answer set should be a minimal model of the GL-reduct may be too strong and exclude some answer sets that would be reasonably acceptable. To address this, we present a novel and more permissive semantics, called determining inference semantics.

ECAI Conference 2020 Conference Paper

Reasoning with Justifiable Exceptions in Contextual Hierarchies

  • Loris Bozzato
  • Luciano Serafini
  • Thomas Eiter

The problem of reasoning with context dependent knowledge has recently gained interest in the area of description logic-based knowledge bases (KBs). Among the several proposals, we consider the Contextualized Knowledge Repository (CKR) framework. The CKR model has been recently extended with the capability of reasoning with global (context independent) defeasible axioms that can be overridden by local (context specific) knowledge. In CKR applications it is often useful to reason over a hierarchical organization of contexts. We highlight here our recent efforts on extending the CKR framework to allow for the representation of exception handling in the inheritance of knowledge across local contexts. We first concentrated on a limitation to a particular kind of context organization, i. e. , ranked hierarchies, which allows us to simplify the definition of reasoning procedures. We then further generalized the proposal to extend the reasoning on exception handling over general contextual hierarchies. In this paper we summarize the basic definitions for simple CKRs with Justifiable Exceptions, the emerging computational properties, and the ASP-based reasoning procedures that we developed. Moreover, we highlight the open challenges in generalizing the approach and our future directions.

ECAI Conference 2020 Conference Paper

Weighted LARS for Quantitative Stream Reasoning

  • Thomas Eiter
  • Rafael Kiesel

We extend LARS, which is a recent stream reasoning framework based on ASP, to weighted LARS (wLARS), where formulae are interpreted as algebraic expressions over semirings. This adds the ability to express quantitative measures of many different natures and to approach respective reasoning problems such as probabilistic reasoning, preferential reasoning and quantitative queries in a uniform manner. Notably, well-known quantitative ASP extensions can be formalized using wLARS, thus lifting them to the streaming setting. We identify a relevant wLARS fragment that is equivalent to weighted automata, which consequently gives us a rule-based language for expressing behaviors of such automata. Furthermore, we analyze evaluating wLARS formulae, showing that brave preferential reasoning is PSPACE- resp. Σ p 3 -complete in relevant settings.

JELIA Conference 2019 Conference Paper

Abstraction for Non-ground Answer Set Programs

  • Zeynep G. Saribatur
  • Peter Schüller
  • Thomas Eiter

Abstract We address the issue of abstraction, a widely used notion to simplify problems, in the context of Answer Set Programming (ASP), which is a highly expressive formalism and a convenient tool for declarative problem solving. We introduce a method to automatically abstract non-ground ASP programs given an abstraction over the domain, which ensures that each original answer set is mapped to some abstract answer set. We discuss abstraction possibilities on several examples and show the use of abstraction to gain insight into problem instances, e. g. , domain details irrelevant for problem solving; this makes abstraction attractive for getting to the essence of the problem. We also provide a tool implementing automatic abstraction from an input program.

AIJ Journal 2019 Journal Article

Determining inference semantics for disjunctive logic programs

  • Yi-Dong Shen
  • Thomas Eiter

In a seminal paper, Gelfond and Lifschitz [34] introduced simple disjunctive logic programs, where in rule heads the disjunction operator “|” is used to express incomplete information, and defined the answer set semantics (called GL-semantics for short) based on a program transformation (called GL-reduct) and the minimal model requirement. Our observations reveal that the requirement of the GL-semantics, i. e. , an answer set should be a minimal model of rules of the GL-reduct, may sometimes be too strong a condition and exclude some answer sets that would be reasonably acceptable. To address this, we present an alternative, more permissive answer set semantics, called the determining inference (DI) semantics. Specifically, we introduce a head selection function to formalize the operator | and define answer sets as follows: (i) Given an interpretation I and a selection function sel, we transform a disjunctive program Π into a normal program Π s e l I, called a disjunctive program reduct; (ii) given a base answer set semantics X for normal programs, we define I to be a candidate answer set of Π w. r. t. X if I is an answer set of Π s e l I under X; and (iii) we define I to be an answer set of Π w. r. t. X if I is a minimal candidate answer set. The DI-semantics is general and applicable to extend any answer set semantics X for normal programs to disjunctive programs. By replacing X with the GL n l p -semantics defined by Gelfond and Lifschitz [33], we induce a DI-semantics for simple disjunctive programs, and by replacing X with the well-justified semantics defined by Shen et al. [65], we further induce a DI-semantics for general disjunctive programs. We also establish a novel characterization of the GL-semantics in terms of a disjunctive program reduct, which reveals the essential difference of the DI-semantics from the GL-semantics and leads us to giving a satisfactory solution to the open problem presented by Hitzler and Seda [36] about characterizing split normal derivatives of a simple disjunctive program Π such that answer sets of the normal derivatives are answer sets of Π under the GL-semantics. Finally we give computational complexity results; in particular we show that in the propositional case deciding whether a simple disjunctive program Π has some DI-answer set is NP-complete. This is in contrast to the GL-semantics and equivalent formulations such as the FLP-semantics [24], where deciding whether Π has some answer set is Σ 2 p -complete, while brave and cautious reasoning are Σ 2 p - and Π 2 p -complete, respectively, for both GL- and DI-answer sets. For general disjunctive programs with compound formulas as building blocks, the complexity of brave and cautious reasoning increases under DI-semantics by one level of the polynomial hierarchy, which thus offers higher problem solving capacity.

IJCAI Conference 2019 Conference Paper

Meta-Interpretive Learning Using HEX-Programs

  • Tobias Kaminski
  • Thomas Eiter
  • Katsumi Inoue

Meta-Interpretive Learning (MIL) is a recent approach for Inductive Logic Programming (ILP) implemented in Prolog. Alternatively, MIL-problems can be solved by using Answer Set Programming (ASP), which may result in performance gains due to efficient conflict propagation. However, a straightforward MIL-encoding results in a huge size of the ground program and search space. To address these challenges, we encode MIL in the HEX-extension of ASP, which mitigates grounding issues, and we develop novel pruning techniques.

AIJ Journal 2018 Journal Article

Enhancing context knowledge repositories with justifiable exceptions

  • Loris Bozzato
  • Thomas Eiter
  • Luciano Serafini

Dealing with context dependent knowledge is a well-known area of study that roots in John McCarthy's seminal work. More recently, the Contextualized Knowledge Repository (CKR) framework has been conceived as a logic-based approach in which knowledge bases have a two layered structure, modeled by a global context and a set of local contexts. The global context not only contains the meta-knowledge defining the properties of local contexts, but also holds the global (context independent) object knowledge that is shared by all of the local contexts. In many practical cases, however, it is desirable to leave the possibility to “override” the global object knowledge at the local level: in other words, it is interesting to recognize the pieces of knowledge that can admit exceptional instances in the local contexts that do not need to satisfy the general axiom. To address this need, we present in this paper an extension of CKR in which defeasible axioms can be included in the global context. The latter are verified in the local contexts only for the instances for which no exception to overriding exists, where exceptions require a justification in terms of facts that are provable from the knowledge base. We formally define this semantics and study some semantic and computational properties, where we characterize the complexity of the major reasoning tasks, among them satisfiability testing, instance checking, and conjunctive query answering. Furthermore, we present a translation of extended CKRs with knowledge bases in the Description Logic SROIQ -RL under the novel semantics to datalog programs under the stable model (answer set) semantics. We also present an implementation prototype and examine its scalability with respect to the size of the input CKR and the amount (level) of defeasibility in experiments. Finally, we compare our representation approach with some major formalisms for expressing defeasible knowledge in Description Logics and contextual knowledge representation. Our work adds to the body of results on using deductive database technology such as SQL and datalog in these areas, and provides an expressive formalism (in terms of intrinsic complexity) for exception handling by overriding.

IJCAI Conference 2018 Conference Paper

Enhancing Context Knowledge Repositories with Justifiable Exceptions (Extended Abstract)

  • Loris Bozzato
  • Thomas Eiter
  • Luciano Serafini

The Contextualized Knowledge Repository (CKR) framework was conceived as a logic-based approach for representing context dependent knowledge, which is a well-known area of study in AI. The framework has a two-layer structure with a global context that contains context-independent knowledge and meta-information about the contexts, and a set of local contexts with specific knowledge bases. In many practical cases, it is desirable that inherited global knowledge can be "overridden" at the local level. In order to address this need, we present an extension of CKR with global defeasible axioms: these axioms locally apply to (tuples of) individuals unless an exception for overriding exists; such an exception, however, requires a justification that is provable from the knowledge base. We formalize this intuition and study its semantic and computational properties. Furthermore, we present a translation of extended CKRs to datalog programs under the answer set (i. e. , stable) semantics and we present an implementation prototype. Our work adds to the body of results on using deductive database technology in these areas, and provides an expressive formalism for exception handling by overriding.

JAIR Journal 2018 Journal Article

Exploiting Partial Assignments for Efficient Evaluation of Answer Set Programs with External Source Access

  • Thomas Eiter
  • Tobias Kaminski
  • Christoph Redl
  • Antonius Weinzierl

Answer Set Programming (ASP) is a well-known declarative problem solving approach based on nonmonotonic logic programs, which has been successfully applied to a wide range of applications in artificial intelligence and beyond. To address the needs of modern applications, HEX-programs were introduced as an extension of ASP with external atoms for accessing information outside programs via an API style bi-directional interface mechanism. To evaluate such programs, conflict-driving learning algorithms for SAT and ASP solving have been extended in order to capture the semantics of external atoms. However, a drawback of the state-of-the-art approach is that external atoms are only evaluated under complete assignments (i.e., input to the external source) while in practice, their values often can be determined already based on partial assignments alone (i.e., from incomplete input to the external source). This prevents early backtracking in case of conflicts, and hinders more efficient evaluation of HEX-programs. We thus extend the notion of external atoms to allow for three-valued evaluation under partial assignments, while the two-valued semantics of the overall HEX-formalism remains unchanged. This paves the way for three enhancements: first, to evaluate external sources at any point during model search, which can trigger learning knowledge about the source behavior and/or early backtracking in the spirit of theory propagation in SAT modulo theories (SMT). Second, to optimize the knowledge learned in terms of so-called nogoods, which roughly speaking are impossible input-output configurations. Shrinking nogoods to their relevant input part leads to more effective search space pruning. And third, to make a necessary minimality check of candidate answer sets more efficient by exploiting early external evaluation calls. As this check usually accounts for a large share of the total runtime, optimization is here particularly important. We further present an experimental evaluation of an implementation of a novel HEX-algorithm that incorporates these enhancements using a benchmark suite. Our results demonstrate a clear efficiency gain over the state-of-the-art HEX-solver for the benchmarks, and provide insights regarding the most effective combinations of solver configurations.

AIJ Journal 2018 Journal Article

LARS: A Logic-based framework for Analytic Reasoning over Streams

  • Harald Beck
  • Minh Dao-Tran
  • Thomas Eiter

The increasing availability of streaming data has accelerated advances in information processing tools that no longer store data for static querying but push information to consumers as soon as it becomes available. Stream processing aims at providing languages and tools for data that changes at a high rate. To cope with the volume of data, query languages often extend existing approaches for static data by means of window operators that return snapshots of recent data. However, the semantics of these languages are often given only informally or operationally, which makes their analysis and comparison difficult. A formal means to express the declarative semantics of such systems seems to be missing. This lack of theory is of particular relevance for the emerging research in stream reasoning which shifts the focus from throughput to higher expressiveness. To fill this gap, we present LARS, a Logic-based framework for Analytic Reasoning over Streams. At its core, LARS formulas extend propositional logic with generic window operators and additional controls to handle temporal information. On top of this, LARS programs extend Answer Set Programming (ASP) with rich stream reasoning capabilities; the latter can be exploited to target AI applications in a streaming context, such as diagnosis, configuration or planning. Specifically, we study in this article the computational complexity of LARS formulas and programs, their relationship to Linear Temporal Logic (LTL) and the well-known Continuous Query Language (CQL). Furthermore, we discuss the modeling capabilities of LARS in notes on the SPARQL extensions C-SPARQL and CQELS, and on the interval-based approach of the complex event processing language ETALIS. We finally briefly touch available implementations, in particular, the recent prototype engines Laser and Ticker that aim for high throughput and high expressiveness, respectively. Notably, both engines specify their semantics in LARS, indicating the desired flexibility of the framework and its potential as stream reasoning language itself, which is further explored in other works.

KR Conference 2018 Conference Paper

Omission-based Abstraction for Answer Set Programs

  • Zeynep G. Saribatur
  • Thomas Eiter

Abstraction is a well-known approach to reduce program complexity by over-approximating the problem with a deliberate loss of information. It has not been considered so far in the context of Answer Set Programming, a convenient tool for problem solving. In this paper, we introduce a method to automatically abstract ground ASP programs that preserves their structure by reducing the vocabulary. Such an abstraction makes it possible to generate partial answer set candidates, which can help with the approximation of reasoning. Faithful (non-spurious) abstractions may be used to represent the projection of answer sets and to guide solvers in answer set construction. In order to deal with the unavoidably introduced spurious answer sets, we employ an ASP debugging approach to help with the refinement of the abstraction. We investigate the usage of such an abstraction to obtain explanations of unsatisfiable programs as a show case.

IJCAI Conference 2018 Conference Paper

Preference-Based Inconsistency Management in Multi-Context Systems (Extended Abstract)

  • Thomas Eiter
  • Antonius Weinzierl

Establishing information exchange between existing knowledge-based systems can lead to devastating inconsistency. Automatic resolution of inconsistency often is unsatisfactory, because any modification of the information flow may lead to bad or even dangerous conclusions. Methods to identify and select preferred repairs of inconsistency are thus needed. In this work, we leverage the expressive power and generality of Multi-Context Systems (MCS), a formalism for information exchange, to select most preferred repairs, by use of a meta-reasoning transformation. As for computational complexity, finding preferred repairs is not higher than the base case; finding most-preferred repairs is higher, yet worst-case optimal.

KR Conference 2018 Conference Paper

Reasoning with Justifiable Exceptions in Contextual Hierarchies

  • Loris Bozzato
  • Luciano Serafini
  • Thomas Eiter

The problem of representing and reasoning with context dependent knowledge has been of certain interest since the beginning of AI. Among the available solutions, we consider the Contextualized Knowledge Repository (CKR) framework. In CKR applications it is often useful to reason over a hierarchical organization of contexts: however, the CKR model is not able to represent exception handling in the inheritance of knowledge across contexts. In this paper we develop a proposal, based on a recent principle for exception handling for inheritance in description logics, that allows CKRs with context dependent defeasible axioms which can be overridden by more specific local knowledge. We provide an alternative semantics for a core (simple) version of CKR that copes with contextual defeasible axioms, and we define a datalog translation generating programs that are complete w. r. t. instance checking under the proposed semantics in the case of ranked contextual hierarchies.

IJCAI Conference 2017 Conference Paper

Evaluating Epistemic Negation in Answer Set Programming (Extended Abstract)

  • Yi-Dong Shen
  • Thomas Eiter

Epistemic negation 'not' along with default negation 'neg' plays a key role in knowledge representation and nonmonotonic reasoning. However, the existing approaches behave not satisfactorily in that they suffer from the problems of unintended world views due to recursion through the epistemic modal operator K or M ( K F and M F are shorthands for (neg not F) and (not neg F), respectively). In this paper we present a general approach to epistemic negation which is free of unintended world views and thus offers a solution to the long-standing problem of epistemic specifications which were introduced by Gelfond 1991 over two decades ago.

IJCAI Conference 2017 Conference Paper

Lazy-Grounding for Answer Set Programs with External Source Access

  • Thomas Eiter
  • Tobias Kaminski
  • Antonius Weinzierl

HEX-programs enrich the well-known Answer Set Programming (ASP) paradigm. In HEX, problems are solved using nonmonotonic logic programs with bidirectional access to external sources. ASP evaluation is traditionally based on grounding the input program first, but recent advances in lazy-grounding make the latter also interesting for HEX, as the grounding bottleneck of ASP may be avoided. We explore this issue and present a new evaluation algorithm for HEX-programs based on lazy-grounding solving for ASP. Nonmonotonic dependencies and value invention (i. e. , import of new constants) from external sources make an efficient solution nontrivial. However, illustrative benchmarks show a clear advantage of the new algorithm for grounding-intense programs, which is a new perspective to make HEX more suitable for real-world application needs.

JAIR Journal 2017 Journal Article

Preference-Based Inconsistency Management in Multi-Context Systems

  • Thomas Eiter
  • Antonius Weinzierl

Multi-Context Systems (MCS) are a powerful framework for interlinking possibly heterogeneous, autonomous knowledge bases, where information can be exchanged among knowledge bases by designated bridge rules with negation as failure. An acknowledged issue with MCS is inconsistency that arises due to the information exchange. To remedy this problem, inconsistency removal has been proposed in terms of repairs, which modify bridge rules based on suitable notions for diagnosis of inconsistency. In general, multiple diagnoses and repairs do exist; this leaves the user, who arguably may oversee the inconsistency removal, with the task of selecting some repair among all possible ones. To aid in this regard, we extend the MCS framework with preference information for diagnoses, such that undesired diagnoses are filtered out and diagnoses that are most preferred according to a preference ordering are selected. We consider preference information at a generic level and develop meta-reasoning techniques on diagnoses in MCS that can be exploited to reduce preference-based selection of diagnoses to computing ordinary subset-minimal diagnoses in an extended MCS. We describe two meta-reasoning encodings for preference orders: the first is conceptually simple but may incur an exponential blowup. The second is increasing only linearly in size and based on duplicating the original MCS. The latter requires nondeterministic guessing if a subset-minimal among all most preferred diagnoses should be computed. However, a complexity analysis of diagnoses shows that this is worst-case optimal, and that in general, preferred diagnoses have the same complexity as subset-minimal ordinary diagnoses. Furthermore, (subset-minimal) filtered diagnoses and (subset-minimal) ordinary diagnoses also have the same complexity.

IJCAI Conference 2017 Conference Paper

Streaming Multi-Context Systems

  • Minh Dao-Tran
  • Thomas Eiter

Multi-Context Systems (MCS) are a powerful framework to interlink heterogeneous knowledge bases under equilibrium semantics. Recent extensions of MCS to dynamic data settings either abstract from computing time, or abandon a dynamic equilibrium semantics. We thus present streaming MCS, which have a run-based semantics that accounts for asynchronous, distributed execution and supports obtaining equilibria for contexts in cyclic exchange (avoiding infinite loops); moreover, they equip MCS with native stream reasoning features. Ad-hoc query answering is NP-complete while prediction is PSpace-complete in relevant settings (but undecidable in general); tractability results for suitable restrictions.

JAIR Journal 2016 Journal Article

Computing Repairs of Inconsistent DL-Programs over EL Ontologies

  • Thomas Eiter
  • Michael Fink
  • Daria Stepanova

Description Logic (DL) ontologies and non-monotonic rules are two prominent Knowledge Representation (KR) formalisms with complementary features that are essential for various applications. Nonmonotonic Description Logic (DL) programs combine these formalisms thus providing support for rule-based reasoning on top of DL ontologies using a well-defined query interface represented by so-called DL-atoms. Unfortunately, interaction of the rules and the ontology may incur inconsistencies such that a DL-program lacks answer sets (i.e., models), and thus yields no information. This issue is addressed by recently defined repair answer sets, for computing which an effective practical algorithm was proposed for DL-Lite A ontologies that reduces a repair computation to constraint matching based on so-called support sets. However, the algorithm exploits particular features of DL-Lite A and can not be readily applied to repairing DL-programs over other prominent DLs like EL. compared to DL-Lite A, in EL support sets may neither be small nor only few support sets might exist, and completeness of the algorithm may need to be given up when the support information is bounded. We thus provide an approach for computing repairs for DL-programs over EL ontologies based on partial (incomplete) support families. The latter are constructed using datalog query rewriting techniques as well as ontology approximation based on logical difference between EL-terminologies. We show how the maximal size and number of support sets for a given DL-atom can be estimated by analyzing the properties of a support hypergraph, which characterizes a relevant set of TBox axioms needed for query derivation. We present a declarative implementation of the repair approach and experimentally evaluate it on a set of benchmark problems; the promising results witness practical feasibility of our repair approach.

AIJ Journal 2016 Journal Article

Data repair of inconsistent nonmonotonic description logic programs

  • Thomas Eiter
  • Michael Fink
  • Daria Stepanova

Combining Description Logic (DL) ontologies and nonmonotonic rules has gained increasing attention in the past decade, due to the growing range of applications of DLs. A well-known proposal for such a combination are non-monotonic DL-programs, which support rule-based reasoning on top of DL ontologies in a loose coupling, using a well-defined query interface. However, inconsistency may easily arise as a result of the interaction of the rules and the ontology, such that no answer set (i. e. , model) of a DL-program exists; this makes the program useless. To overcome this problem, we present a framework for repairing inconsistencies in DL-programs by exchanging formulas of an ontology formulated in DL- Lite A, which is a prominent DL that allows for tractable reasoning. Viewing the data part of the ontology as a source of inconsistency, we define program repairs and repair answer sets based on them. We analyze the complexity of the notion, and we extend an algorithm for evaluating DL-programs to compute repair answer sets, under optional selection of preferred repairs that satisfy additional constraints. The algorithm induces a generalized ontology repair problem, in which the entailment respectively non-entailment of queries to the ontology, subject to possible updates, must be achieved by a data change. While this problem is intractable in general, we identify several tractable classes of preferred repairs that are useful in practice. For the class of deletion repairs among them, we optimize the algorithm by reducing query evaluation to constraint matching, based on the novel concept of support set, which roughly speaking is a portion of the data from which entailment of an ontology query follows. Our repair approach is implemented within an answer set program system, using a declarative method for repair computation. An experimental evaluation on a suite of benchmark problems shows the effectiveness of our approach and promising results, both regarding performance and quality of the obtained repairs. While we concentrate on DL- Lite A ontologies, our notions extend to other DLs, for which more general computation approaches may be used.

AIJ Journal 2016 Journal Article

Domain expansion for ASP-programs with external sources

  • Thomas Eiter
  • Michael Fink
  • Thomas Krennwallner
  • Christoph Redl

Answer set programming (ASP) is a popular approach to declarative problem solving which for broader usability has been equipped with external source access. The latter may introduce new constants to the program (known as value invention), which can lead to infinite answer sets and non-termination; to prevent this, syntactic safety conditions on programs are common which considerably limit expressiveness (in particular, recursion). We present liberal domain-expansion (lde) safe programs, a novel generic class of ASP programs with external source access and value invention that enjoy finite restrictability, i. e. , equivalence to a finite ground version. They use term bounding functions as a parametric notion of safety, which can be instantiated with syntactic, semantic or combined safety criteria; this empowers us to generalize and integrate many other notions of safety from the literature, and modular composition of criteria makes future extensions easy. Furthermore, we devise a grounding algorithm for lde-safe programs which in contrast to traditional algorithms can ground any such program directly without the need for program decomposition. While we present our approach on top of a proposed formalism in order to make the formalization precise, the general concepts carry over to related formalisms and important special cases as well. An experimental evaluation of lde-safety on various applications confirms the practicability of our approach.

IJCAI Conference 2016 Conference Paper

Equivalent Stream Reasoning Programs

  • Harald Beck
  • Minh Dao-Tran
  • Thomas Eiter

The emerging research field of stream reasoning faces the challenging trade-off between expressiveness of query programs and data throughput. For optimizing programs methods are needed to tell whether two programs are equivalent. Towards providing practical reasoning techniques on streams, we consider LARS programs, which is a powerful extension of Answer Set Programming (ASP) for stream reasoning that supports windows on streams for discarding information. We define different notions of equivalence between such programs and give semantic characterizations in terms of models. We show how a practically relevant fragment can be alternatively captured usingHere-and-There models, yielding an extension of equilibrium semantics of ASP to this class of programs. Finally, we characterize the computational complexity of deciding the considered equival encerelations.

AIJ Journal 2016 Journal Article

Evaluating epistemic negation in answer set programming

  • Yi-Dong Shen
  • Thomas Eiter

Epistemic negation not along with default negation ¬ plays a key role in knowledge representation and nonmonotonic reasoning. However, the existing epistemic approaches such as those by Gelfond [13, 15, 14], Truszczynski [33] and Kahl et al. [18] behave not satisfactorily in that they suffer from the problems of unintended world views due to recursion through the epistemic modal operator K or M ( K F and M F are shorthands for ¬ not F and not ¬ F, respectively). In this paper we present a new approach to handling epistemic negation which is free of unintended world views and thus offers a solution to the long-standing problem of epistemic specifications which were introduced by Gelfond [13] over two decades ago. We consider general logic programs consisting of rules of the form H ← B, where H and B are arbitrary first-order formulas possibly containing epistemic negation, and define a general epistemic answer set semantics for general logic programs by introducing a novel program transformation and a new definition of world views in which we apply epistemic negation to minimize the knowledge in world views. The general epistemic semantics is applicable to extend any existing answer set semantics, such as those defined in [26, 27, 32, 1, 8, 12, 29], with epistemic negation. For illustration, we extend FLP answer set semantics of Faber et al. [8] for general logic programs with epistemic negation, leading to epistemic FLP semantics. We also extend the more restrictive well-justified FLP semantics of Shen et al. [29], which is free of circularity for default negation, to an epistemic well-justified semantics. We consider the computational complexity of epistemic FLP semantics and show that for a propositional program Π with epistemic negation, deciding whether Π has epistemic FLP answer sets is Σ 3 p -complete and deciding whether a propositional formula F is true in Π under epistemic FLP semantics is Σ 4 p -complete in general, but has lower complexity for logic programs that match normal epistemic specifications, where the complexity of world view existence and query evaluation drops by one level in the polynomial hierarchy.

JELIA Conference 2016 Conference Paper

Exploiting Contextual Knowledge for Hybrid Classification of Visual Objects

  • Thomas Eiter
  • Tobias Kaminski

Abstract We consider the problem of classifying visual objects in a scene by exploiting the semantic context. For this task, we define hybrid classifiers (HC) that combine local classifiers with context constraints, and can be applied to collective classification problems (CCPs) in general. Context constraints are represented by weighted ASP constraints using object relations. To integrate probabilistic information provided by the classifier and the context, we embed our encoding in the formalism \(LP^{MLN}\), and show that an optimal labeling can be efficiently obtained from the corresponding \(LP^{MLN}\) program by employing an ordinary ASP solver. Moreover, we describe a methodology for constructing an HC for a CCP, and present experimental results of applying an HC for object classification in indoor and outdoor scenes, which exhibit significant improvements in terms of accuracy compared to using only a local classifier.

IJCAI Conference 2016 Conference Paper

Exploiting Partial Assignments for Efficient Evaluation of Answer Set Programs with External Source Access

  • Thomas Eiter
  • Tobias Kaminski
  • Christoph Redl
  • Antonius Weinzierl

Answer Set Programming (ASP) is a well-known problem solving approach based on nonmonotonic logic programs and efficient solvers. HEX-programs extend ASP with external atoms for access to arbitrary external information. In this work, we extend the evaluation principles of external atoms to partial assignments, lift nogood learning to this setting, and introduce a variant of nogood minimization. This enables external sources to guide the search for answer sets akin to theory propagation. Our benchmark experiments demonstrate a clear improvement in efficiency over the state-of-the-art HEX-solver.

KR Conference 2016 Conference Paper

Generalized Consistent Query Answering under Existential Rules

  • Thomas Eiter
  • Thomas Lukasiewicz
  • Livia Predoiu

Previous work has proposed consistent query answering as a way to resolve inconsistencies in ontologies. In these approaches to consistent query answering, however, only inconsistencies due to errors in the underlying database are considered. In this paper, we additionally assume that ontological axioms may be erroneous, and that some database atoms and ontological axioms may not be removed to resolve inconsistencies. This problem is especially well-suited in debugging mappings between distributed ontologies. We define two different semantics, one where ontological axioms as a whole are ignored to resolve an inconsistency, and one where only some of their instances are ignored. We then give a precise picture of the complexity of consistent query answering under these two semantics when ontological axioms are encoded as different classes of existential rules. In the course of this, we also close two open complexity problems in standard consistent query answering under existential rules.

JELIA Conference 2016 Conference Paper

Reactive Policies with Planning for Action Languages

  • Zeynep G. Saribatur
  • Thomas Eiter

Abstract Action languages are an important family of formalisms to represent action domains in a declarative manner and to reason about them. For this reason, the behavior of an agent in an environment may be governed by policies which take such action domain descriptions into account. In this paper, we describe a formal semantics for describing policies that express a reactive behavior for an agent, and connect our framework with the representation power of action languages. In this framework, we mitigate the large state spaces by employing the notion of indistinguishability, and combine components that are efficient for describing reactivity such as target establishment and (online) planning. Our representation allows one to analyze the flow of executing the given reactive policy, and lays foundations for verifying properties of policies. Additionally, the flexibility of the representation opens a range of possibilities for designing behaviors.

JELIA Conference 2016 Conference Paper

Rule-based Stream Reasoning for Intelligent Administration of Content-Centric Networks

  • Harald Beck
  • Bruno Bierbaumer
  • Minh Dao-Tran
  • Thomas Eiter
  • Hermann Hellwagner
  • Konstantin Schekotihin

Abstract Content-Centric Networking (CCN) research addresses the mismatch between the modern usage of the Internet and its outdated architecture. Importantly, CCN routers use various caching strategies to locally cache content frequently requested by end users. However, it is unclear which content shall be stored and when it should be replaced. In this work, we employ novel techniques towards intelligent administration of CCN routers. Our approach allows for autonomous switching between existing strategies in response to changing content request patterns using rule-based stream reasoning framework LARS which extends Answer Set Programming for streams. The obtained possibility for flexible router configuration at runtime allows for faster experimentation and may result in significant performance gains, as shown in our evaluation.

AIJ Journal 2016 Journal Article

Semi-equilibrium models for paracoherent answer set programs

  • Giovanni Amendola
  • Thomas Eiter
  • Michael Fink
  • Nicola Leone
  • João Moura

The answer set semantics may assign a logic program to model, due to logical contradiction or unstable negation, which is caused by cyclic dependency of an atom on its negation. While logical contradictions can be handled with traditional techniques from paraconsistent reasoning, instability requires other methods. We consider resorting to a paracoherent semantics, in which 3-valued interpretations are used where a third truth value besides true and false expresses that an atom is believed true. This is at the basis of the semi-stable model semantics, which was defined using a program transformation. In this paper, we give a model-theoretic characterization of semi-stable models, which makes the semantics more accessible. Motivated by some anomalies of semi-stable model semantics with respect to basic epistemic properties, we propose an amendment that satisfies these properties. The latter has both a transformational and a model-theoretic characterization that reveals it as a relaxation of equilibrium logic, the logical reconstruction of answer set semantics, and is thus called the semi-equilibrium model semantics. We consider refinements of this semantics to respect modularity in the rules, based on splitting sets, the major tool for modularity in modeling and evaluating answer set programs. In that, we single out classes of canonical models that are amenable for customary bottom-up evaluation of answer set programs, with an option to switch to a paracoherent mode when lack of an answer set is detected. A complexity analysis of major reasoning tasks shows that semi-equilibrium models are harder than answer sets (i. e. , equilibrium models), due to a global minimization step for keeping the gap between true and believed true atoms as small as possible. Our results contribute to the logical foundations of paracoherent answer set programming, which gains increasing importance in inconsistency management, and at the same time provide a basis for algorithm development and integration into answer set solvers.

IJCAI Conference 2015 Conference Paper

Answer Update for Rule-Based Stream Reasoning

  • Harald Beck
  • Minh Dao-Tran
  • Thomas Eiter

Stream reasoning is the task of continuously deriving conclusions on streaming data. To get results instantly one evaluates a query repeatedly on recent data chunks selected by window operators. However, simply recomputing results from scratch is impractical for rule-based reasoning with semantics similar to Answer Set Programming, due to the trade-off between complexity and data throughput. To address this problem, we present a method to efficiently update models of a rule set. In particular, we show how an answer stream (model) of a LARS program can be incrementally adjusted to new or outdated input by extending truth maintenance techniques. We obtain in this way a means towards practical rule-based stream reasoning with nonmonotonic negation, various window operators and different forms of temporal reference.

JAIR Journal 2015 Journal Article

Distributed Evaluation of Nonmonotonic Multi-context Systems

  • Minh Dao-Tran
  • Thomas Eiter
  • Michael Fink
  • Thomas Krennwallner

Multi-context Systems (MCSs) are a formalism for systems consisting of knowledge bases (possibly heterogeneous and non-monotonic) that are interlinked via bridge rules, where the global system semantics emerges from the local semantics of the knowledge bases (also called “contexts”) in an equilibrium. While MCSs and related formalisms are inherently targeted for distributed set- tings, no truly distributed algorithms for their evaluation were available. We address this short- coming and present a suite of such algorithms which includes a basic algorithm DMCS, an ad- vanced version DMCSOPT that exploits topology-based optimizations, and a streaming algorithm DMCS-STREAMING that computes equilibria in packages of bounded size. The algorithms be- have quite differently in several respects, as experienced in thorough experimental evaluation of a system prototype. From the experimental results, we derive a guideline for choosing the appropriate algorithm and running mode in particular situations, determined by the parameter settings.

AAAI Conference 2015 Conference Paper

LARS: A Logic-Based Framework for Analyzing Reasoning over Streams

  • Harald Beck
  • Minh Dao-Tran
  • Thomas Eiter
  • Michael Fink

The recent rise of smart applications has drawn interest to logical reasoning over data streams. Different query languages and stream processing/reasoning engines were proposed. However, due to a lack of theoretical foundations, the expressivity and semantics of these diverse approaches were only informally discussed. Towards clear specifications and means for analytic study, a formal framework is needed to characterize their semantics in precise terms. We present LARS, a Logic-based framework for Analyzing Reasoning over Streams, i. e. , a rule-based formalism with a novel window operator providing a flexible mechanism to represent views on streaming data. We establish complexity results for central reasoning tasks and show how the prominent Continuous Query Language (CQL) can be captured. Moreover, the relation between LARS and ETALIS, a system for complex event processing is discussed. We thus demonstrate the capability of LARS to serve as the desired formal foundation for expressing and analyzing different semantic approaches to stream processing/reasoning and engines.

JELIA Conference 2014 Conference Paper

Computing Repairs for Inconsistent DL-programs over EL Ontologies

  • Thomas Eiter
  • Michael Fink 0001
  • Daria Stepanova 0001

Abstract DL-programs couple nonmonotonic logic programs with DL- ontologies through queries in a loose way which may lead to inconsistency, i. e. , lack of an answer set. Recently defined repair answer sets remedy this. In particular, for \(DL-Lite_{\mathcal{A}}\) ontologies, the computation of deletion repair answer sets can effectively be reduced to constraint matching based on so-called support sets. Here we consider the problem for DL-programs over \(\mathcal{EL}\) ontologies. This is more challenging than adopting a suitable notion of support sets and their computation. Compared to \(DL-Lite_{\mathcal{A}}\), support sets may neither be small nor few, and completeness may need to be given up in favor of sound repair computation on incomplete support information. We provide such an algorithm and discuss partial support set computation, as well as a declarative implementation. Preliminary experiments show a very promising potential of the partial support set approach.

AAAI Conference 2014 Conference Paper

Exploiting Support Sets for Answer Set Programs with External Evaluations

  • Thomas Eiter
  • Michael Fink
  • Christoph Redl
  • Daria Stepanova

Answer set programs (ASP) with external evaluations are a declarative means to capture advanced applications. However, their evaluation can be expensive due to external source accesses. In this paper we consider HEX-programs that provide external atoms as a bidirectional interface to external sources and present a novel evaluation method based on support sets, which informally are portions of the input to an external atom that will determine its output for any completion of the partial input. Support sets allow one to shortcut the external source access, which can be completely eliminated. This is particularly attractive if a compact representation of suitable support sets is efficiently constructible. We discuss some applications with this property, among them description logic programs over DL-Lite ontologies, and present experimental results showing that support sets can significantly improve efficiency.

AIJ Journal 2014 Journal Article

Finding explanations of inconsistency in multi-context systems

  • Thomas Eiter
  • Michael Fink
  • Peter Schüller
  • Antonius Weinzierl

Interlinking knowledge sources to enable information exchange is basic means to build enriched knowledge-based systems, which gains importance with the spread of the Internet. Inconsistency, however, arises easily in such systems, which is not least due to their heterogeneity, but also due to their independent design. This makes developing methods for consistency management of such systems a pressing issue. An important aspect is that in many relevant cases, the information at individual sources may not be amenable to change in order to resolve inconsistency, like in case of autonomous management of the sources. We thus aim at analyzing inconsistency of a system by means of the interlinking of sources and changes thereof. More concretely, we consider the powerful framework of Multi-Context Systems, in which decentralized and heterogeneous system parts interact via (possibly nonmonotonic) bridge rules for information exchange. Nonmonotonicity and potential cyclic dependencies pose additional challenges that call for suitable methods of inconsistency analysis. We thus provide two approaches for explaining inconsistency, which both characterize inconsistency in terms of bridge rules, but in different ways: by pointing out rules which need to be altered for restoring consistency, and by finding combinations of rules which cause inconsistency. We show duality and modularity properties of these notions, give precise complexity characterizations, and provide algorithms for their computation, which have been implemented in a prototype, by means of so-called hex-programs. Our results provide a basis for inconsistency management in heterogeneous knowledge systems which, different from and orthogonal to other works, explicitly addresses the knowledge interlinks in order to restore consistency.

AIJ Journal 2014 Journal Article

FLP answer set semantics without circular justifications for general logic programs

  • Yi-Dong Shen
  • Kewen Wang
  • Thomas Eiter
  • Michael Fink
  • Christoph Redl
  • Thomas Krennwallner
  • Jun Deng

The answer set semantics presented by Faber et al. [27] has been widely used to define so called FLP answer sets for different types of logic programs. However, it was recently observed that when being extended from normal to more general classes of logic programs, this approach may produce answer sets with circular justifications that are caused by self-supporting loops. The main reason for this behavior is that the FLP answer set semantics is not fully constructive by a bottom up construction of answer sets. In this paper, we overcome this problem by enhancing the FLP answer set semantics with a level mapping formalism such that every answer set I can be built by fixpoint iteration of a one-step provability operator (more precisely, an extended van Emden–Kowalski operator for the FLP reduct f Π I ). This is inspired by the fact that under the standard answer set semantics, each answer set I of a normal logic program Π is obtainable by fixpoint iteration of the standard van Emden–Kowalski one-step provability operator for the Gelfond–Lifschitz reduct Π I, which induces a level mapping. The enhanced FLP answer sets, which we call well-justified FLP answer sets, are thanks to the level mapping free of circular justifications. As a general framework, the well-justified FLP answer set semantics applies to logic programs with first-order formulas, logic programs with aggregates, description logic programs, hex-programs etc. , provided that the rule satisfaction is properly extended to such general logic programs. We study in depth the computational complexity of FLP and well-justified FLP answer sets for general classes of logic programs. Our results show that the level mapping does not increase the worst-case complexity of FLP answer sets. Furthermore, we describe an implementation of the well-justified FLP answer set semantics, and report about an experimental evaluation, which indicates a potential for performance improvements by the level mapping in practice.

JELIA Conference 2014 Conference Paper

Modular Paracoherent Answer Sets

  • Giovanni Amendola
  • Thomas Eiter
  • Nicola Leone

Abstract The answer set semantics may assign a logic program no model due to classic contradiction or cyclic negation. The latter can be remedied by resorting to a paracoherent semantics given by semi-equilibrium ( SEQ ) models, which are 3-valued interpretations that generalize the logical reconstruction of answer sets given by equilibrium models. While SEQ -models have interesting properties, they miss modularity in the rules, such that a natural modular (bottom up) evaluation of programs is hindered. We thus refine SEQ -models using splitting sets, the major tool for modularity in modeling and evaluating answer set programs. We consider canonical models that are independent of any particular splitting sequence from a class of splitting sequences, and present two such classes whose members are efficiently recognizable. Splitting SEQ -models does not make reasoning harder, except for deciding model existence in presence of constraints (without constraints, split SEQ -models always exist).

ECAI Conference 2014 Conference Paper

Towards Practical Deletion Repair of Inconsistent DL-programs

  • Thomas Eiter
  • Michael Fink 0001
  • Daria Stepanova 0001

Nonmonotonic Description Logic (DL-) programs couple nonmonotonic logic programs with DL-ontologies through queries in a loose way which may lead to inconsistency, i. e. , lack of an answer set. Recently defined repair answer sets remedy this but a straightforward computation method lacks practicality. We present a novel evaluation algorithm for deletion repair answer sets based on support sets, which reduces evaluation of DL-LiteAontology queries to constraint matching. This leads to significant performance gains towards inconsistency management in practice.

IJCAI Conference 2013 Conference Paper

Data Repair of Inconsistent DL-Programs

  • Thomas Eiter
  • Michael Fink
  • Daria Stepanova

Nonmonotonic Description Logic (DL) programs support rule-based reasoning on top of Description Logic ontologies, using a well-defined query interface. However, the interaction of the rules and the ontology may cause inconsistency such that no answer set (i. e. model) exists. We thus consider repairing DL-programs, i. e. , changing formulas to obtain consistency. Viewing the data part of the ontology as the source of inconsistency, we define program repairs and repair answer sets based on changes to it. We analyze the complexity of the notion, and we extend an algorithm for evaluating DL-programs to compute repair answer sets, under optional selection of preferred repairs. The extension involves a generalized ontology repair problem, in which the entailment and non-entailment of sets of queries with updates to the ontology must be achieved. While this is intractable in general, we identify for the Description Logic DL-LiteA some tractable classes of preferred repairs that are useful in practice.

AAAI Conference 2013 Conference Paper

Liberal Safety for Answer Set Programs with External Sources

  • Thomas Eiter
  • Michael Fink
  • Thomas Krennwallner
  • Christoph Redl

Answer set programs with external source access may introduce new constants that are not present in the program, which is known as value invention. As naive value invention leads to programs with infinite grounding and answer sets, syntactic safety criteria are imposed on programs. However, traditional criteria are in many cases unnecessarily strong and limit expressiveness. We present liberal domain-expansion (de-) safe programs, a novel generic class of answer set programs with external source access that has a finite grounding and allows for value invention. De-safe programs use so-called term bounding functions as a parameter for modular instantiation with concrete—e. g. , syntactic or semantic or both—safety criteria. This ensures extensibility of the approach in the future. We provide concrete instances of the framework and develop an operator that can be used for computing a finite grounding. Finally, we discuss related notions of safety from the literature, and show that our approach is strictly more expressive.

JELIA Conference 2012 Conference Paper

Exploiting Unfounded Sets for HEX-Program Evaluation

  • Thomas Eiter
  • Michael Fink 0001
  • Thomas Krennwallner
  • Christoph Redl
  • Peter Schüller

Abstract HEX programs extend logic programs with external computations through external atoms, whose answer sets are the minimal models of the Faber-Leone-Pfeifer-reduct. As already reasoning from Horn programs with nonmonotonic external atoms of polynomial complexity is on the second level of the polynomial hierarchy, answer set checking needs special attention; simply computing reducts and searching for smaller models does not scale well. We thus extend an approach based on unfounded sets to HEX and integrate it in a Conflict Driven Clause Learning framework for HEX program evaluation. It reduces the check to a search for unfounded sets, which is more efficiently implemented as a SAT problem. We give a basic encoding for HEX and show optimizations by additional clauses. Experiments show that the new approach significantly decreases runtime.

LPAR Conference 2012 Conference Paper

Forgetting for Defeasible Logic

  • Grigoris Antoniou
  • Thomas Eiter
  • Kewen Wang 0001

Abstract The concept of forgetting has received significant interest in artificial intelligence recently. Informally, given a knowledge base, we may wish to forget about (or discard) some redundant parts (such as atoms, predicates, concepts, etc) but still preserve the consequences for certain forms of reasoning. In nonmonotonic reasoning, so far forgetting has been studied only in the context of extension based approaches, mainly answer-set programming. In this paper forgetting is studied in the context of defeasible logic, which is a simple, efficient and sceptical nonmonotonic reasoning approach.

JELIA Conference 2012 Conference Paper

Inconsistency Management for Traffic Regulations: Formalization and Complexity Results

  • Harald Beck
  • Thomas Eiter
  • Thomas Krennwallner

Abstract Smart Cities is a vision driven by the availability of governmental data that fosters many challenging applications. One of them is the management of inconsistent traffic regulations, i. e. , the handling of inconsistent traffic signs and measures in urban areas such as wrong sign posting, or errors in data acquisition in traffic sign administration software. We investigate such inconsistent traffic scenarios and formally model traffic regulations using a logic-based approach for traffic signs and measures, and logical theories describe emerging conflicts on a graph-based street model. Founded on this model, we consider major reasoning tasks including consistency testing, diagnosis, and repair, and we analyze their computational complexity for different logical representation formalisms. Our results provide a basis for an ongoing implementation of the approach.

JELIA Conference 2012 Conference Paper

OMiGA: An Open Minded Grounding On-The-Fly Answer Set Solver

  • Minh Dao-Tran
  • Thomas Eiter
  • Michael Fink 0001
  • Gerald Weidinger
  • Antonius Weinzierl

Abstract We present a new solver for Answer-Set Programs whose main features include grounding on-the-fly and readiness for use in solving distributed answer-set programs. The solver is implemented in Java and uses an underlying Rete network for propagation. Initial experimental results show the benefit of using Rete for this purpose, but also exhibit the need for learning in the presence of grounding on-the-fly.

AAAI Conference 2012 Conference Paper

Query Rewriting for Horn-SHIQ Plus Rules

  • Thomas Eiter
  • Magdalena Ortiz
  • Mantas Simkus
  • Trung-Kien Tran
  • Guohui Xiao

Query answering over Description Logic (DL) ontologies has become a vibrant field of research. Efficient realizations often exploit database technology and rewrite a given query to an equivalent SQL or Datalog query over a database associated with the ontology. This approach has been intensively studied for conjunctive query answering in the DL-Lite and EL families, but is much less explored for more expressive DLs and queries. We present a rewriting-based algorithm for conjunctive query answering over Horn-SHIQ ontologies, possibly extended with recursive rules under limited recursion as in DL+log. This setting not only subsumes both DL-Lite and EL, but also yields an algorithm for answering (limited) recursive queries over Horn-SHIQ ontologies (an undecidable problem for full recursive queries). A prototype implementation shows its potential for applications, as experiments exhibit efficient query answering over full Horn-SHIQ ontologies and benign downscaling to DL-Lite, where it is competitive with comparable state of the art systems.

IJCAI Conference 2011 Conference Paper

Managed Multi-Context Systems

  • Gerhard Brewka
  • Thomas Eiter
  • Michael Fink
  • Antonius Weinzierl

Multi-context systems (MCS) are a powerful framework for interlinking heterogeneous knowledge sources. They model the flow of information among different reasoning components (called contexts) in a declarative way, using so-called bridge rules, where contexts and bridge rules may be nonmonotonic. We considerably generalize MCS to managed MCS (mMCS): while the original bridge rules can only add information to contexts, our generalization allows arbitrary operations on context knowledge bases to be freely defined, e. g. , deletion or revision operators. The paper motivates and introduces the generalized framework and presents several interesting instances. Furthermore, we consider inconsistency management in mMCS and complexity issues.

JELIA Conference 2010 Conference Paper

Decomposition of Distributed Nonmonotonic Multi-Context Systems

  • Seif El-Din Bairakdar
  • Minh Dao-Tran
  • Thomas Eiter
  • Michael Fink 0001
  • Thomas Krennwallner

Abstract Multi-Context Systems (MCS) are formalisms that enable the interlinkage of single knowledge bases, called contexts, via bridge rules. Recently, a fully distributed algorithm for evaluating heterogeneous, nonmonotonic MCS was described in [7]. In this paper, we continue this line of work and present a decomposition technique for MCS which analyzes the topology of an MCS. It applies pruning techniques to get economically small representations of context dependencies. Orthogonal to this, we characterize minimal interfaces for information exchange between contexts, such that data transmissions can be minimized. We then present a novel evaluation algorithm that operates on a query plan which is compiled with topology pruning and interface minimization. The effectiveness of the optimization techniques is demonstrated by a prototype implementation, which uses an off-the-shelf SAT solver and shows encouraging experimental results.

KR Conference 2010 Conference Paper

Distributed Nonmonotonic Multi-Context Systems

  • Minh Dao-Tran
  • Thomas Eiter
  • Michael Fink
  • Thomas Krennwallner

We present a distributed algorithm for computing equilibria of heterogeneous nonmonotonic multi-context systems (MCS). The algorithm can be parametrized to compute only partial equilibria, which can be used for reasoning tasks like query answering or satisfiability checking that need only partial information and not whole belief states. Furthermore, caching is employed to cut redundant solver calls. As a showcase, we instantiate the MCS framework with answer set program contexts. To characterize equilibria of such MCS, we develop notions of loop formulas that enable reductions to the classical satisfiability problem (SAT). Notably, loop formulas for bridge rules between contexts and for the local contexts can be combined to a uniform encoding of an MCS into a (distributed) SAT instance. As a consequence, we can use SAT solvers for belief set building. We demonstrate this approach by an experimental prototype implementation, which uses an off-the-shelf SAT solver.

KR Conference 2010 Conference Paper

Finding Explanations of Inconsistency in Multi-Context Systems

  • Thomas Eiter
  • Michael Fink
  • Peter Schüller
  • Antonius Weinzierl

We provide two approaches for explaining inconsistency in multi-context systems, where decentralized and heterogeneous system parts interact via nonmonotonic bridge rules. Inconsistencies arise easily in such scenarios, and nonmonotonicity calls for specific methods of inconsistency analysis. Both our approaches characterize inconsistency in terms of involved bridge rules: either by pointing out rules which need to be altered for restoring consistency, or by finding combinations of rules which cause inconsistency. We show duality and modularity properties, give precise complexity characterizations, and provide algorithms for computation using HEXprograms. Our results form a basis for inconsistency management in heterogeneous knowledge integration systems.

KR Conference 2010 Conference Paper

Paracoherent Answer Set Programming

  • Thomas Eiter
  • Michael Fink
  • Joao Moura

We study the problem of reasoning from incoherent answer set programs, i. e., from logic programs that do not have an answer set due to cyclic dependencies of an atom from its default negation. As a starting point we consider so-called semi-stable models which have been developed for this purpose building on a program transformation, called epistemic transformation. We give a model-theoretic characterization of this semantics, considering pairs of two-valued interpretations of the original program, rather than resorting to its epistemic transformation. Moreover, we show some anomalies of semi-stable semantics with respect to basic epistemic properties and propose an alternative semantics satisfying these properties. In addition to a model-theoretic and a transformational characterization of the alternative semantics, we prove precise complexity results for main reasoning tasks under both semantics. (1) Every (consistent) answer set of a program corresponds to a model (answer set coverage). (2) If a (consistent) answer set exists for a program, then all models correspond to an answer set (congruence). (3) If a program has a classical model, then it has a model (classical coherence). Widely-known semantics, such as 3-valued stable models (Przymusinski 1991), L-stable models (Eiter, Leone, and Saccà 1997), revised stable models (Pereira and Pinto 2005), regular models (You and Yuan 1994), and pstable models (Osorio, Ramı́rez, and Carballido 2008), satisfy only part of these requirements (see the Discussion section for further semantics and more details). Semi-stable models (Sakama and Inoue 1995) however, satisfy all three properties and thus are the prevailing paracoherent semantics. Despite the model-theoretic nature of ASP, semi-stable models have been defined by means of a program transformation, called epistemic transformation. A semantic characterization in the style of equilibrium models for answer sets (Pearce and Valverde 2008) is still missing. We address this problem and make the following main contributions.

JELIA Conference 2010 Conference Paper

Preference-Based Inconsistency Assessment in Multi-Context Systems

  • Thomas Eiter
  • Michael Fink 0001
  • Antonius Weinzierl

Abstract Resolving inconsistency in knowledge-integration systems is a major issue, especially when interlinking heterogeneous, autonomous sources. The latter can be done using a multi-context system, also in presence of non-monotonicity. Recent work considered diagnosis and explanation of inconsistency in such systems in terms of faulty information exchange. To discriminate between different solutions, we consider inconsistency assessment using preference. We present means to a) filter undesired diagnoses b) select the most preferred ones given an arbitrary preference order and c) use CP-nets for efficient selection. Furthermore, we show how to incorporate the assessment into a Multi-Context System by a transformational approach. In a range of settings, the complexity does not increase compared to the basic case and key properties like decentralized information exchange and information hiding are preserved.

AAAI Conference 2010 Conference Paper

Space Efficient Evaluation of ASP Programs with Bounded Predicate Arities

  • Thomas Eiter
  • Wolfgang Faber
  • Mushthofa Mushthofa

Answer Set Programming (ASP) has been deployed in many applications, thanks to the availability of efficient solvers. Most programs encountered in practice have an important property: Their predicate arities are bounded by a constant, and in this case it is known that the relevant computations can be done using polynomial space. However, all competitive ASP systems rely on grounding, due to which they may use exponential space for these programs. We present three evaluation methods that respect the polynomial space bound and a generic framework architecture for realization. Experimental results for a prototype implementation indicate that the methods are effective. They show not only benign space consumption, but interestingly also good runtime compared to some state of the art ASP solvers.

JELIA Conference 2010 Conference Paper

The DMCS Solver for Distributed Nonmonotonic Multi-Context Systems

  • Seif El-Din Bairakdar
  • Minh Dao-Tran
  • Thomas Eiter
  • Michael Fink 0001
  • Thomas Krennwallner

Abstract The DMCS system is an implementation of the equilibrium semantics for heterogeneous and nonmonotonic multi-context systems (MCS) [3], which feature contexts with heterogeneous and possibly nonmonotonic logics. Each context in an MCS comprises of two parts: a local knowledge base and a set of bridge rules that can access the beliefs of other contexts and add new information to the knowledge base. In this setting, contexts are loosely coupled, and may model distributed information linkage applications; thus it is natural to have a system that allows for the distributed evaluation of MCS.

JELIA Conference 2010 Conference Paper

The mcs-ie System for Explaining Inconsistency in Multi-Context Systems

  • Markus Bögl
  • Thomas Eiter
  • Michael Fink 0001
  • Peter Schüller

Abstract The Multi-Context System Inconsistency Explainer allows for evaluation of semantics and explanation of inconsistencies in systems where heterogeneous knowledge bases are linked via nonmonotonic rules. The implementation is based on the dlvhex tool, which is an extension of answer set programming with external atoms and higher order features.

ECAI Conference 2010 Conference Paper

Tractable Reasoning with DL-Programs over Datalog-rewritable Description Logics

  • Stijn Heymans
  • Thomas Eiter
  • Guohui Xiao 0001

The deployment of KR formalisms to the Web has created the need for formalisms that combine heterogeneous knowledge bases. Nonmonotonic dl-programs provide a loose integration of Description Logic (DL) ontologies and Logic Programming (LP) rules with negation, where a rule engine can query an ontology with a native DL reasoner. However, even for tractable dl-programs, the overhead of an external DL reasoner might be considerable. To remedy this, we consider Datalog-rewritable DL ontologies, i. e. , ones that can be rewritten to Datalog programs, such that dl-programs can be reduced to Datalog ¬, i. e, Datalog with negation, under well-founded semantics. To illustrate this framework, we consider several Datalog-rewritable DLs. Besides fragments of the tractable OWL 2 Profiles, we also present [Lscr ][Dscr ][Lscr ] + as an interesting DL that is tractable while it has some expressive constructs. Our results enable the usage of DBLP technology to reason efficiently with dl-programs in presence of negation and recursion, as a basis for advanced applications.

AIJ Journal 2010 Journal Article

Updating action domain descriptions

  • Thomas Eiter
  • Esra Erdem
  • Michael Fink
  • Ján Senko

Incorporating new information into a knowledge base is an important problem which has been widely investigated. In this paper, we study this problem in a formal framework for reasoning about actions and change. In this framework, action domains are described in an action language whose semantics is based on the notion of causality. Unlike the formalisms considered in the related work, this language allows straightforward representation of non-deterministic effects and indirect effects of (possibly concurrent) actions, as well as state constraints; therefore, the updates can be more general than elementary statements. The expressivity of this formalism allows us to study the update of an action domain description with a more general approach compared to related work. First of all, we consider the update of an action description with respect to further criteria, for instance, by ensuring that the updated description entails some observations, assertions, or general domain properties that constitute further constraints that are not expressible in an action description in general. Moreover, our framework allows us to discriminate amongst alternative updates of action domain descriptions and to single out a most preferable one, based on a given preference relation possibly dependent on the specified criteria. We study semantic and computational aspects of the update problem, and establish basic properties of updates as well as a decomposition theorem that gives rise to a divide and conquer approach to updating action descriptions under certain conditions. Furthermore, we study the computational complexity of decision problems around computing solutions, both for the generic setting and for two particular preference relations, viz. set-inclusion and weight-based preference. While deciding the existence of solutions and recognizing solutions are PSPACE-complete problems in general, the problems fall back into the polynomial hierarchy under restrictions on the additional constraints. We finally discuss methods to compute solutions and approximate solutions (which disregard preference). Our results provide a semantic and computational basis for developing systems that incorporate new information into action domain descriptions in an action language, in the presence of additional constraints.

IJCAI Conference 2009 Conference Paper

  • Diego Calvanese
  • Thomas Eiter
  • Magdalena Ortiz

Reasoning over complex queries in the DLs underlying OWL 2 is of importance in several application domains. We provide decidability and (tight) upper bounds for the problem of checking entailment and containment of positive regular path queries under various combinations of constructs used in such expressive DLs; specifically: regular expressions and (safe) Booleans over roles, and allowing for the combination of any two constructs among inverse roles, qualified number restrictions, and nominals. Our results carry over also to the DLs of the SR family, and thus have a direct impact on OWL 2.

IJCAI Conference 2009 Conference Paper

  • Thomas Eiter
  • Carsten Lutz
  • Magdalena Ortiz
  • Mantas Simkus

We study the computational complexity of conjunctive query answering w. r. t. ontologies formulated in fragments of the description logic SHIQ. Our main result is the identification of two new sources of complexity: the combination of transitive roles and role hierarchies which results in 2-EXPTIMEhardness, and transitive roles alone which result in CO-NEXPTIME-hardness. These bounds complement the existing result that inverse roles make query answering in SHIQ 2-EXPTIME-hard. We also show that conjunctive query answering with transitive roles, but without inverse roles and role hierarchies, remains in EXPTIME if the ABox is tree-shaped.

IJCAI Conference 2009 Conference Paper

  • Thomas Eiter
  • Mantas Simkus

Current Answer Set Programming (ASP) solvers largely build on logic programming without function symbols. This limitation makes ASP decidable, but greatly complicates the modeling of indefinite time, recursive data structures (e. g. , lists), and infinite processes and objects in general. Recent research thus aims at finding decidable fragments of ASP with function symbols and studying their complexity. We identify bidirectional ASP programs as an expressive such fragment that is useful, e. g. , for reasoning about actions involving both the future and the past. We tightly characterize the computational complexity of bidirectional programs and of some of their subclasses, addressing the main reasoning tasks. Our results also imply that the recently introduced FDNC programs can be extended by inverse predicates while retaining decidability, but computational costs are unavoidably higher.

IJCAI Conference 2009 Conference Paper

  • Thomas Eiter
  • Michael Fink
  • Thomas Krennwallner

We present a method to decompose a declarative knowledge base, given by a logic program under Answer Set Semantics with access to external sources. It overcomes the ineffectiveness of current methods due to a lack of structural information about these sources, viewed as black boxes, by exploiting independency information in accesses to them. To this end, we develop a generic notion of domain independence that allows to restrict the evaluation domain and, as a consequence, to prune unnecessary dependency assumptions between atoms. This leads to increased decomposability; we demonstrate this by an evaluation method for HEX-programs based on program rewriting, which may yield large performance gains. While developed for a particular formalism, the notions and ideas of this paper might be adapted to related formalisms as well.

AIJ Journal 2008 Journal Article

Combining answer set programming with description logics for the Semantic Web

  • Thomas Eiter
  • Giovambattista Ianni
  • Thomas Lukasiewicz
  • Roman Schindlauer
  • Hans Tompits

We propose a combination of logic programming under the answer set semantics with the description logics SHIF ( D ) and SHOIN ( D ), which underly the Web ontology languages OWL Lite and OWL DL, respectively. To this end, we introduce description logic programs (or dl-programs), which consist of a description logic knowledge base L and a finite set P of description logic rules (or dl-rules). Such rules are similar to usual rules in nonmonotonic logic programs, but they may also contain queries to L, possibly under default negation, in their bodies. They allow for building rules on top of ontologies but also, to a limited extent, building ontologies on top of rules. We define a suite of semantics for various classes of dl-programs, which conservatively extend the standard semantics of the respective classes and coincide with it in absence of a description logic knowledge base. More concretely, we generalize positive, stratified, and arbitrary normal logic programs to dl-programs, and define a Herbrand model semantics for them. We show that they have similar properties as ordinary logic programs, and also provide fixpoint characterizations in terms of (iterated) consequence operators. For arbitrary dl-programs, we define answer sets by generalizing Gelfond and Lifschitz's notion of a transform, leading to a strong and a weak answer set semantics, which are based on reductions to the semantics of positive dl-programs and ordinary positive logic programs, respectively. We also show how the weak answer sets can be computed utilizing answer sets of ordinary normal logic programs. Furthermore, we show how some advanced reasoning tasks for the Semantic Web, including different forms of closed-world reasoning and default reasoning, as well as DL-safe rules, can be realized on top of dl-programs. Finally, we give a precise picture of the computational complexity of dl-programs, and we describe efficient algorithms and a prototype implementation of dl-programs which is available on the Web.

KR Conference 2008 Conference Paper

Embedding Approaches to Combining Rules and Ontologies into Autoepistemic Logic

  • Jos de Bruijn
  • Thomas Eiter
  • Hans Tompits

The combination of rules and ontologies has a central role in the ongoing development of the Semantic Web. In previous work, autoepistemic logic (AEL) was advocated as a uniform host formalism to study different such combinations, enabling comparisons on a common basis. In this paper, we continue this line of research and investigate different embeddings of major proposals to combine rules and ontologies into first-order autoepistemic logic (FO-AEL). In particular, we present embeddings for dl-programs, r-hybrid knowledge bases, and hybrid MKNF knowledge bases, which are representatives of different combination types. We study the embeddings in the context of FO-AEL under the standard-names assumption, but we also discuss variants using the any- and all-names semantics. Our results provide interesting insights into the properties of the discussed combination formalisms.

AAAI Conference 2008 Conference Paper

Error Classification in Action Descriptions: A Heuristic Approach

  • Thomas Eiter

Action languages allow to formally represent and reason about actions in a highly declarative manner. In recent work, revision and management of conflicts for domain descriptions in such languages wrt. semantic integrity constraints have been considered, in particular their reconciliation. However, merely ad hoc tests and methods have been presented to aid the user in analyzing and correcting a flawed description. We go beyond this and present a methodology on top of such tests for identifying a possible error, which works in several stages. The issue of such a methodology for action languages is novel and has not been addressed before, but is important for building tools and engineering action descriptions in practice.

AIJ Journal 2008 Journal Article

Maintenance goals of agents in a dynamic environment: Formulation and policy construction

  • Chitta Baral
  • Thomas Eiter
  • Marcus Bjäreland
  • Mutsumi Nakamura

The notion of maintenance often appears in the AI literature in the context of agent behavior and planning. In this paper, we argue that earlier characterizations of the notion of maintenance are not intuitive to characterize the maintenance behavior of certain agents in a dynamic environment. We propose a different characterization of maintenance and distinguish it from earlier notions such as stabilizability. Our notion of maintenance is more sensitive to a good-natured agent which struggles with an “adversary” environment, which hinders her by unforeseeable events to reach her goals (not in principle, but in case). It has a parameter k, referring to the length of non-interference (from exogenous events) needed to maintain a goal; we refer to this notion as k-maintainability. We demonstrate the notion on examples, and address the important but non-trivial issue of efficient construction of maintainability control functions. We present an algorithm which in polynomial time constructs a k-maintainable control function, if one exists, or tells that no such control is possible. Our algorithm is based on SAT Solving, and employs a suitable formulation of the existence of k-maintainable control in a fragment of SAT which is tractable. For small k (bounded by a constant), our algorithm is linear time. We then give a logic programming implementation of our algorithm and use it to give a standard procedural algorithm, and analyze the complexity of constructing k-maintainable controls, under different assumptions such as k = 1, and states described by variables. On the one hand, our work provides new concepts and algorithms for maintenance in dynamic environment, and on the other hand, a very fruitful application of computational logic tools. We compare our work with earlier works on control synthesis from temporal logic specification and relate our work to Dijkstra's notion of self-stabilization and related notions in distributed computing.

ECAI Conference 2008 Conference Paper

New Results for Horn Cores and Envelopes of Horn Disjunctions

  • Thomas Eiter
  • Kazuhisa Makino

We provide a characterization of Horn cores for formulas in conjunctive normal form (CNF) and, based on it, a novel algorithm for computing Horn cores of disjunctions of Horn CNFs that has appealing properties (e. g. , it is polynomial for a bounded disjunction). Furthermore, we show that recognizing the Horn envelope of a disjunction of two Horn CNFs is intractable, and that computing a compact Horn CNF for it (that is irredundant and prime) is not feasible in polynomial total time unless P=NP; this answers an open problem.

JELIA Conference 2008 Conference Paper

Query Answering in the Description Logic Horn-

  • Thomas Eiter
  • Georg Gottlob
  • Magdalena Ortiz 0001
  • Mantas Simkus

Abstract We provide an ExpTime algorithm for answering conjunctive queries (CQs) in Horn - \(\mathcal{SHIQ}\), a Horn fragment of the well-known Description Logic \(\mathcal{SHIQ}\) underlying the OWL-Lite standard. The algorithm employs a domino system for model representation, which is constructed via a worst-case optimal tableau algorithm for Horn - \(\mathcal{SHIQ}\); the queries are answered by reasoning over the domino system. Our algorithm not only shows that CQ answering in Horn - \(\mathcal{SHIQ}\) is not harder than satisfiability testing, but also that it is polynomial in data complexity, making Horn - \(\mathcal{SHIQ}\) an attractive expressive Description Logic.

LPAR Conference 2008 Invited Paper

Reasoning Using Knots

  • Thomas Eiter
  • Magdalena Ortiz 0001
  • Mantas Simkus

Abstract The deployment of Description Logics (DLs) and Answer Set Programming (ASP), which are well-known knowledge representation and reasoning formalisms, to a growing range of applications has created the need for novel reasoning algorithms and methods. Recently, knots have been introduced as a tool to facilitate reasoning tasks in extensions of ASP with functions symbols. They were then also fruitfully applied for query answering in Description Logics, hinging on the forest-shaped model property of knowledge bases. This paper briefly reviews the knot idea at a generic level and recalls some of the results obtained with them. It also discusses features of knots and relations to other reasoning techniques, and presents issues for further research.

AIJ Journal 2008 Journal Article

Semantic forgetting in answer set programming

  • Thomas Eiter
  • Kewen Wang

The notion of forgetting, also known as variable elimination, has been investigated extensively in the context of classical logic, but less so in (nonmonotonic) logic programming and nonmonotonic reasoning. The few approaches that exist are based on syntactic modifications of a program at hand. In this paper, we establish a declarative theory of forgetting for disjunctive logic programs under answer set semantics that is fully based on semantic grounds. The suitability of this theory is justified by a number of desirable properties. In particular, one of our results shows that our notion of forgetting can be entirely captured by classical forgetting. We present several algorithms for computing a representation of the result of forgetting, and provide a characterization of the computational complexity of reasoning from a logic program under forgetting. As applications of our approach, we present a fairly general framework for resolving conflicts in inconsistent knowledge bases that are represented by disjunctive logic programs, and we show how the semantics of inheritance logic programs and update logic programs from the literature can be characterized through forgetting. The basic idea of the conflict resolution framework is to weaken the preferences of each agent by forgetting certain knowledge that causes inconsistency. In particular, we show how to use the notion of forgetting to provide an elegant solution for preference elicitation in disjunctive logic programming.

IJCAI Conference 2007 Conference Paper

  • Thomas Eiter
  • Esra Erdem
  • Wolfgang Faber

Reversing actions is the following problem: After executing a sequence of actions, which sequence of actions brings the agent back to the state just before this execution (an action reversal). Notably, this problem is different from a vanilla planning problem since the state we have to get back to is in general unknown. It emerges, for example, if an agent needs to find out which action sequences are undoable, and which ones are committed choices. It has applications related to plan execution and monitoring in nondeterministic domains, such as recovering from a failed execution by partially undoing the plan, dynamically switching from one executed plan to another, or restarting plans. We formalize action reversal in a logic-based action1 framework and characterize its computational complexity. Since unsurprisingly, the problem is intractable in general, we present a knowledge compilation approach that constructs offline a reverse plan library for efficient (in some cases, linear time) online computation of action reversals. Our results for the generic framework can be easily applied for expressive action languages such as C+ or K.

IJCAI Conference 2007 Conference Paper

  • Thomas Eiter
  • Michael Fink
  • Hans Tompits
  • Stefan Woltran

Recent research in nonmonotonic logic programming under the answer-set semantics focuses on different notions of program equivalence. However, previous results do not address the important classes of stratified programs and its subclass of acyclic (i. e. , recursion-free) programs, although they are recognized as important tools for knowledge representation and reasoning. In this paper, we consider such programs, possibly augmented with constraints. Our results show that in the propositional setting, where reasoning is well-known to be polynomial, deciding strong and uniform equivalence is as hard as for arbitrary normal logic programs (and thus coNP-complete), but is polynomial in some restricted cases. Non-ground programs behave similarly. However, exponential lower bounds already hold for small programs (i. e. , with constantly many rules). In particular, uniform equivalence is undecidable even for small Horn programs plus a single negative constraint.

IJCAI Conference 2007 Conference Paper

  • Jos de Bruijn
  • Thomas Eiter
  • Axel Polleres
  • Hans Tompits$

In the context of the Semantic Web, several approaches to the combination of ontologies, given in terms of theories of classical first-order logic, and rule bases have been proposed. They either cast rules into classical logic or limit the interaction between rules and ontologies. Autoepistemic logic (AEL) is an attractive formalism which allows to overcome these limitations, by serving as a uniform host language to embed ontologies and nonmonotonic logic programs into it. For the latter, so far only the propositional setting has been considered. In this paper, we present several embeddings of normal and disjunctive non-ground logic programs under the stable-model semantics into first-order AEL, and compare them in combination with classical theories, with respect to stable expansions and autoepistemic consequences. Our results reveal differences and correspondences of the embeddings and provide a useful guidance in the choice of a particular embedding for knowledge combination.

LPAR Conference 2007 Conference Paper

\mathbb FDNC: Decidable Non-monotonic Disjunctive Logic Programs with Function Symbols

  • Mantas Simkus
  • Thomas Eiter

Abstract Current Answer Set Programming systems are built on non-monotonic logic programs without function symbols; as well-known, they lead to high undecidability in general. However, function symbols are highly desirable for various applications, which challenges to find meaningful and decidable fragments of this setting. We present the class \(\mathbb{FDNC}\) of logic programs which allows for function symbols, disjunction, non-monotonic negation under answer set semantics, and constraints, while still retaining the decidability of the standard reasoning tasks. Thanks to these features, they are a powerful formalism for rule-based modeling of applications with potentially infinite processes and objects, which allows also for common-sense reasoning. We show that consistency checking and brave reasoning are ExpTime -complete in general, but have lower complexity for restricted fragments, and outline worst-case optimal reasoning procedures for these tasks. Furthermore, we present a finite representation of the possibly infinitely many infinite stable models of an \(\mathbb{FDNC}\) program, which may be exploited for knowledge compilation purposes.

JELIA Conference 2006 Conference Paper

A Tool for Answering Queries on Action Descriptions

  • Thomas Eiter
  • Michael Fink 0001
  • Ján Senko

Abstract Action languages [1] are a formal tool for reasoning about actions, where an agent’s knowledge about a domain in question is represented by a declarative action description that consists of logical formulas.

JELIA Conference 2006 Conference Paper

An Implementation for Recognizing Rule Replacements in Non-ground Answer-Set Programs

  • Thomas Eiter
  • Patrick Traxler
  • Stefan Woltran

Abstract Answer-set programming (ASP) has emerged as an important paradigm for declarative problem solving, and provides a host for many different application domains on the basis of nonmonotonic logic programs. The increasing popularity in ASP has raised also the interest in semantic comparisons of programs in ASP [3, 4], which are nowadays recognized as a theoretical basis for program optimization, where equivalencepreserving modifications are of primary interest; in particular, rewriting rules which allow to perform a local change in a program are important. Many such rules have been considered in the propositional setting (cf. , e. g. , [1, 6]) but just recently have been extended to the practicably important case of non-ground programs [2].

AIJ Journal 2006 Journal Article

Causes and explanations in the structural-model approach: Tractable cases

  • Thomas Eiter
  • Thomas Lukasiewicz

This paper continues the research on the computational aspects of Halpern and Pearl's causes and explanations in the structural-model approach. To this end, we first explore how an instance of deciding weak cause can be reduced to an equivalent instance in which irrelevant variables in the (potential) weak cause and the causal model are removed, which extends previous work by Hopkins. We then present a new characterization of weak cause for a certain class of causal models in which the causal graph over the endogenous variables has the form of a directed chain of causal subgraphs, called decomposable causal graph. Furthermore, we also identify two important subclasses in which the causal graph over the endogenous variables forms a directed tree and more generally a directed chain of layers, called causal tree and layered causal graph, respectively. By combining the removal of irrelevant variables with this new characterization of weak cause, we then obtain techniques for deciding and computing causes and explanations in the structural-model approach, which can be done in polynomial time under suitable restrictions. This way, we obtain several tractability results for causes and explanations in the structural-model approach. To our knowledge, these are the first explicit ones. They are especially useful for dealing with structure-based causes and explanations in first-order reasoning about actions, which produces large causal models that are naturally layered through the time line, and thus have the structure of layered causal graphs. Furthermore, an important feature of the tractable cases for causal trees and layered causal graphs is that they can be recognized efficiently, namely in linear time. Finally, by extending the new characterization of weak cause, we obtain similar techniques for computing the degrees of responsibility and blame, and hence also novel tractability results for structure-based responsibility and blame.

JELIA Conference 2006 Conference Paper

Comparing Action Descriptions Based on Semantic Preferences

  • Thomas Eiter
  • Esra Erdem 0001
  • Michael Fink 0001
  • Ján Senko

Abstract We consider action domain descriptions whose meaning can be represented by transition diagrams. We introduce several semantic measures to compare such action descriptions, based on preferences over possible states of the world and preferences over some given conditions (observations, assertions, etc.) about the domain, as well as the probabilities of possible transitions. This preference information is used to assemble a weight which is assigned to an action description. As an application of this approach, we study the problem of updating action descriptions with respect to some given conditions. With a semantic approach based on preferences, not only, for some problems, we get more plausible solutions, but also, for some problems without any solutions due to too strong conditions, we can identify which conditions to relax to obtain a solution. We conclude with computational issues, and characterize the complexity of computing the semantic measures.

AAAI Conference 2006 Conference Paper

Forgetting and Conflict Resolving in Disjunctive Logic Programming

  • Thomas Eiter

We establish a declarative theory of forgetting for disjunctive logic programs. The suitability of this theory is justified by a number of desirable properties. In particular, one of our results shows that our notion of forgetting is completely captured by the classical forgetting. A transformation-based algorithm is also developed for computing the result of forgetting. We also provide an analysis of computational complexity. As an application of our approach, a fairly general framework for resolving conflicts in inconsistent knowledge bases represented by disjunctive logic programs is defined. The basic idea of our framework is to weaken the preferences of each agent by forgetting certain knowledge that causes inconsistency. In particular, we show how to use the notion of forgetting to provide an elegant solution for preference elicitation in disjunctive logic programming.

TCS Journal 2006 Journal Article

Reasoning under minimal upper bounds in propositional logic

  • Thomas Eiter
  • Georg Gottlob

Reasoning from the minimal models of a theory, as fostered by circumscription, is in the area of Artificial Intelligence an important method to formalize common sense reasoning. However, as it appears, minimal models may not always be suitable to capture the intuitive semantics of a knowledge base, aiming intuitively at an exclusive interpretation of disjunctions of atoms, i. e. , if possible then assign at most one of the disjuncts the value true in a model. In this paper, we consider an approach which is more lenient and also admits non-minimal models, such that inclusive interpretation of disjunction also may be possible in cases where minimal model reasoning adopts an exclusive interpretation. Nonetheless, in the spirit of minimization, the approach aims at including only positive information that is necessary. This is achieved by closing the set of admissible models of a theory under minimal upper bounds in the set of models of the theory, which we refer to as curbing. We demonstrate this method on some examples, and investigate its semantical and computational properties. We establish that curbing is an expressive reasoning method, since the main reasoning tasks are shown to be PSPACE-complete. On the other hand, we also present cases of lower complexity, and in particular cases in which the complexity is located, just as for ordinary minimal model reasoning, at the second level of the Polynomial Hierarchy, or even below.

KR Conference 2006 Conference Paper

Replacements in Non-Ground Answer-Set Programming

  • Thomas Eiter
  • Michael Fink
  • Hans Tompits
  • Patrick Traxler
  • Stefan Woltran

In this paper, we propose a formal framework for specifying rule replacements in nonmonotonic logic programs within the answer-set programming paradigm. Of particular interest are replacement schemas retaining specific notions of equivalence, among them the prominent notions of strong and uniform equivalence, which have been introduced as theoretical tools for program optimization and verification. We derive some general properties of the replacement framework with respect to these notions of equivalence. Moreover, we generalize results about particular replacement schemas which have been established for ground programs to the non-ground case. Finally, we report a number of complexity results which address the problem of deciding how hard it is to apply a replacement to a given program. Our results provide an important step towards the development of effective optimization methods for non-ground answer-set programming, an issue which has not been addressed much so far.

ECAI Conference 2006 Conference Paper

Resolving Conflicts in Action Descriptions

  • Thomas Eiter
  • Esra Erdem 0001
  • Michael Fink 0001
  • Ján Senko

We study resolving conflicts between an action description and a set of conditions (possibly obtained from observations), in the context of action languages. In this formal framework, the meaning of an action description can be represented by a transition diagram—a directed graph whose nodes correspond to states and whose edges correspond to transitions describing action occurrences. This allows us to characterize conflicts by means of states and transitions of the given action description that violate some given conditions. We introduce a basic method to resolve such conflicts by modifying the action description, and discuss how the user can be supported in obtaining more preferred solutions. For that, we identify helpful questions the user may ask (e. g. , which specific parts of the action description cause a conflict with some given condition), and we provide answers to them using properties of action descriptions and transition diagrams. Finally, we discuss the computational complexity of these questions in terms of related decision problems.

IJCAI Conference 2005 Conference Paper

A Uniform Integration of Higher-Order Reasoning and External Evaluations in Answer-Set Programming

  • Thomas Eiter
  • Giovambattista Ianni
  • Roman Schindlauer
  • Hans

We introduce HEX programs, which are nonmonotonic logic programs admitting higher-order atoms as well as external atoms, and we extend the wellknown answer-set semantics to this class of programs. Higher-order features are widely acknowledged as useful for performing meta-reasoning, among other tasks. Furthermore, the possibility to exchange knowledge with external sources in a fully declarative framework such as Answer-Set Programming (ASP) is nowadays important, in particular in view of applications in the Semantic Web area. Through external atoms, HEX programs can model some important extensions to ASP, and are a useful KR tool for expressing various applications. Finally, complexity and implementation issues for a preliminary prototype are discussed.

IJCAI Conference 2005 Conference Paper

On Solution Correspondences in Answer-Set Programming

  • Thomas Eiter
  • Hans Tompits
  • Stefan

We introduce a general framework for specifying program correspondence under the answer-set semantics. The framework allows to define different kinds of equivalence notions, including previously defined notions like strong and uniform equivalence, in which programs are extended with rules from a given context, and correspondence is determined by means of a binary relation. In particular, refined equivalence notions based on projected answer sets can be defined within this framework, where not all parts of an answer set are of relevance. We study general characterizations of inclusion and equivalence problems, introducing novel semantical structures. Furthermore, we deal with the issue of determining counterexamples for a given correspondence problem, and we analyze the computational complexity of correspondence checking.

AAAI Conference 2005 Conference Paper

Strong and Uniform Equivalence in Answer-Set Programming: Characterizations and Complexity Results for the Non-Ground Case

  • Thomas Eiter
  • Hans Tompits

Recent research in nonmonotonic logic programming under the answer-set semantics studies different notions of equivalence. In particular, strong and uniform equivalence are proposed as useful tools for optimizing (parts of) a logic program. While previous research mainly addressed propositional (i. e. , ground) programs, we deal here with the more general case of non-ground programs, and provide semantical characterizations capturing the essence of equivalence, generalizing the concepts of SE-models and UE-models, respectively, as originally introduced for propositional programs. We show that uniform equivalence is undecidable, and we give decidability results and precise complexity bounds for strong equivalence (thereby correcting a previous complexity bound for strong equivalence from the literature) as well as for uniform equivalence for finite vocabularies.

IJCAI Conference 2005 Conference Paper

Updating Action Domain Descriptions

  • Thomas Eiter
  • Esra Erdem
  • Michael Fink
  • Ján

How can an intelligent agent update her knowledge base about an action domain, relative to some conditions (possibly obtained from earlier observations)? We study this question in a formal framework for reasoning about actions and change, in which the meaning of an action domain description can be represented by a directed graph whose nodes correspond to states and whose edges correspond to action occurrences. We define the update of an action domain description in this framework, and show among other results that a solution to this problem can be obtained by a divide-and-conquer approach in some cases. We also introduce methods to compute a solution and an approximate solution to this problem, and analyze the computational complexity of these problems. Finally, we discuss techniques to improve the quality of solutions.

ICAPS Conference 2004 Conference Paper

A Polynomial Time Algorithm for Constructing k-Maintainable Policies

  • Chitta Baral
  • Thomas Eiter

In this paper we present a polynomial time algorithm for constructing k-maintainable policies (Nakamura, Baral, and Bjareland 2000). Our algorithm, in polynomial time, constructs a k-maintainable control policy, if one exists, or tells that no such policy is possible. Our algorithm is based on SAT Solving, and employs a suitable formulation of the existence of k-maintainable control in a fragment of SAT which is tractable. We then give a logic programming implementation of our algorithm and use it to give a standard procedural algorithm. We then present several complexity results about constructing k- maintainable controls, under different assumptions such as k = 1, and compact representation.

KR Conference 2004 Conference Paper

Combining Answer Set Programming with Description Logics for the Semantic Web

  • Thomas Eiter
  • Thomas Lukasiewicz
  • Roman Schindlauer
  • Hans Tompits

Towards the integration of rules and ontologies in the Semantic Web, we propose a combination of logic programming under the answer set semantics with the description logics SHIF(D) and SHOIN(D), which underly the Web ontology languages OWL Lite and OWL DL, respectively. This combination allows for building rules on top of ontologies but also, to a limited extent, building ontologies on top of rules. We introduce description logic programs (dl-programs), which consist of a description logic knowledge base L and a finite set of description logic rules (dl-rules) P. Such rules are similar to usual rules in logic programs with negation as failure, but may also contain queries to L, possibly default negated, in their bodies. We define Herbrand models for dl-programs, and show that satisfiable positive dl-programs have a unique least Herbrand model. More generally, consistent stratified dl-programs can be associated with a unique minimal Herbrand model that is characterized through iterative least Herbrand models. We then generalize the (unique) minimal Herbrand model semantics for positive and stratified dl-programs to a strong answer set semantics for all dl-programs, which is based on a reduction to the least model semantics of positive dl-programs. We also define a weak answer set semantics based on a reduction to the answer sets of ordinary logic programs. Strong answer sets are weak answer sets, and both properly generalize answer sets of ordinary normal logic programs. We then give fixpoint characterizations for the (unique) minimal Herbrand model semantics of positive and stratified dl-programs, and show how to compute these models by finite fixpoint iterations. Furthermore, we give a precise picture of the complexity of deciding strong and weak answer set existence for a dl-program.

KR Conference 2004 Conference Paper

Complexity of Model Checking and Bounded Predicate Arities for Non-ground Answer Set Programming

  • Thomas Eiter
  • Wolfgang Faber
  • Michael Fink
  • Gerald Pfeifer
  • Stefan Woltran

Answer Set Programming has become a host for expressing knowledge representation problems, which reinforces the interest in efficient methods for computing answer sets of a logic program. While for propositional programs, the complexity of this task has been amply studied and is well-understood, less attention has been paid to the case of non-ground programs, which is much more important from a KR language perspective. Existing Answer Set Programming systems employ different representations of models, but the consequences of these representations for answer set computation and reasoning tasks have not been analyzed in detail. In this paper, we present novel complexity results on answer set checking for non-ground programs under two methods for representing answer sets and a variety of syntactic restrictions. In particular, we consider set-based and bitmap-based representations, which are popular in implementations of Answer Set Programming systems. Based on these results, we also derive new complexity results for the canonical reasoning tasks over answer sets, under the assumption that predicate arities are bounded by some constant. Our results imply that in such a setting - which appears to be a reasonable assumption in practice - more efficient implementations than those currently available may be feasible.

AIJ Journal 2004 Journal Article

Complexity results for explanations in the structural-model approach

  • Thomas Eiter
  • Thomas Lukasiewicz

We analyze the computational complexity of Halpern and Pearl's (causal) explanations in the structural-model approach, which are based on their notions of weak and actual cause. In particular, we give a precise picture of the complexity of deciding explanations, α-partial explanations, and partial explanations, and of computing the explanatory power of partial explanations. Moreover, we analyze the complexity of deciding whether an explanation or an α-partial explanation over certain variables exists. We also analyze the complexity of deciding explanations and partial explanations in the case of succinctly represented context sets, the complexity of deciding explanations in the general case of situations, and the complexity of deciding subsumption and equivalence between causal models. All complexity results are derived for the general case, as well as for the restriction to the case of binary causal models, in which all endogenous variables may take only two values. To our knowledge, no complexity results for explanations in the structural-model approach have been derived so far. Our results give insight into the computational structure of Halpern and Pearl's explanations, and pave the way for efficient algorithms and implementations.

LPAR Conference 2004 Conference Paper

Nonmonotonic Description Logic Programs: Implementation and Experiments

  • Thomas Eiter
  • Giovambattista Ianni
  • Roman Schindlauer
  • Hans Tompits

Abstract The coupling of description logic reasoning systems with other reasoning formalisms (possibly over the Web) is becoming an important research issue and calls for advanced methods and algorithms. Recently, several notions of description logic programs have been introduced, combining rule-based semantics with description logics. Among them are nonmonotonic description logic programs (or dl-programs for short) which combine nonmonotonic logic programs with description logics under a generalized version of the answer-set and the well-founded semantics, respectively, which are the predominant semantics for nonmonotonic logic programs. In this paper, we consider some technical issues regarding an efficient implementation for both semantics, which has been realized in a working prototype exploiting the two state-of-art tools DLV and RACER. A major issue in this respect is efficient interfacing between the two reasoning systems at hand, for which we devised special methods. Such methods may fruitfully be used for the implementation of systems of similar nature. Reported experimentation activities with our prototype show that the methods we have developed are effective and are a key for highly optimized nonmonotonic dl-program engines.

KR Conference 2004 Conference Paper

On Eliminating Disjunctions in Stable Logic Programming

  • Thomas Eiter
  • Michael Fink
  • Hans Tompits
  • Stefan Woltran

Disjunction is generally considered to add expressive power to logic programs under the stable model semantics, which have become a popular programming paradigm for knowledge representation and reasoning. However, disjunction is often not really needed, in that an equivalent program without disjunction can be given. In this paper, we consider the question, given a disjunctive logic program, P, under which conditions an equivalent normal (i. e., disjunction-free) logic program Q exists. In fact, we study this problem under different notions of equivalence, viz. for ordinary equivalence (considering the collections of all stable models of the programs) as well as for the more restrictive notions of strong and uniform equivalence. We resolve the issue for propositional programs on which we focus here, and present a simple, appealing semantic criterion from which all disjunctions can be eliminated under strong equivalence. Testing this criterion is coNP-complete, but the class of programs satisfying it has the same complexity as disjunctive logic programs in general. We also show that under ordinary and uniform equivalence, disjunctions can always be eliminated. In all cases, we give constructive methods to achieve this. However, we also provide evidence that disjunctive logic programs are a more succinct knowledge representation formalism than normal logic programs under all these notions of equivalence.

NMR Workshop 2004 Conference Paper

Plan reversals for recovery in execution monitoring

  • Thomas Eiter
  • Esra Erdem 0001
  • Wolfgang Faber 0001

In this paper, we introduce a new method to recover from discrepancies in a general monitoring framework where the agent finds some explanations (points of failure) for discrepancies. According to this method, the agent finds a reverse plan to backtrack to a diagnosed point of failure and subsequently continues with the original plan. This method is appealing given that such a reverse plan is short with respect to the overall plan to be executed. While a reverse plan could be computed online by solving a planning problem, we present a potentially more efficient method: We first build offline a reverse plan library by finding reverse plans for action sequences, and then use this library online to construct reverse plans. The former part is done by reducing the problem of finding pairs of action sequences and reverse plans (of a certain length) to a conformant planning problem; for the latter, we present a polynomial time algorithm. Furthermore, we analyze the complexity of finding reverse plans, and obtain that the presented reduction is reasonable in general.

AIJ Journal 2003 Journal Article

A logic programming approach to knowledge-state planning, II: The system

  • Thomas Eiter
  • Wolfgang Faber
  • Nicola Leone
  • Gerald Pfeifer
  • Axel Polleres

In Part I of this series of papers, we have proposed a new logic-based planning language, called K. This language facilitates the description of transitions between states of knowledge and it is well suited for planning under incomplete knowledge. Nonetheless, K also supports the representation of transitions between states of the world (i. e. , states of complete knowledge) as a special case, proving to be very flexible. In the present Part II, we describe the DLV K planning system, which implements K on top of the disjunctive logic programming system DLV. This novel planning system allows for solving hard planning problems, including secure planning under incomplete initial states (often called conformant planning in the literature), which cannot be solved at all by other logic-based planning systems such as traditional satisfiability planners. We present a detailed comparison of the DLV K system to several state-of-the-art conformant planning systems, both at the level of system features and on benchmark problems. Our results indicate that, thanks to the power of knowledge-state problem encoding, the DLV K system is competitive even with special purpose conformant planning systems, and it often supplies a more natural and simple representation of the planning problems.

CSL Conference 2003 Conference Paper

Generating All Abductive Explanations for Queries on Propositional Horn Theories

  • Thomas Eiter
  • Kazuhisa Makino

Abstract Abduction is a fundamental mode of reasoning, which has taken on increasing importance in Artificial Intelligence (AI) and related disciplines. Computing abductive explanations is an important problem, and there is a growing literature on this subject. We contribute to this endeavor by presenting new results on computing multiple resp. all of the possibly exponentially many explanations of an abductive query from a propositional Horn theory represented by a Horn CNF. Here the issues are whether a few explanations can be generated efficiently and, in case of all explanations, whether the computation is possible in polynomial total time (or output-polynomial time ), i. e. , in time polynomial in the combined size of the input and the output. We explore these issues for queries in CNF and important restrictions thereof. Among the results, we show that computing all explanations for a negative query literal from a Horn CNF is not feasible in polynomial total time unless P = NP, which settles an open issue. However, we show how to compute under restriction to acyclic Horn theories polynomially many explanations in input polynomial time and all explanations in polynomial total time, respectively. Complementing and extending previous results, this draws a detailed picture of the computational complexity of computing multiple explanations for queries on Horn theories.

UAI Conference 2003 Conference Paper

Probabilistic Reasoning about Actions in Nonmonotonic Causal Theories

  • Thomas Eiter
  • Thomas Lukasiewicz

We present the language {m P}{cal C}+ for probabilistic reasoning about actions, which is a generalization of the action language {cal C}+ that allows to deal with probabilistic as well as nondeterministic effects of actions. We define a formal semantics of {m P}{cal C}+ in terms of probabilistic transitions between sets of states. Using a concept of a history and its belief state, we then show how several important problems in reasoning about actions can be concisely formulated in our formalism.

JELIA Conference 2002 Conference Paper

Answer Set Planning under Action Costs

  • Thomas Eiter
  • Wolfgang Faber 0001
  • Nicola Leone
  • Gerald Pfeifer
  • Axel Polleres

Abstract We present \( \mathcal{K}^c \), which extends the declarative planning language \( \mathcal{K} \) by action costs and optimal plans that minimize overall action costs (cheapest plans). As shown, this novel language allows for expressing some nontrivial planning tasks in an elegant way. Furthermore, it flexibly allows for representing planning problems under other optimality criteria as well, such as computing “fastest” plans (with the least number of steps), and refinement combinations of cheap and fast plans. Our experience is encouraging and supports the claim that answer set planning may be a valuable approach to advanced planning systems in which intricate planning tasks can be naturally specified and effectively solved.

UAI Conference 2002 Conference Paper

Causes and Explanations in the Structural-Model Approach: Tractable Cases

  • Thomas Eiter
  • Thomas Lukasiewicz

In this paper, we continue our research on the algorithmic aspects of Halpern and Pearl's causes and explanations in the structural-model approach. To this end, we present new characterizations of weak causes for certain classes of causal models, which show that under suitable restrictions deciding causes and explanations is tractable. To our knowledge, these are the first explicit tractability results for the structural-model approach.

AIJ Journal 2002 Journal Article

Complexity results for structure-based causality

  • Thomas Eiter
  • Thomas Lukasiewicz

We give a precise picture of the computational complexity of causal relationships in Pearl's structural models, where we focus on causality between variables, event causality, and probabilistic causality. As for causality between variables, we consider the notions of causal irrelevance, cause, cause in a context, direct cause, and indirect cause. As for event causality, we analyze the complexity of the notions of necessary and possible cause, and of the sophisticated notions of weak and actual cause by Halpern and Pearl. In the course of this, we also prove an open conjecture by Halpern and Pearl, and establish other semantic results. We then analyze the complexity of the probabilistic notions of probabilistic causal irrelevance, likely causes of events, and occurrences of events despite other events. Moreover, we consider decision and optimization problems involving counterfactual formulas. To our knowledge, no complexity aspects of causal relationships in the structural-model approach have been considered so far, and our results shed light on this issue.

TCS Journal 2002 Journal Article

Decision lists and related Boolean functions

  • Thomas Eiter
  • Toshihide Ibaraki
  • Kazuhisa Makino

We consider Boolean functions represented by decision lists, and study their relationships to other classes of Boolean functions. It turns out that the elementary class of 1-decision lists has interesting relationships to independently defined classes such as disguised Horn functions, read-once functions, nested differences of concepts, threshold functions, and 2-monotonic functions. In particular, 1-decision lists coincide with fragments of the mentioned classes. We further investigate the recognition problem for this class, as well as the extension problem in the context of partially defined Boolean functions (pdBfs). We show that finding an extension of a given pdBf in the class of 1-decision lists is possible in linear time. This improves on previous results. Moreover, we present an algorithm for enumerating all such extensions with polynomial delay.

JELIA Conference 2002 Invited Paper

Hypergraph Transversal Computation and Related Problems in Logic and AI

  • Thomas Eiter
  • Georg Gottlob

Abstract Generating minimal transversals of a hypergraph is an important problem which has many applications in Computer Science. In the present paper, we address this problem and its decisional variant, i. e. , the recognition of the transversal hypergraph for another hypergraph. We survey some results on problems which are known to be related to computing the transversal hypergraph, where we focus on problems in propositional Logic and AI. Some of the results have been established already some time ago, and were announced but their derivation was not widely disseminated. We then address recent developments on the computational complexity of computing resp. recognizing the transversal hypergraph. The precise complexity of these problems is not known to date, and is in fact open for more than 20 years now.

STOC Conference 2002 Conference Paper

New results on monotone dualization and generating hypergraph transversals

  • Thomas Eiter
  • Georg Gottlob
  • Kazuhisa Makino

This paper considers the problem of dualizing a monotone CNF (equivalently, computing all minimal transversals of a hypergraph), whose associated decision problem is a prominent open problem in NP -completeness. We present a number of new polynomial time resp. output-polynomial time results for significant cases, which largely advance the tractability frontier and improve on previous results. Furthermore, we show that duality of two monotone CNFs can be disproved with limited nondeterminism (more precisely, in polynomial time with $O(\log^2 n)$ suitably guessed bits). This result sheds new light on the complexity of this important problem.

AAAI Conference 2002 Conference Paper

On Computing all Abductive Explanations

  • Thomas Eiter

We consider the computation of all respectively a polynomial subset of the explanations of an abductive query from a Horn theory, and pay particular attention to whether the query is a positive or negative letter, the explanation is based on literals from an assumption set, and the Horn theory is represented in terms of formulas or characteristic models. We derive tractability results, one of which refutes a conjecture by Selman and Levesque, as well as intractability results, and furthermore also semi-tractability results in terms of solvability in quasi-polynomial time. Our results complement previous results in the literature, and elucidate the computational complexity of generating the set of explanations.

TCS Journal 2002 Journal Article

On the complexity of data disjunctions

  • Thomas Eiter
  • Helmut Veith

We study the complexity of data disjunctions in disjunctive deductive databases (DDDBs). A data disjunction is a disjunctive ground clause R( c ̄ 1)⋯R( c ̄ k), k⩾2, which is derived from the database such that all atoms in the clause involve the same predicate R. We consider the complexity of deciding existence and uniqueness of a minimal data disjunction, as well as actually computing one, both for propositional (data) and nonground (program) complexity of the database. Our results extend and complement previous results on the complexity of disjunctive databases, and provide newly developed tools for the analysis of the complexity of function computation.

JELIA Conference 2002 Conference Paper

The DLV K Planning System: Progress Report

  • Thomas Eiter
  • Wolfgang Faber 0001
  • Nicola Leone
  • Gerald Pfeifer
  • Axel Polleres

Abstract The knowledge based planning system DLV K implements answer set planning on top of the DLV system [ 1 ]. It is developed at TU Wien and supports the declarative language K [ 2 ], [ 3 ] and its extension K c [ 5 ]. The language K is syntactically similar to the action language C [ 7 ], but semantically closer to answer set programming (by including default negation, for example). K and K c offer the following distinguishing features:

JELIA Conference 2002 Conference Paper

The DLV System

  • Nicola Leone
  • Gerald Pfeifer
  • Wolfgang Faber 0001
  • Francesco Calimeri
  • Tina Dell'Armi
  • Thomas Eiter
  • Georg Gottlob
  • Giovambattista Ianni

Abstract The development of the DLV system has started as a research projectfinanced by FWF (the Austrian Science Funds) in 1996, and has evolved into an international collaboration over the years. Currently, the University of Calabria and TU Wien participate in the project, supported by a scientific-technological collaboration between Italy and Austria. At the time of writing, the latest version of the system has been released on April 12, 2002.

LPAR Conference 2001 Conference Paper

Reasoning about Evolving Nonmonotonic Knowledge Bases

  • Thomas Eiter
  • Michael Fink 0001
  • Giuliana Sabbatini
  • Hans Tompits

Abstract Recently, several approaches to updating knowledge bases modeled as extended logic programs (ELPs) have been introduced, ranging from basic methods to incorporate (sequences of) sets of rules into a logic program, to more elaborate methods which use an update policy for specifying how updates must be incorporated. In this paper, we introduce a framework for reasoning about evolving knowledge bases, which are represented as ELPs and maintained by an update policy. We describe a formal model which captures various update approaches, and define a logical language for expressing properties of evolving knowledge bases. We further investigate the semantical properties of knowledge states with respect to reasoning. In particular, we describe finitary characterizations of the evolution, and derive complexity results for our framework.

JELIA Conference 2000 Invited Paper

Considerations on Updates of Logic Programs

  • Thomas Eiter
  • Michael Fink 0001
  • Giuliana Sabbatini
  • Hans Tompits

Abstract Among others, Alferes et al. (1998) presented an approach for updating logic programs with sets of rules based on dynamic logic programs. We syntactically redefine dynamic logic programs and investigate their semantical properties, looking at them from perspectives such as a belief revision and abstract consequence relation view. Since the approach does not respect minimality of change, we refine its stable model semantics and present minimal stable models and strict stable models. We also compare the update approach to related work, and find that is equivalent to a class of inheritance programs independently defined by Buccafurri et al. (1999).

AIJ Journal 2000 Journal Article

Default reasoning from conditional knowledge bases: Complexity and tractable cases

  • Thomas Eiter
  • Thomas Lukasiewicz

Conditional knowledge bases have been proposed as belief bases that include defeasible rules (also called defaults) of the form “φ→ψ”, which informally read as “generally, if φ then ψ”. Such rules may have exceptions, which can be handled in different ways. A number of entailment semantics for conditional knowledge bases have been proposed in the literature. However, while the semantic properties and interrelationships of these formalisms are quite well understood, about their computational properties only partial results are known so far. In this paper, we fill these gaps and first draw a precise picture of the complexity of default reasoning from conditional knowledge bases: Given a conditional knowledge base KB and a default φ→ψ, does KB entail φ→ψ? We classify the complexity of this problem for a number of well-known approaches (including Goldszmidt et al. 's maximum entropy approach and Geffner's conditional entailment), where we consider the general propositional case as well as natural syntactic restrictions (in particular, to Horn and literal-Horn conditional knowledge bases). As we show, the more sophisticated semantics for conditional knowledge bases are plagued with intractability in all these fragments. We thus explore cases in which these semantics are tractable, and find that most of them enjoy this property on feedback-free Horn conditional knowledge bases, which constitute a new, meaningful class of conditional knowledge bases. Furthermore, we generalize previous tractability results from Horn to q-Horn conditional knowledge bases, which allow for a limited use of disjunction. Our results complement and extend previous results, and contribute in refining the tractability/intractability frontier of default reasoning from conditional knowledge bases. They provide useful insight for developing efficient implementations.

AIJ Journal 2000 Journal Article

Heterogeneous active agents, III: Polynomially implementable agents

  • Thomas Eiter
  • V.S. Subrahmanian
  • T.J. Rogers

In “Heterogeneous active agents, I” (Eiter et al. , 1999), two of the authors have introduced techniques to build agents on top of arbitrary data structures, and to “agentize” new/existing programs. They provided a series of successively more sophisticated semantics for such agent systems, and showed that as these semantics become epistemically more desirable, a computational price may need to be paid. In this paper, we identify a class of agents that are called weakly regular—this is done by first identifying a fragment of agent programs (Eiter et al. , 1999) called weakly regular agent programs (WRAPs for short). It is shown that WRAPs are definable via three parameters—checking for a property called “safety”, checking for a property called “conflict-freedom” and checking for a “deontic stratifiability” property. Algorithms for each of these are developed. A weakly regular agent is then defined in terms of these concepts, and a regular agent is one that satisfies an additional boundedness property. We then describe a polynomial algorithm that computes (under suitable assumptions) the reasonable status set semantics of regular agents—this semantics was identified by Eiter et al. (1999) as being epistemically most desirable. Though this semantics is coNP-complete for arbitrary agent programs (Eiter and Subrahmanian, 1999), it is polynomially computable via our algorithm for regular agents. Finally, we describe our implementation architecture and provide details of how we have implemented RAPs, together with experimental results.

JELIA Conference 2000 Conference Paper

New Tractable Cases in Default Reasoning from Conditional Knowledge Bases

  • Thomas Eiter
  • Thomas Lukasiewicz

Abstract We present new tractable cases for default reasoning from conditional knowledge bases. In detail, we introduce q-Horn conditional knowledge bases, which allow for a limited use of disjunction. We show that previous tractability results for ε-entailment, proper ε-entailment, and z - and z + -entailment in the Horn case can be extended to the q-Horn case. Moreover, we present feedback-free- Horn conditional knowledge bases, which constitute a new, meaningful class of conditional knowledge bases. We show that the maximum entropy approach and lexicographic entailment are tractable in the feedback-free-Horn case. Our results complement and extend previous results, and contribute in refining the tractability/ intractability frontier of default reasoning from conditional knowledge bases.

LPAR Conference 2000 Conference Paper

On the Complexity of Theory Curbing

  • Thomas Eiter
  • Georg Gottlob

Abstract In this paper, we determine the complexity of propositional theory curbing. Theory Curbing is a nonmonotonic technique of common sense reasoning that is based on model minimality but unlike circumscription treats disjunction inclusively. In an earlier paper, theory curbing was shown to be feasible in PSPACE, but the precise complexity was left open. In the present paper we prove it to be PSPACE-complete. In particular, we show that both the model checking and the inferencing problem under curbed theories are PSPACE complete. We also study relevant cases where the complexity of theory curbing is located - just as for plain propositional circumscription - at the second level of the polynomial hierarchy and is thus presumably easier than PSPACE.

AIJ Journal 1999 Journal Article

Computing intersections of Horn theories for reasoning with models

  • Thomas Eiter
  • Toshihide Ibaraki
  • Kazuhisa Makino

Model-based reasoning has been proposed as an alternative form of representing and accessing logical knowledge bases. In this approach, a knowledge base is represented by a set of characteristic models. In this paper, we consider computational issues when combining logical knowledge bases, which are represented by their characteristic models; in particular, we study taking their logical intersection. We present low-order polynomial time algorithms or prove intractability for the major computation problems in the context of knowledge bases which are Horn theories. In particular, we show that a model of the intersection Σ of Horn theories Σ 1, …, Σ l, represented by their characteristic models, can be found in linear time, and that some characteristic model of Σ can be found in polynomial time. Moreover, we present an algorithm which enumerates all the models of Σ with polynomial delay. The analogous problem for the characteristic models is proved to be intractable, even if the possible exponential size of the output is taken into account. Furthermore, we show that approximate computation of the set of characteristic models is difficult as well. Nonetheless, we show that deduction from Σ is possible for a large class of queries in polynomial time, while abduction turns out to be intractable. We also consider a generalization of Horn theories, and prove negative results for the basic questions, indicating that an extension of the positive results beyond Horn theories is not immediate.

AIJ Journal 1999 Journal Article

Enhancing model checking in verification by AI techniques

  • Francesco Buccafurri
  • Thomas Eiter
  • Georg Gottlob
  • Nicola Leone

Model checking is a fruitful application of computational logic with high relevance to the verification of concurrent systems. While model checking is capable of automatically testing that a concurrent system satisfies its formal specification, it can not precisely locate an error and suggest a repair, i. e. , a suitable correction, to the system. In this paper, we tackle this problem by using principles from AI. In particular, we introduce the abstract concept of a system repair problem, and exemplify this concept on repair of concurrent programs and protocols. For the development of our framework, we formally extend the concept ofcounterexample, which has been proposed in model checking previously, and provide examples which demonstrate the need for such an extension. Moreover, we investigate into optimization issues for the problem of finding a repair, and present techniques which gain in some cases a considerable reduction of the search space for a repair.

AIJ Journal 1999 Journal Article

Heterogeneous active agents, I: Semantics

  • Thomas Eiter
  • V.S. Subrahmanian
  • George Pick

Over the years, many different agent programming languages have been proposed. In this paper, we propose a concept called Agent Programs using which, the way an agent should act in various situations can be declaratively specified by the creator of that agent. Agent Programs may be built on top of arbitrary pieces of software code and may be used to specify what an agent is obliged to do, what an agent may do, and what an agent may not do. In this paper, we define several successively more sophisticated and epistemically satisfying declarative semantics for agent programs. We further show that agent programs cleanly extend well understood semantics for logic programs, and thus are clearly linked to existing results on logic programming and nonmonotonic reasoning.

AIJ Journal 1999 Journal Article

Heterogeneous active agents, II: Algorithms and complexity

  • Thomas Eiter
  • V.S. Subrahmanian

In Part I of this series of papers, we developed a language called Agent Programs for defining the operational behavior of software agents and defined a set of successively more satisfying (epistemically) semantics for such agent programs. In Part II of this series of papers, we study the computation price to be paid (in terms of complexity) for these epistemic desiderata. In particular, we develop algorithms for the above semantics, and describe results on their computational complexity. We show that (surprisingly) the reasonable status set semantics is the easiest to compute of the semantics proposed.

AIJ Journal 1999 Journal Article

Preferred answer sets for extended logic programs

  • Gerhard Brewka
  • Thomas Eiter

In this paper, we address the issue of how Gelfond and Lifschitz's answer set semantics for extended logic programs can be suitably modified to handle prioritized programs. In such programs an ordering on the program rules is used to express preferences. We show how this ordering can be used to define preferred answer sets and thus to increase the set of consequences of a program. We define a strong and a weak notion of preferred answer sets. The first takes preferences more seriously, while the second guarantees the existence of a preferred answer set for programs possessing at least one answer set. Adding priorities to rules is not new, and has been explored in different contexts. However, we show that many approaches to priority handling, most of which are inherited from closely related formalisms like default logic, are not suitable and fail on intuitive examples. Our approach, which obeys abstract, general principles that any approach to prioritized knowledge representation should satisfy, handles them in the expected way. Moreover, we investigate the complexity of our approach. It appears that strong preference on answer sets does not add on the complexity of the principal reasoning tasks, and weak preference leads only to a mild increase in complexity.

AAAI Conference 1998 Conference Paper

Computing Intersections of Horn Theories for Reasoning with Models

  • Thomas Eiter

We consider computational issues in combining logical knowledge bases represented by their characteristic models; in particular, we study taking their logical intersection. We present efficient algorithms or prove intractability for the major computation problems for Horn knowledge bases. We also consider an extension of Horn theories, for which negative results are obtained. They indicate that generalizing the positive results beyond Horn theories is not immediate.

TCS Journal 1998 Journal Article

Expressive power and complexity of partial models for disjunctive deductive databases

  • Thomas Eiter
  • Nicola Leone
  • Domenico Saccá

This paper investigates the expressive power and complexity of partial model semantics for disjunctive deductive databases. In particular, partial stable, regular model, maximal stable (M-stable), and least undefined stable (L-stable) semantics for function-free disjunctive logic programs are considered, for which the expressiveness of queries based on possibility and certainty inference is determined. On the complexity side, we determine the data and expression complexity of query evaluation. The analysis pays particular attention to the impact of syntactical restrictions on programs in the form of limited use of disjunction and negation. It appears that the considered semantics capture complexity classes at the lower end of the polynomial hierarchy. In fact, each class ∑ i P, Π i P, 1 ⩽i⩽ 3 is captured by some semantics using appropriate syntactical restrictions. Partial stable models have exactly the same expressive power and complexity as total stable models (∑2 P resp. Π 2 P ), while a higher degree of expressiveness is obtained by the semantics which minimize undefinedness (M-stable, regular, and L-stable semantics). In particular, L-stable semantics has the highest expressive power (∑3 P resp. Π 3 P ). An interesting result in this course is that, in contrast with total stable models, negation is for partial stable models more expressive than disjunction. For the data complexity of queries, we obtain completeness results for the classes ∑ i P, Π i P, i⩽3, and, for the expression complexity, completeness results for the analogous classes at the lower end of the weak exponential hierarchy. The results of this paper complement and extend previous results, and contribute to a more complete picture of the computational aspects of disjunctive logic programming and databases, which supports in choosing an appropriate setting that fits the needs in practice.

TCS Journal 1997 Journal Article

Abduction from logic programs: Semantics and complexity

  • Thomas Eiter
  • Georg Gottlob
  • Nicola Leone

Abduction — from observations and a theory, find using hypotheses an explanation for the observations — gained increasing interest during the last years. This form of reasoning has wide applicability in different areas of computer science; in particular, it has been recognized as an important principle of common-sense reasoning. In this paper, we define a general abduction model for logic programming, where the inference operator (i. e. , the semantics to be applied on programs), can be specified by the user. Advanced forms of logic programming have been proposed as valuable tools for knowledge representation and reasoning. We show that logic programming semantics can be more meaningful for abductive reasoning than classical inference by providing examples from the area of knowledge representation and reasoning. The main part of the paper is devoted to an extensive study of the computational complexity of the principal problems in abductive reasoning, which are: Given an instance of an abduction problem (1) does the problem have solution (i. e. , an explanation); (2) does a given hypothesis belong to some explanation; and (3) does a given hypothesis belong to all explanations. This problems are analyzed for different underlying logic programming semantics, namely, the well-founded semantics, the stable model semantics and the minimal model semantics, paying attention to normal and disjunctive logic programs for the case of propositional as well as function-free first-order programs. The main results are that the above abductive reasoning tasks on propositional logic programs populate the classes at the lower end of the polynomial hierarchy up to ∑4 p, and provide complete problems for a number of classes over the first four levels of the hierarchy. Similar results are obtained in the first-order case. This proves abduction from logic programs as a rich source of problems of varying complexity.

AIJ Journal 1997 Journal Article

Semantics and complexity of abduction from default theories

  • Thomas Eiter
  • Georg Gottlob
  • Nicola Leone

Abductive reasoning (roughly speaking, find an explanation for observations out of hypotheses) has been recognized as an important principle of common-sense reasoning. Since logical knowledge representation is commonly based on nonclassical formalisms like default logic, autoepistemic logic, or circumscription, it is necessary to perform abductive reasoning from theories (i. e. , knowledge bases) of nonclassical logics. In this paper, we investigate how abduction can be performed from theories in default logic. In particular, we present a basic model of abduction from default theories. Different modes of abduction are plausible, based on credulous and skeptical default reasoning; they appear useful for different applications such as diagnosis and planning. Moreover, we thoroughly analyze the complexity of the main abductive reasoning tasks, namely finding an explanation, deciding relevance of a hypothesis and deciding necessity of a hypothesis. These problems are intractable even in the prepositional case and we locate them into the appropriate slots of the polynomial hierarchy. However, we also present known classes of default theories for which abduction is tractable. Moreover, we also consider first-order default theories, based on domain closure and the unique names assumption. In this setting, the abduction tasks are decidable, but have exponentially higher complexity than in the propositional case.

TCS Journal 1996 Journal Article

Querying disjunctive databases through nonmonotonic logics

  • Piero A. Bonatti
  • Thomas Eiter

Query languages for retrieving information from disjunctive databases are an interesting open area of research. In this paper we study the expressive power of major nonmonotonic formalisms — such as circumscription, default logic, autoepistemic logic and some logic programming languages — used as query languages over disjunctive databases. For this aim, we define the semantics of query expressions formulated in different nonmonotonic logics. The expressive power of the languages that we consider has been explored in the context of relational databases. Here, we extend this study to disjunctive databases; as a result, we obtain a finer-grained characterization of the expressiveness of those languages and interesting fragments thereof. For instance, we show that there exist simple queries that cannot be expressed by any preferential semantics (including the minimal model semantics and the various forms of circumscription), while they can be expressed in default and autoepistemic logic. Secondly, we show that default logic, autoepistemic logic and some of their fragments express the same class of Boolean queries, which turns out to be a strict subclass of the ∑ p 2-recognizable Boolean queries. The latter result is proved by means of a new technique, based on a counting argument. Then we prove that under the assumption that the database consists of clauses whose length is bounded by some constant, default logic and autoepistemic logic express all of the ∑ p 2-recognizable Boolean queries, while preference-based logics cannot. These results hold for brave reasoning; we obtain dual results for cautious reasoning. Our results appear to be interesting both in the area of database theory and in the area of knowledge representation.

TCS Journal 1993 Journal Article

Propositional circumscription and extended closed-world reasoning are ΠP2-complete

  • Thomas Eiter
  • Georg Gottlob

Circumscription and the closed-world assumption with its variants are well-known nonmonotonic techniques for reasoning with incomplete knowledge. Their complexity in the propositional case has been studied in detail for fragments of propositional logic. One open problem is whether the deduction problem for arbitrary propositional theories under the extended closed-world assumption or under circumscription is ΠP 2-complete, i. e. , complete for a class of the second level of the polynomial hierarchy. We answer this question by proving these problems ΠP 2-complete, and we show how this result applies to other variants of closed-world reasoning.

IJCAI Conference 1993 Conference Paper

The Complexity of Nested Counterfactuals and Iterated Knowledge Base Revisions

  • Thomas Eiter
  • Georg Gottlob

We consider the computational complexity of evaluating nested counterfactuals over a propositional knowledge base. Counterfactual implication models a statement "if p, then q, " where p is known or expected to be false, and is different from material implication A nested counterfactual is a counterfactual statement where the conclusion q is a (possibly negated) counterfactual. Statements of the form intuitively correspond to hypothetical queries involving a sequence of revisions. We show that evaluating such statements is complete, and that this task becomes PSPACE-cornplete if negation is allowed in the nesting. We also consider nesting a counterfactual in the premise, i. e. and show that evaluating such statements is most likely much harder than evaluating

AIJ Journal 1992 Journal Article

An efficient method for eliminating varying predicates from a circumscription

  • Marco Cadoli
  • Thomas Eiter
  • Georg Gottlob

Circumscription appears to be the most powerful and well-studied technique used in formalizing common-sense reasoning. The general form of predicate circumscription allows for fixed and varying (floating) predicates. We show that the inference problem under this form of circumscription is efficiently reducible to inferencing under circumscription without varying predicates. In fact, we transform this problem even into circumscription without fixed and varying predicates, that is where all predicates are minimized. Thus any theorem prover or algorithm for inferencing under circumscription without fixed and varying predicates is able to handle inferencing under the general form of predicate circumscription. As a consequence, algorithms that compute circumscription for an inference task can be simplified.

AIJ Journal 1992 Journal Article

On the complexity of propositional knowledge base revision, updates, and counterfactuals

  • Thomas Eiter
  • Georg Gottlob

We study the complexity of several recently proposed methods for updating or revising propositional knowledge bases under the principle of Minimal Change. In particular, we derive complexity results for the following problem: given a knowledge base T, an update p, and a formula q, decide whether q is derivable from T ○ p, the updated (or revised) knowledge base. Note that this problem includes the evaluation of the counterfactual p > q over T, that is a conditional statement “if p, then q”, where p is known or expected to be false. We consider the general case where T is an arbitrary propositional formula (or theory) as well as restricted versions of this problem, in particular where T is a conjunction of Horn clauses, or where the size of the update p is bounded by a constant.