Irina Trubitsyna

AAAI Conference 2026 Conference Paper

Conditional Probabilistic Bipolar Argumentation Framework: Explanations, Complexity and Approximation

• Gianvincenzo Alfano
• Sergio Greco
• Domenico Mandaglio
• Francesco Parisi
• Irina Trubitsyna

Recently, there has been an increasing interest in extending Dung's framework with probability theory, leading to the Probabilistic Argumentation Framework (PAF), and with supports in addition to attacks, leading to the Bipolar Argumentation Framework (BAF). In this paper, we introduce the Conditional Probabilistic Bipolar Argumentation Framework (CPBAF), which extends Probabilistic and Bipolar AF by allowing conditional probabilities on arguments, attacks, and on (possibly cyclic) supports. In this setting, we address the problem of computing the probability that a given argument is accepted. This is carried out by introducing the concept of probabilistic explanation for a given (probabilistic) extension. We show that the complexity of the problem is FP^#P-hard and propose polynomial approximation algorithms with bounded additive error for CPBAF where cycles with an odd number of attacks are forbidden.

AIJ Journal 2025 Journal Article

Constraints and lifting-based (conditional) preferences in abstract argumentation

• Gianvincenzo Alfano
• Sergio Greco
• Francesco Parisi
• Irina Trubitsyna

AAAI Conference 2025 Conference Paper

Even-if Explanations: Formal Foundations, Priorities and Complexity

• Gianvincenzo Alfano
• Sergio Greco
• Domenico Mandaglio
• Francesco Parisi
• Reza Shahbazian
• Irina Trubitsyna

Explainable AI has received significant attention in recent years. Machine learning models often operate as black boxes, lacking explainability and transparency while supporting decision-making processes. Local post-hoc explainability queries attempt to answer why individual inputs are classified in a certain way by a given model. While there has been important work on counterfactual explanations, less attention has been devoted to semifactual ones. In this paper, we focus on local post-hoc explainability queries within the semifactual `even-if' thinking and their computational complexity among different classes of models, and show that both linear and tree-based models are strictly more interpretable than neural networks. After this, we introduce a preference-based framework enabling users to personalize explanations based on their preferences, both in the case of semifactuals and counterfactuals, enhancing interpretability and user-centricity. Finally, we explore the complexity of several interpretability problems in the proposed preference-based framework and provide algorithms for polynomial cases.

KR Conference 2025 Conference Paper

Extending Abstract Argumentation Frameworks with Knowledge Bases

• Gianvincenzo Alfano
• Sergio Greco
• Cristian Molinaro
• Francesco Parisi
• Irina Trubitsyna

Dung's abstract Argumentation Framework (AF) has been extended in several directions to make knowledge representation and reasoning more intuitive and expressive. In this paper, we present the Knowledge-based Argumentation Framework (KAF), an extension of AF with a Knowledge Base (KB) expressed in DL-Lite, which includes concept and role instances describing the topology of an AF, besides additional knowledge on the domain. The KAF semantics is given by a set of KAF extensions, each consisting of an extension of the underlying AF together with a ``pertinent'' subset of the original KB, which is obtained by discarding assertions referring to arguments that have been ruled out in the AF extension. Then, the framework is further expanded into the Constrained KAF (CKAF), where a set of restricted relational calculus formulae is used for reasoning over `feasible' subframeworks that satisfy the formulae and minimally differ from the original framework. We thoroughly investigate the computational complexity of classical reasoning problems under popular argumentation semantics, and show that well-known AF-based frameworks are special cases of CKAF.

IJCAI Conference 2025 Conference Paper

Featured Argumentation Framework: Semantics and Complexity

• Gianvincenzo Alfano
• Sergio Greco
• Francesco Parisi
• Irina Trubitsyna

