Truszczynski, Miroslaw



Answer Set Programming: An Introduction to the Special Issue

AI Magazine

This editorial introduces answer set programming, a vibrant research area in computational knowledge representation and declarative programming. We give a brief overview of the articles that form this special issue on answer set programming and of the main topics they discuss.


Answer Set Programming: An Introduction to the Special Issue

AI Magazine

This editorial introduces answer set programming, a vibrant research area in computational knowledge representation and declarative programming. We give a brief overview of the articles that form this special issue on answer set programming and of the main topics they discuss.


First Order Logic with Inductive Definitions for Model-Based Problem Solving

AI Magazine

In answer-set programming (ASP), programs can be viewed as specifications of finite Herbrand structures. Other logics can be (and, in fact, were) used towards the same end and can be taken as the basis of declarative programming systems of similar functionality as ASP. We discuss here one such logic, the logic FO(ID), and its implementation IDP3. The choice is motivated by notable similarities between ASP and FO(ID), even if both approaches trace back to different origins


An Abstract View on Modularity in Knowledge Representation

AAAI Conferences

Modularity is an essential aspect of knowledge representation theory and practice. It has received substantial attention. We introduce model-based modular systems, an abstract framework for modular knowledge representation formalisms, similar in scope to multi-context systems but employing a simpler information-flow mechanism. We establish the precise relationship between the two frameworks, showing that they can simulate each other. We demonstrate that recently introduced modular knowledge representation formalisms integrating logic programming with satisfiability and, more generally, with constraint satisfaction can be cast as modular systems in our sense. These results show that our formalism offers a simple unifying framework for studies of modularity in knowledge representation.


Learning Partial Lexicographic Preference Trees over Combinatorial Domains

AAAI Conferences

We introduce partial lexicographic preference trees (PLPtrees) as a formalism for compact representations of preferences over combinatorial domains. Our main results concern the problem of passive learning of PLP-trees. Specifically, forseveral classes of PLP-trees, we study how to learn (i) a PLP-tree consistent with a dataset of examples, possibly subject to requirements on the size of the tree, and (ii) a PLP-tree correctly ordering as many of the examples as possible in case the dataset of examples is inconsistent. We establish complexity of these problems and, in all cases where the problem is in the class P, propose polynomial time algorithms.


Preference Trees: A Language for Representing and Reasoning about Qualitative Preferences

AAAI Conferences

We introduce a novel qualitative preference representation language, preference trees , or P-trees . We show that the lan- guage is intuitive to specify preferences over combinatorial domains and it extends existing preference formalisms such as LP-trees , ASO-rules and possibilistic logic . We study rea- soning problems with P-trees and obtain computational com- plexity results.


The View-Update Problem for Indefinite Databases

arXiv.org Artificial Intelligence

This paper introduces and studies a declarative framework for updating views over indefinite databases. An indefinite database is a database with null values that are represented, following the standard database approach, by a single null constant. The paper formalizes views over such databases as indefinite deductive databases, and defines for them several classes of database repairs that realize view-update requests. Most notable is the class of constrained repairs. Constrained repairs change the database "minimally" and avoid making arbitrary commitments. They narrow down the space of alternative ways to fulfill the view-update request to those that are grounded, in a certain strong sense, in the database, the view and the view-update request.


Transition Systems for Model Generators - A Unifying Approach

arXiv.org Artificial Intelligence

A fundamental task for propositional logic is to compute models of propositional formulas. Programs developed for this task are called satisfiability solvers. We show that transition systems introduced by Nieuwenhuis, Oliveras, and Tinelli to model and analyze satisfiability solvers can be adapted for solvers developed for two other propositional formalisms: logic programming under the answer-set semantics, and the logic PC(ID). We show that in each case the task of computing models can be seen as "satisfiability modulo answer-set programming," where the goal is to find a model of a theory that also is an answer set of a certain program. The unifying perspective we develop shows, in particular, that solvers CLASP and MINISATID are closely related despite being developed for different formalisms, one for answer-set programming and the latter for the logic PC(ID).


Representing Preferences Among Sets

AAAI Conferences

We study methods to specify preferences among subsets of a set (a universe ). The methods we focus on are of two types. The first one assumes the universe comes with a preference relation on its elements and attempts to lift that relation to subsets of the universe. That approach has limited expressivity but results in orderings that capture interesting general preference principles. The second method consists of developing formalisms allowing the user to specify "atomic" improvements, and generating from them preferences on the powerset of the universe. We show that the particular formalism we propose is expressive enough to capture the lifted preference relations of the first approach, and generalizes propositional CP-nets. We discuss the importance of domain-independent methods for specifying preferences on sets for knowledge representation formalisms, selecting the formalism of argumentation frameworks as an illustrative example.