Fundamenta Informaticae

In this brief note, we outline Mario Ornaghi’s contributions to the field of computational logic to celebrate his 70th birthday.

This paper introduces an instantiation of the constraint logic programming scheme called CLP(PolyFD) in which variables take values from finite subsets of the integers and constraints are expressed as equalities, inequalities, and disequalities of polynomials with integer coefficients. Such constraints, which we call polynomial constraints over finite domains, can be treated effectively by means of a specific solver under the assumption that initial approximations of the domains of variables are available. The proposed solver deals with constraints in a canonical form and it uses the modified Bernstein form of polynomials to detect the satisfiability of constraints. The solver is complete and a preliminary assessment of its performance is reported.

Constructive description logics define interpretations of description logics under different constructive semantics. These logics have been mostly studied from the point of view of their formal properties: limited practical approaches have been shown for their use in knowledge representation and Semantic Web languages and tools (which, on the other hand, constitute the distinctive applications of description logics).

In this paper we demonstrate a solution to address this aspect: from the theoretical point of view, we first introduce an information terms semantics for the minimal description logic ɛℒ and we establish formal results linking this constructive semantics to answer set semantics. Using these results, on the practical side, we then present a prototype managing one aspect of such semantics (the generation of information terms of a knowledge base) using OWL-EL ontologies and “off the shelf” tools.

In order to enable logic programming to deal with the diversity of pervasive systems, where many heterogeneous, domain-specific computational models could benefit from the power of symbolic computation, we explore the expressive power of labelled systems. To this end, we define a new notion of truth for logic programs extended with labelled variables interpreted in non-Herbrand domains—where, however, terms maintain their usual Herbrand interpretations.

First, a model for labelled variables in logic programming is defined. Then, the fixpoint and the operational semantics are presented and their equivalence is formally proved. A meta-interpreter implementing the operational semantics is also introduced, followed by some case studies aimed at showing the effectiveness of our approach in selected scenarios.

The capability to store data about Business Process (BP) executions in so-called Event Logs has brought to the identification of a range of key reasoning services (consistency, compliance, runtime monitoring, prediction) for the analysis of process executions and process models. Tools for the provision of these services typically focus on one form of reasoning alone. Moreover, they are often very rigid in dealing with forms of incomplete information about the process execution. While this enables the development of ad hoc solutions, it also poses an obstacle for the adoption of reasoning-based solutions in the BP community.

In this paper, we introduce the notion of Structured Processes with Observability and Time (SPOT models), able to support incompleteness (of traces and logs), and temporal constraints on the activity duration and between activities. Then, we exploit the power of abduction to provide a flexible, yet computationally effective framework able to reinterpret key reasoning services in terms of incompleteness and observability in a uniform way.

We present a logic-based framework for the specification and validation of distributed protocols. Our specification language is a logic-based presentation of update rules for arbitrary graphs. Update rules are specified via conditional rewriting rules defined over a relational language. We focus our attention on unary and binary relations as a way to specify predicates over nodes and edges of a graph. For the considered language, we define assertions that can be applied to specify correctness properties for arbitrary configurations. We apply the language to model the distributed version of the Dining Philosopher Protocol. The protocol is defined for asynchronous processes distributed over a graph with arbitrary topology. We propose then validation methods based on source to source transformations and deductive reasoning. We apply the resulting method to provide a succint correctness proof of the considered case-study.

In this work we study a rational extension 𝒮ℛ𝒪ℰℒ(⊓, ×) ^R T of the low complexity description logic 𝒮ℛ𝒪ℰℒ(⊓, ×), which underlies the OWL EL ontology language. The extension involves a typicality operator T, whose semantics is based on Lehmann and Magidor’s ranked models and allows for the definition of defeasible inclusions. We consider both rational entailment and minimal entailment. We show that deciding instance checking under minimal entailment is in general ∏ 2 P -hard, while, under rational entailment, instance checking can be computed in polynomial time. We develop a Datalog calculus for instance checking under rational entailment and exploit it, with stratified negation, for computing the rational closure of simple KBs in polynomial time.

The paper presents a methodology to revise a Description Logic knowledge base when exceptions are detected. The approach exploits concepts and results from techniques developed for debugging Description Logic terminologies. Debugging an inconsistent terminology amounts to identifying a minimal subset of axioms responsible for the inconsistency (i.e., an error to be removed by a knowledge engineer). Exception handling, instead, requires to revise the axioms causing an inconsistency so that a new consistent knowledge base is obtained, encompassing the detected exception about an individual x. To this aim, we make use of a nonmonotonic extension of the Description Logic 𝒜ℒ𝒞 based on the combination of a typicality operator and the well established nonmonotonic mechanism of rational closure, which allows one to deal with prototypical properties and defeasible inheritance.

Dialogical games as introduced by Lorenzen and Lorenz describe a reasoning technique for intuitionistic and classical predicate logic: two players (proponent and opponent) argue about the validity of a given formula according to predefined rules. If the proponent has a winning strategy then the formula is proven to be valid. The underlying game rules can be modified to have an impact on proof search strategies and increase the efficiency of such a searching process. In this paper, a multi-agent version of dialogical logic is introduced that corresponds more to multi-conclusion sequent calculi for propositional intuitionistic logic rather than single-conclusion ones which are more related to two-player dialogues. We also consider an extension for the normal modal logic S4. The rules lead us to a normalization of a proof, let us focus on the proponents’ relevant decisions, and therefore give explicit directives that increase compactness of the proofsearching process. This allows us to perform parts of the proof in a parallel way. We prove soundness and completeness of these multi-agent systems.