Dung's Argumentation Framework (AF) has been extended in several directions to make knowledge representation and reasoning tasks more intuitive and/or expressive. We present a novel extension of AF called Featured AF (FAF), where each argument has associated a set of features expressed by means of unary and binary facts. In such a context, a query is expressed by means of a conjunctive relational calculus formula which is evaluated over the extensions of the FAF. Then, this framework is further expanded into the so-called Extended FAF (EFAF), where a first-order logic formula (FOL) is used for reasoning over `feasible' subframeworks that satisfy the FOL formula and minimally differ from the original framework. We investigate the computational complexity of verification and acceptance problems under several semantics and show that incomplete AF (iAF) frameworks, including correlated iAF and constrained iAF, are special cases of EFAF.

AIJ Journal 2024 Journal Article

Abstract argumentation frameworks with strong and weak constraints

• Gianvincenzo Alfano
• Sergio Greco
• Domenico Mandaglio
• Francesco Parisi
• Irina Trubitsyna

AAAI Conference 2024 Conference Paper

Complexity of Credulous and Skeptical Acceptance in Epistemic Argumentation Framework

• Gianvincenzo Alfano
• Sergio Greco
• Francesco Parisi
• Irina Trubitsyna

Dung’s Argumentation Framework (AF) has been extended in several directions. Among the numerous proposed extensions, three of them seem to be of particular interest and have correlations between them. These extensions are: constrained AF (CAF), where AF is augmented with (strong) constraints; epistemic AF (EAF), where AF is augmented with epistemic constraints; and incomplete AF (iAF), where arguments and attacks can be uncertain. While the complexity and expressiveness of CAF and iAF have been studied, that of EAF has not been explored so far. In this paper we investigate the complexity and expressivity of EAF. To this end, we first introduce the Labeled CAF (LCAF), a variation of CAF where constraints are defined over the alphabet of labeled arguments. Then, we investigate the complexity of credulous and skeptical reasoning and show that: i) EAF is more expressive than iAF (under preferred semantics), ii) although LCAF is a restriction of EAF where modal operators are not allowed, these frameworks have the same complexity, iii) the results for LCAF close a gap in the characterization of the complexity of CAF. Interestingly, even though EAF has the same complexity as LCAF, it allows modeling domain knowledge in a more natural and easy-to-understand way.

KR Conference 2024 Conference Paper

Counterfactual and Semifactual Explanations in Abstract Argumentation: Formal Foundations, Complexity and Computation

• Gianvincenzo Alfano
• Sergio Greco
• Francesco Parisi
• Irina Trubitsyna

Explainable Artificial Intelligence and Formal Argumentation have received significant attention in recent years. Argumentation frameworks are useful for representing knowledge and reasoning on it. Counterfactual and semifactual explanations are interpretability techniques that provide insights into the outcome of a model by generating alternative hypothetical instances. While there has been important work on counterfactual and semifactual explanations for Machine Learning (ML) models, less attention has been devoted to these kinds of problems in argumentation. In this paper, we explore counterfactual and semifactual reasoning in abstract Argumentation Framework. We investigate the computational complexity of counterfactual- and semifactual-based reasoning problems, showing that they are generally harder than classical argumentation problems such as credulous and skeptical acceptance. Finally, we show that counterfactual and semifactual queries can be encoded in weak-constrained Argumentation Framework, and provide a computational strategy through ASP solvers.

IJCAI Conference 2024 Conference Paper

General Epistemic Abstract Argumentation Framework: Semantics and Complexity

• Gianvincenzo Alfano
• Sergio Greco
• Francesco Parisi
• Irina Trubitsyna

Epistemic Abstract Argumentation Framework (EAAF) extends Dung's framework (AAF)---a central formalism in AI for modeling disputes among agents---by allowing the representation of epistemic knowledge. In particular, EAAF augments AAF with weak and strong epistemic attacks whose intuitive meaning is that an argument a defeats an argument b by means of a weak (resp. strong) epistemic attack if a is true in every (resp. at least one) extension. So far, the semantics of EAAF has been defined only for a restricted class of frameworks, namely acyclic EAAF, where epistemic attacks do not occur in any cycle. In this paper, we provide an intuitive semantics for (general) EAAF that naturally extends that for AAF as well as that for acyclic EAAF. After providing some fundamental properties and giving an algorithm that enables the computation of EAAF semantics, by relying on state-of-the-art AAF-solvers, we investigate the complexity of canonical argumentation problems.

