Fundamenta Informaticae - Volume 147, issue 1

Authors: Inclezan, Daniela | Maratea, Marco | Marek, Victor

Article Type: Other

DOI: 10.3233/FI-2016-1395

Citation: Fundamenta Informaticae, vol. 147, no. 1, pp. v-vii, 2016

Authors: Abseher, Michael | Gebser, Martin | Musliu, Nysret | Schaub, Torsten | Woltran, Stefan

Article Type: Research Article

Abstract: Answer Set Programming (ASP) is a powerful declarative programming paradigm that has been successfully applied to many different domains. Recently, ASP has also proved successful for hard optimization problems like course timetabling and travel allotment. In this paper, we approach another important task, namely, the shift design problem, aiming at an alignment of a minimum number of shifts in order to meet required numbers of employees (which typically vary for different time periods) in such a way that over- and understaffing is minimized. We provide an ASP encoding of the shift design problem, which, to the best of our knowledge, …has not been addressed by ASP yet. Our experimental results demonstrate that ASP is capable of improving the best known solutions to some benchmark problems. Other instances remain challenging and make the shift design problem an interesting benchmark for ASP-based optimization methods. Show more

DOI: 10.3233/FI-2016-1396

Citation: Fundamenta Informaticae, vol. 147, no. 1, pp. 1-25, 2016

Authors: Bliem, Bernhard | Charwat, Günther | Hecher, Markus | Woltran, Stefan

Article Type: Research Article

Abstract: Many problems from the area of AI have been shown tractable for bounded treewidth. In order to put such results into practice, quite involved dynamic programming (DP) algorithms on tree decompositions have to be designed and implemented. These algorithms typically show recurring patterns that call for tasks like subset minimization. In this paper we present a novel approach to obtain such DP algorithms from simpler principles, where the DP formalization of subset minimization is performed automatically. We first give a theoretical account of our novel method, and then present D-FLAT^2, a system that allows one to specify the core DP …algorithm via answer set programming (ASP). We illustrate the approach at work by providing several DP algorithms that are more space-efficient than existing solutions, while featuring improved readability, reuse and therefore maintainability of ASP code. Experiments show that our approach also yields a significant improvement in runtime performance. Show more

Keywords: subset minimization, dynamic programming, tree decomposition, answer-set programming, artificial intelligence

DOI: 10.3233/FI-2016-1397

Citation: Fundamenta Informaticae, vol. 147, no. 1, pp. 27-61, 2016

Authors: Bomanson, Jori | Gebser, Martin | Janhunen, Tomi | Kaufmann, Benjamin | Schaub, Torsten

Article Type: Research Article

Abstract: Acyclicity constraints are prevalent in knowledge representation and applications where acyclic data structures such as DAGs and trees play a role. Recently, such constraints have been considered in the satisfiability modulo theories (SMT) framework, and in this paper we carry out an analogous extension to the answer set programming (ASP) paradigm. The resulting formalism, ASP modulo acyclicity, offers a rich set of primitives to express constraints related to recursive structures. In the technical results of the paper, we relate the new generalization with standard ASP by showing (i) how acyclicity extensions translate into normal rules, (ii) how weight constraint programs …can be instrumented by acyclicity extensions to capture stability in analogy to unfounded set checking, and (iii) how the gap between supported and stable models is effectively closed in the presence of such an extension. Moreover, we present an efficient implementation of acyclicity constraints by incorporating a respective propagator into the state-of-the-art ASP solver CLASP . The implementation provides a unique combination of traditional unfounded set checking with acyclicity propagation. In the experimental part, we evaluate the interplay of these orthogonal checks by equipping logic programs with supplementary acyclicity constraints. The performance results show that native support for acyclicity constraints is a worthwhile addition, furnishing a complementary modeling construct in ASP itself as well as effective means for translation-based ASP solving. Show more

DOI: 10.3233/FI-2016-1398

Citation: Fundamenta Informaticae, vol. 147, no. 1, pp. 63-91, 2016

Authors: Fandinno, Jorge

Article Type: Research Article

Abstract: In this work we propose an extension of logic programming, under the stable model semantics , and the action language ℬ𝒞 where rule bodies and causal laws may contain a new kind of literal, that we call causal literal , that allows us to inspect the causal justifications of standard atoms. To this aim, we extend a recently proposed semantics where each atom belonging to a stable model is associated with a justification in the form of an algebraic expression (which corresponds to a logical proof built with rule labels). In particular, we use causal literals for evaluating and deriving …new conclusions from statements like “A has been sufficient to cause B .” We also use the proposed semantics to extend the action language ℬ𝒞 with causal literals and, by some examples, show how this action language is useful for expressing a high level representation of some typical Knowledge Representation examples involving causal knowledge. Show more

DOI: 10.3233/FI-2016-1399

Citation: Fundamenta Informaticae, vol. 147, no. 1, pp. 93-131, 2016

Authors: Zhang, Zhizheng | Wang, Bin | Zhang, Shutao

Article Type: Research Article

Abstract: This paper develops a logic programming language, GI-log, that extends answer set programming language with a new graded modality Kω where ω is an interval satisfying ω ⊆ [0, 1]. The modality is used to precede a literal in rules bodies, and thus allows for the representation of graded introspections in the presence of multiple belief sets: Kω F intuitively means: it is known that the proportion of the belief sets where F is true is in the interval ω . We define the semantics of GI-log, study the relation to the languages …of strong introspections, give an algorithm for computing solutions of GI-log programs, and investigate the use of GI-log for formalizing contextual reasoning, conformant planning with threshold, and modeling a graph problem. Show more

Keywords: logic programming, epistemic specification, graded introspection

DOI: 10.3233/FI-2016-1400

Citation: Fundamenta Informaticae, vol. 147, no. 1, pp. 133-158, 2016