AAMAS Conference 2024 Conference Paper

On General Epistemic Abstract Argumentation Frameworks

• Gianvincenzo Alfano
• Sergio Greco
• Francesco Parisi
• Irina Trubitsyna

Epistemic Abstract Argumentation Framework (EAAF) extends Dung’s framework (AAF) by allowing the representation of epistemic attacks. So far, the semantics of EAAF has been defined only for a restricted class of frameworks, namely acyclic EAAF, where epistemic attacks do not occur in any cycle. In this paper, we provide an intuitive semantics for (general) EAAF that naturally extends that for AAF as well as that for acyclic EAAF.

AAAI Conference 2023 Conference Paper

Abstract Argumentation Framework with Conditional Preferences

• Gianvincenzo Alfano
• Sergio Greco
• Francesco Parisi
• Irina Trubitsyna

Dung's abstract Argumentation Framework (AF) has emerged as a central formalism in the area of knowledge representation and reasoning. Preferences in AF allow to represent the comparative strength of arguments in a simple yet expressive way. Preference-based AF (PAF) has been proposed to extend AF with preferences of the form a > b, whose intuitive meaning is that argument a is better than b. In this paper we generalize PAF by introducing conditional preferences of the form a > b \leftarrow body that informally state that a is better than b whenever the condition expressed by body is true. The resulting framework, namely Conditional Preference-based AF (CPAF), extends the PAF semantics under three well-known preference criteria, i.e. democratic, elitist, and KTV. After introducing CPAF, we study the complexity of the verification problem (deciding whether a set of arguments is a ``best'' extension) as well as of the credulous and skeptical acceptance problems (deciding whether a given argument belongs to any or all ``best'' extensions, respectively) under multiple-status semantics (that is, complete, preferred, stable, and semi-stable semantics) for the above-mentioned preference criteria.

ECAI Conference 2023 Conference Paper

Complexity of Verification and Existence Problems in Epistemic Argumentation Framework

• Gianvincenzo Alfano
• Sergio Greco
• Domenico Mandaglio
• Francesco Parisi
• Irina Trubitsyna

Dung’s Argumentation Framework (AF) has been extended in several directions. An interesting extension, among others, is the Epistemic AF (EAF) which allows representing the agent’s belief by means of epistemic constraints. In particular, an epistemic constraint is a propositional formula over labeled arguments (e. g. in(a), out(c)) extended with the modal operators K and M that intuitively state that the agent believes that a given formula is certainly or possibly true, respectively. In this paper, focusing on EAF, we investigate the complexity of the possible and necessary variants of three canonical problems in abstract argumentation: verification, existence, and non-empty existence. Moreover, we explore the relationship between EAF and incomplete AF (iAF), an extension of AF where arguments and attacks may be uncertain. Our complexity analysis shows that the verification problem in iAF can be naturally reduced to the verification in EAF, while it turns out that a similar result cannot hold for the necessary (non-empty) existence problem.

AAMAS Conference 2023 Conference Paper

Epistemic Abstract Argumentation Framework: Formal Foundations, Computation and Complexity

• Gianvincenzo Alfano
• Sergio Greco
• Francesco Parisi
• Irina Trubitsyna

Dung’s Abstract Argumentation Framework (AAF) has emerged as a central formalism in AI for modeling disputes among agents. In this paper, we introduce an extension of Dung’s framework, called Epistemic Abstract Argumentation Framework (EAAF), which enhances AAF by allowing the representation of some pieces of epistemic knowledge. We generalize the concept of attack in AAF, introducing strong and weak epistemic attacks in EAAF, whose intuitive meaning is that an attacked argument is epistemically accepted only if the attacking argument is possibly or certainly rejected, respectively. We provide an intuitive semantics for EAAF that naturally extends that for AAF, and give an algorithm that enables the computation of epistemic extensions by using AAF-solvers. Finally, we analyze the complexity of the following argumentation problems: verification, i. e. checking whether a set of arguments is an epistemic extension; existence, i. e. checking whether there is at least one (non-empty) epistemic extension; and acceptance, i. e. checking whether an argument is epistemically accepted, under well-known argumentation semantics (i. e. grounded, complete, and preferred).

AIJ Journal 2023 Journal Article

Explainable acceptance in probabilistic and incomplete abstract argumentation frameworks

• Gianvincenzo Alfano
• Marco Calautti
• Sergio Greco
• Francesco Parisi
• Irina Trubitsyna

NMR Workshop 2023 Conference Paper

On the Conditional Preference-based Argumentation Framework

• Gianvincenzo Alfano
• Sergio Greco
• Francesco Parisi
• Irina Trubitsyna

Dung’s abstract Argumentation Framework (AF) has emerged as a central formalism in the area of knowledge representation and reasoning. Preferences in AF allow to represent the comparative strength of arguments in a simple yet expressive way. Preference-based AF (PAF) has been proposed to extend AF with preferences of the form 𝑎 > 𝑏, whose intuitive meaning is that argument 𝑎 is better than 𝑏. In this paper we discuss the recently proposed Conditional Preference-based Argumentation Framework (CPAF) [1] that extends PAF by introducing conditional preferences of the form 𝑎 > 𝑏 ← 𝑏𝑜𝑑𝑦 informally stating that 𝑎 is better than 𝑏 whenever the condition expressed by 𝑏𝑜𝑑𝑦 is true. We discuss CPAF properties and complexity results of the well-known verification and acceptance problems under multiple-status argumentation semantics.

NMR Workshop 2023 Conference Paper

On the Extended Preference-based Constrained Argumentation Framework

• Gianvincenzo Alfano
• Sergio Greco
• Francesco Parisi
• Irina Trubitsyna

In recent years there has been an increasing interest in extending Dung’s framework to facilitate the knowledge representation and reasoning process. In this paper, we discuss a recently proposed extension of abstract Argumentation Framework (AF) that allows for the representation of preferences over arguments’ truth values (3-valued preferences) [1]. For instance, we can express a preference stating that extensions where argument 𝑎 is false (i. e. defeated) are preferred to extensions where argument 𝑏 is false. Interestingly, such a framework generalizes the well-known Preference-based AF with no additional cost in terms of computational complexity for most of the classical argumentation semantics. Then, AF is further extended by considering both (3-valued) preferences and 3-valued constraints, that is constraints of the form 𝜙 ⇒ 𝑣 or 𝑣 ⇒ 𝜙, where 𝜙 is a logical formula and 𝑣 is a 3-valued truth value. We discuss the complexity of deciding acceptance of arguments in this context.

IJCAI Conference 2023 Conference Paper

Preferences and Constraints in Abstract Argumentation

• Gianvincenzo Alfano
• Sergio Greco
• Francesco Parisi
• Irina Trubitsyna

In recent years there has been an increasing interest in extending Dung's framework to facilitate the knowledge representation and reasoning process. In this paper, we present an extension of Abstract Argumentation Framework (AF) that allows for the representation of preferences over arguments' truth values (3-valued preferences). For instance, we can express a preference stating that extensions where argument a is false (i. e. defeated) are preferred to extensions where argument b is false. Interestingly, such a framework generalizes the well-known Preference-based AF with no additional cost in terms of computational complexity for most of the classical argumentation semantics. Then, we further extend AF by considering both (3-valued) preferences and 3-valued constraints, that is constraints of the form \varphi \Rightarrow v or v \Rightarrow \varphi, where \varphi is a logical formula and v is a 3-valued truth value. After investigating the complexity of the resulting framework, as both constraints and preferences may represent subjective knowledge of agents, we extend our framework by considering multiple agents and study the complexity of deciding acceptance of arguments in this context.

AAAI Conference 2022 Conference Paper

Incomplete Argumentation Frameworks: Properties and Complexity

• Gianvincenzo Alfano
• Sergio Greco
• Francesco Parisi
• Irina Trubitsyna

Dung’s Argumentation Framework (AF) has been extended in several directions, including the possibility of representing unquantified uncertainty about the existence of arguments and attacks. The framework resulting from such an extension is called incomplete AF (iAF). In this paper, we first introduce three new satisfaction problems named totality, determinism and functionality, and investigate their computational complexity for both AF and iAF under several semantics. We also investigate the complexity of credulous and skeptical acceptance in iAF under semi-stable semantics—a problem left open in the literature. We then show that any iAF can be rewritten into an equivalent one where either only (unattacked) arguments or only attacks are uncertain. Finally, we relate iAF to probabilistic argumentation framework, where uncertainty is quantified.

IJCAI Conference 2022 Conference Paper

On Preferences and Priority Rules in Abstract Argumentation

• Gianvincenzo Alfano
• Sergio Greco
• Francesco Parisi
• Irina Trubitsyna

Dung's abstract Argumentation Framework (AF) has emerged as a central formalism for argumentation in AI. Preferences in AF allow to represent the comparative strength of arguments in a simple yet expressive way. In this paper we first investigate the complexity of the verification as well as credulous and skeptical acceptance problems in Preference-based AF (PAF) that extends AF with preferences over arguments. Next, after introducing new semantics for AF where extensions are selected using cardinality (instead of set inclusion) criteria and investigating their complexity, we introduce a framework called AF with Priority rules (AFP) that extends AF with sequences of priority rules. AFP generalizes AF with classical set-inclusion and cardinality based semantics, suggesting that argumentation semantics can be viewed as ways to express priorities among extensions. Finally, we extend AFP by proposing AF with Priority rules and Preferences (AFP^2), where also preferences over arguments can be used to define priority rules, and study the complexity of the above-mentioned problems.

AIJ Journal 2022 Journal Article

Preference-based inconsistency-tolerant query answering under existential rules

• Marco Calautti
• Sergio Greco
• Cristian Molinaro
• Irina Trubitsyna

TCS Journal 2022 Journal Article

Query answering over inconsistent knowledge bases: A probabilistic approach

• Marco Calautti
• Sergio Greco
• Cristian Molinaro
• Irina Trubitsyna

AAAI Conference 2021 Conference Paper

Argumentation Frameworks with Strong and Weak Constraints: Semantics and Complexity

• Gianvincenzo Alfano
• Sergio Greco
• Francesco Parisi
• Irina Trubitsyna

Dung’s abstract Argumentation Framework (AF) has emerged as a central formalism in formal argumentation. Key aspects of the success and popularity of Dung’s framework include its simplicity and expressiveness. Integrity constraints help to express domain knowledge in a compact and natural way, thus keeping easy the modeling task even for problems that otherwise would be hard to encode within an AF. In this paper, after providing an intuitive semantics based on Lukasiewicz’s logic for AFs with (strong) constraints, called Constrained AFs (CAFs), we propose Weak constrained AFs (WAFs) that enhance CAFs with weak constraints. Intuitively, these constraints can be used to find “optimal” solutions to problems defined through CAFs. We provide a detailed complexity analysis of CAFs and WAFs, showing that strong constraints do not increase the expressive power of AFs in most cases, while weak constraints systematically increase the expressive power of CAFs under several wellknown argumentation semantics.

IJCAI Conference 2021 Conference Paper

Defining the Semantics of Abstract Argumentation Frameworks through Logic Programs and Partial Stable Models (Extended Abstract)

• Gianvincenzo Alfano
• Sergio Greco
• Francesco Parisi
• Irina Trubitsyna

Extensions of Dung’s Argumentation Framework (AF) include the class of Recursive Bipolar AFs (Rec-BAFs), i. e. AFs with recursive attacks and supports. We show that a Rec-BAF \Delta can be translated into a logic program P_\Delta so that the extensions of \Delta under different semantics coincide with subsets of the partial stable models of P_\Delta.

KR Conference 2020 Conference Paper

Explainable Acceptance in Probabilistic Abstract Argumentation: Complexity and Approximation

• Gianvincenzo Alfano
• Marco Calautti
• Sergio Greco
• Francesco Parisi
• Irina Trubitsyna

Recently there has been an increasing interest in probabilistic abstract argumentation, an extension of Dung's abstract argumentation framework with probability theory. In this setting, we address the problem of computing the probability that a given argument is accepted. This is carried out by introducing the concept of probabilistic explanation for a given (probabilistic) extension. We show that the complexity of the problem is FP^#P-hard and propose polynomial approximation algorithms with bounded additive error for probabilistic argumentation frameworks where odd-length cycles are forbidden. This is quite surprising since, as we show, such kind of approximation algorithm does not exist for the related FP^#P-hard problem of computing the probability of the credulous acceptance of an argument, even for the special class of argumentation frameworks considered in the paper.

KR Conference 2020 Conference Paper

Preference-based Inconsistency-Tolerant Query Answering under Existential Rules

• Marco Calautti
• Sergio Greco
• Cristian Molinaro
• Irina Trubitsyna

Query answering over inconsistent knowledge bases is a problem that has attracted a great deal of interest over the years. Different inconsistency-tolerant semantics have been proposed, and most of them are based on the notion of repair, that is, a "maximal" consistent subset of the database. In general, there can be several repairs, so it is often natural and desirable to express preferences among them. In this paper, we propose a framework for querying inconsistent knowledge bases under user preferences for existential rule languages. We provide generalizations of popular inconsistency-tolerant semantics taking preferences into account and study the data and combined complexity of different relevant problems.

IJCAI Conference 2018 Conference Paper

Computing Approximate Query Answers over Inconsistent Knowledge Bases

• Sergio Greco
• Cristian Molinaro
• Irina Trubitsyna

Consistent query answering is a principled approach for querying inconsistent knowledge bases. It relies on the notion of a "repair", that is, a maximal consistent subset of the facts in the knowledge base. One drawback of this approach is that entire facts are deleted to resolve inconsistency, even if they may still contain useful "reliable" information. To overcome this limitation, we propose a new notion of repair allowing values within facts to be updated for restoring consistency. This more fine-grained repair primitive allows us to preserve more information in the knowledge base. We also introduce the notion of a "universal repair", which is a compact representation of all repairs. Then, we show that consistent query answering in our framework is intractable (coNP-complete). In light of this result, we develop a polynomial time approximation algorithm for computing a sound (but possibly incomplete) set of consistent query answers.

IJCAI Conference 2015 Conference Paper

Logic Program Termination Analysis Using Atom Sizes

• Marco Calautti
• Sergio Greco
• Cristian Molinaro
• Irina Trubitsyna

Recent years have witnessed a great deal of interest in extending answer set programming with function symbols. Since the evaluation of a program with function symbols might not terminate and checking termination is undecidable, several classes of logic programs have been proposed where the use of function symbols is limited but the program evaluation is guaranteed to terminate. In this paper, we propose a novel class of logic programs whose evaluation always terminates. The proposed technique identifies terminating programs that are not captured by any of the current approaches. Our technique is based on the idea of measuring the size of terms and atoms to check whether the rule head size is bounded by the body, and performs a more fine-grained analysis than previous work. Rather than adopting an all-ornothing approach (either we can say that the program is terminating or we cannot say anything), our technique can identify arguments that are “limited” (i. e. , where there is no infinite propagation of terms) even when the program is not entirely recognized as terminating. Identifying arguments that are limited can support the user in the problem formulation and help other techniques that use limited arguments as a starting point. Another useful feature of our approach is that it is able to leverage external information about limited arguments. We also provide results on the correctness, the complexity, and the expressivity of our technique.

IJCAI Conference 2013 Conference Paper

Bounded Programs: A New Decidable Class of Logic Programs with Function Symbols

• Sergio Greco
• Cristian Molinaro
• Irina Trubitsyna

While function symbols are widely acknowledged as an important feature in logic programming, they make common inference tasks undecidable. To cope with this problem, recent research has focused on identifying classes of logic programs imposing restrictions on the use of function symbols, but guaranteeing decidability of common inference tasks. This has led to several criteria, called termination criteria, providing sufficient conditions for a program to have finitely many stable models, each of finite size. This paper introduces the new class of bounded programs which guarantees the aforementioned property and strictly includes the classes of programs determined by current termination criteria. Different results on the correctness, the expressiveness, and the complexity of the class of bounded programs are presented.

JELIA Conference 2012 Conference Paper

The View-Update Problem for Indefinite Databases

• Luciano Caroprese
• Irina Trubitsyna
• Miroslaw Truszczynski
• Ester Zumpano

Abstract 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.

JELIA Conference 2006 Conference Paper

On the Semantics of Logic Programs with Preferences

• Sergio Greco
• Irina Trubitsyna
• Ester Zumpano

Abstract This work is a contribution to realizing prioritized reasoning in logic programming in the presence of preference relations involving atoms. In more details, the case of dynamic preferences is investigated and a semantics interpreting each preference rule as a tool for representing a choice over alternative options is proposed. The technique, providing a new interpretation for prioritized logic programs, is inspired by the one proposed by Sakama and Inoue in [19] and enriched with the use of structural information of preference rules as proposed by Brewka et al. in [6]. Specifically, the analysis of the logic program is carried out together with the analysis of preferences in order to determine the choice order and the sets of comparable models. The proposed approach is compared with those in [6, 19]. Complexity analysis is also performed showing that the use of additional information does not increase the complexity of computing preferred stable models.

LPAR Conference 2002 Conference Paper

Query Optimization of Disjunctive Databases with Constraints through Binding Propagation

• Gianluigi Greco
• Sergio Greco
• Irina Trubitsyna
• Ester Zumpano

Abstract In this paper we present a technique for the optimization of bound queries over disjunctive deductive databases with constraints, i. e. rules defining properties which have to be satisfied by all instances over database schema. The technique we propose, allows the binding propagation into disjunctive queries with a set of constraints; thus, reducing the size of the data relevant to answer the query it, consequently, minimizes both the complexity of computing a single model and the whole number of models to be considered. The main contribution of this work consists in the extension of previous techniques by considering Datalog programs with both disjunctive heads and constraints. In particular, by considering weak constraints the technique is also suitable for dealing with optimization problems. Several experiments have confirmed the value of the technique.

LOPSTR Conference 2002 Conference Paper

Translating Datalog-Like Optimization Queries into ILOG Programs

• Gianluigi Greco
• Sergio Greco
• Irina Trubitsyna
• Ester Zumpano

Abstract This paper presents a logic language, called \( \mathcal{N}\mathcal{P}{\mathbf{ }}Datalog \) suitable for expressing NP search and optimization problems. The ‘search’ language extends stratified Datalog with constraints and allows disjunction to define nondeterministically partitions of relations. It’s well known that \( \mathcal{N}\mathcal{P} \) search problems can be formulated as unstratified DATALOG queries under nondeterministic stable model semantics so that each stable model corresponds to a possible solution. \( \mathcal{N}\mathcal{P} \) optimization problems are then formulated by adding a max (or min ) construct to select the stable model (thus, the solution) which maximizes (resp. , minimizes) the result of a polynomial function applied to the answer relation. The problem in using DATALOG ¬ to express search and optimization problems is that the unrestricted negation in programs is often neither simple nor intuitive and, besides, it does not allow to discipline the expressive power. Thus, we consider restricted forms of negation which force user to write programs in a more disciplined way without loosing of expressive power. More specifically, we consider the language \( \mathcal{N}\mathcal{P}{\mathbf{ }}Datalog \) which extends DATALOG ¬ s with two simple forms of unstratified negation embedded into built-in constructs: head disjunction and constraints. Thus the core of our language is stratified Datalog extended with two constructs allowing nondeterministic selections and with query goals enforcing conditions to be satisfied by stable models.