VLDB 2026 Research / reviewers in the wild / expert
Matteo Cristani
dblp:96/6270
· DBLP profile ↗
65ranked-venue papers
40as first author
17since 2021 · last 2026
0000-0001-5680-0080ORCID · corroborated
Domains — the database's venue-derived domains; a paper can count in several
Artificial intelligence and machine learning · 51 · 34 first-author · 12 since 2021Graphics, computer vision, multimedia, augmented reality and games · 11 · 8 first-author · 2 since 2021Theory of computation · 7 · 2 first-author · 3 since 2021Applied, interdisciplinary, general and emerging computing · 5 · 1 first-author · 3 since 2021Databases, data management, data science and information retrieval · 4 · 3 first-author · 1 since 2021Security and privacy · 2 · 1 first-authorSoftware engineering, systems software and programming languages · 2 · 1 first-author
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2026 | Computing the Distribution of the Traces of a Business Process by Their Lengths
Matteo Cristani, Tewabe Chekole Workneh, Claudio Tomazzoli, Federica Paci |
IEA/AIE (3) | 1 |
| 2025 | A Formal Methodology for Risk Estimation in Business Process Management
Matteo Cristani, Tewabe Chekole Workneh, Claudio Tomazzoli, Federica Paci |
PRIMA | 1 |
| 2025 | Business Process Compliance with impact constraintsabstractBusiness Process Compliance is a family of methods to evaluate Business Processes in terms of the existence of one execution (one trace) that does not violate constraints superimposed on the process itself. The dual version is formulated as the superimposition of a set of constraints and consequent evaluation of the process for all the executions . These problems are relevant to a large part of actual applications, especially those in the context of regulatory compliance where we aim at verifying the process against a normative background (including, for instance, soft ones, such as guidelines, product specification, and product standards) or goals fixed by the owner of the process. In this paper we discuss one new type of compliance, that is impact compliance , devised to verify when a process respects a set of constraints, to establish that certain amounts, measuring the undesired effects of the tasks executed to implement the process, are below given limits . In the current literature on Business Process Management, Business Process Analysis, and Business Process Compliance, this type of compliance checking process has not yet been addressed. As we demonstrate in this paper, this problem is significant and complex to address. In particular, we show that the checking problems described above are, under certain structural conditions, polynomially solvable on deterministic machines. In general, however, the first problem is NP-complete whilst the second is polynomially solvable on deterministic machines. Tewabe Chekole Workneh, Pietro Sala, Romeo Rizzi, Matteo Cristani |
Inf. Syst. | 4 |
| 2025 | Revising non-monotonic theories with sufficient and necessary conditions: the case of Defeasible LogicabstractAbstract In the setting of Defeasible Logic, we deal with the problem of revising and contracting a non-monotonic theory while minimizing the number of rules to be removed from the theory itself. The process is based on the notions of a set of rules being necessary and sufficient in order to prove a claim. The substantial difference among classical and non-monotonic reasoning processes makes this issue significant in order to achieve the correct revision processes. We show that the process is however computationally hard, and can be solved in polynomial time on non-deterministic machines. Francesco Olivieri, Matteo Cristani, Guido Governatori, Luca Pasetto, Antonino Rotolo, Simone Scannapieco, Claudio Tomazzoli, Tewabe Chekole Workneh |
J. Log. Comput. | 2 |
| 2024 | AI-driven quasi-optimal security camera positioning for harbor controlabstractThe problem of positioning cameras for optimal monitoring of a given surface, while given a budget, is quite evidently hard. Moreover, it is very difficult to collect information that could reduce the span of admissible solutions and therefore downsize the problem itself. In this paper, as referred to a specific case in a critical infrastructure, the harbour of the Ventotene Island in southern Italy, how the above mentioned problem can be solved in an effective way by employing a Genetic algorithm. The approach is also generalised in order to solve similar problems. Claudio Tomazzoli, Matteo Cristani, Tewabe Chekole Workneh, Francesco Olivieri, Simone Scannapieco |
KES | 2 |
| 2024 | Data Augmentation for Business Process Alignment: Proof of Concept and Experimental Design
Matteo Cristani, Mattia Zorzan, Tewabe Chekole Workneh, Claudio Tomazzoli |
KES-AMSTA | 1 |
| 2024 | AI-Driven Nitrogen Stress Management in Cereal Crops via Drone Technology
Hailemicael Lulseged Yimer, Matteo Cristani, Tewabe Chekole Workneh, Claudio Tomazzoli |
KES-AMSTA | 2 |
| 2023 | The architecture of a reasoning system for Defeasible Deontic LogicabstractWe present the architecture of Houdini-2.0, a reasoning system that computes the extension of a defeasible deontic theory given as input, the process of computing the consequences of the rules expressed in the theory itself. The decision process is a sceptical, non-monotonic, and it allows us to determine which prescriptive behaviours are in force (obligations, permissions, prohibitions) along with propositional ones. The system is based on pre-existing algorithmic solutions, and it is implemented as an online platform to deploy the results of a computation in several use cases, including those that pertain legal domain. Matteo Cristani, Guido Governatori, Francesco Olivieri, Luca Pasetto, Francesco Tubini, Celeste Veronese, Alessandro Villa, Edoardo Zorzi |
KES | 1 |
| 2022 | Classification Rules Explain Machine Learning
Matteo Cristani, Francesco Olivieri, Tewabe Chekole Workneh, Luca Pasetto, Claudio Tomazzoli |
ICAART (3) | 1 |
| 2022 | Forensic Analysis of Text and Messages in Smartphones by a Unification Rosetta Stone Procedure
Claudio Tomazzoli, Simone Scannapieco, Matteo Cristani |
IEA/AIE | 3 |
| 2022 | Stable Normative ExplanationsabstractModelling the concept of explanation is a central matter in AI systems, as it provides methods for developing eXplainable AI (XAI). When explanation applies to normative reasoning, XAI aims at promoting normative trust in the decisions of AI systems: in fact, such a trust depends on understanding whether systems predictions correspond to legally compliant scenarios. This paper extends to normative reasoning a work by Governatori et al. (2022) on the notion of stable explanations in a non-monotonic setting: when an explanation is stable, it can be used to infer the same normative conclusion independently of other facts that are found afterwards. Guido Governatori, Francesco Olivieri, Antonino Rotolo, Matteo Cristani |
JURIX | 4 |
| 2022 | Impact Logic: Reasoning with resources and lossesabstractThe notion of Business Process Compliance has been widely discussed as one of the most important issues to be solved when comparing the description of a business process against a normative background. Many changes have been provided to the basic notion above. The introduction of changes to the normative background has been considered, as well as the idea of Compliance by Design. In this paper, we discuss how to devise a business process that is compliant to an impact constraint set. We shall show that the technical problems determined by this concept are all within the horizon of adding to the logical framework the notions of Resource and Product. Matteo Cristani, Francesco Olivieri, Luca Pasetto, Claudio Tomazzoli, Tewabe Chekole Workneh |
KES | 1 |
| 2022 | Inference to the Stable Explanations
Guido Governatori, Francesco Olivieri, Antonino Rotolo, Matteo Cristani |
LPNMR | 4 |
| 2021 | Computing Defeasible Meta-logic
Francesco Olivieri, Guido Governatori, Matteo Cristani, Abdul Sattar 0001 |
JELIA | 3 |
| 2021 | Computing Private International LawabstractThis paper develops a new comprehensive computational framework for reasoning about private international law that encompasses the reasoning patterns modeled by previous works [3,8,9]. The framework is a multi-modal extension of [10] preserving some nice properties of the original system, including some efficient algorithms to compute the extensions of normative theories representing legal systems. Guido Governatori, Francesco Olivieri, Antonino Rotolo, Abdul Sattar 0001, Matteo Cristani |
JURIX | 5 |
| 2021 | Revising Ethical Principles and Norms in Hybrid Societies: Basic Principles and Issues
Matteo Cristani, Francesco Olivieri, Luca Pasetto |
KES-AMSTA | 1 |
| 2021 | Text Analytics Can Predict Contract Fairness, Transparency and ApplicabilityabstractThere is a growing attention, in the research communities of political economics, onto the potential of text analytics in classifying documents with economic content. This interest extends the data analytics approach that has been the traditional base for economic theory with scientific perspective. To devise a general method for prediction applicability, we identify some phases of a methodology and perform tests on a large well-structured repository of resource contracts containing documents related to resources. The majority of these contracts involve mining resources. In this paper we prove that, by the usage of text analytics measures, we can cluster these documents on three indicators: fairness of the contract content, transparency of the document themselves, and applicability of the clauses of the contract intended to guarantee execution on an international basis. We achieve these results, consistent with a gold-standard test obtained with human experts, using text similarity b (More) Nicola Assolini, Adelaide Baronchelli, Matteo Cristani, Luca Pasetto, Francesco Olivieri, Roberto Ricciuti, Claudio Tomazzoli |
WEBIST | 3 |
| 2020 | A knowledge-intensive methodology for explainable sales predictionabstractInsert here your abstract text. Matteo Cristani, Luca Pasetto, Claudio Tomazzoli |
KES | 1 |
| 2020 | Protecting the environment: a multi-agent approach to environmental monitoringabstractIn this paper we discuss a transition model from commonly adopted models of data gathering, transfer and management for environmental monitoring towards more sophisticated ones based on Artificial Intelligence and IoT. The transition model is based on the paradigm of multiple agent systems. The adoption of this transition model is motivated by the need to improve effectiveness, efficiency and interoperability of environmental monitoring by simultaneously guaranteeing its sustainability in economic terms. Matteo Cristani, Luca Pasetto, Claudio Tomazzoli |
KES | 1 |
| 2020 | Characterising Functional Brain Connectivity as Social Network: the Transtopic Centrality IndexabstractGraph-based network modeling is becoming increasingly pervasive touching very different fields. Among these are social networks analysis and brain connectivity modeling. Though apparently very far apart, these two domains share the same questions about how the underlying network is structured and h ow this can be measured. This determines an a-priori unexpected convergence of the research efforts of two different communities, that is neurosciences and information technology. In this work, we put forth some basic issues emerging from the overlaps of the two domains and propose a first simple measure allowing to capture one among the features of interest: the transtopic closeness centrality. To this end, the related concepts are briefly recalled and two case studies are considered. Then, relying on social network analysis principles, the transposition to functional brain networks is proposed highlighting and discussing some of the inherent critical issues. Gloria Menegaz, Claudio Tomazzoli, Matteo Cristani, Ilaria Boscolo Galazzo, Silvia Francesca Storti |
Fundam. Informaticae | 3 |
| 2019 | Non-monotonic Reasoning on the Web
Matteo Cristani |
ICWE | 1 |
| 2019 | "It Could Be Worse, It Could Be Raining": Reliable Automatic Meteorological Forecasting for Holiday Planning
Matteo Cristani, Francesco Domenichini, Claudio Tomazzoli, Margherita Zorzi |
IEA/AIE | 1 |
| 2019 | Automatic Generation of Dictionaries: The Journalistic Lexicon Case
Matteo Cristani, Claudio Tomazzoli, Margherita Zorzi |
IEA/AIE | 1 |
| 2019 | Advancements in Resource-Driven Substructural Defeasible Logic
Francesco Olivieri, Guido Governatori, Matteo Cristani |
JELIA | 3 |
| 2019 | Automatic Clustering of User Communities
Matteo Cristani, Michele Manzato, Simone Scannapieco, Claudio Tomazzoli, Stefano-Francesco Zuliani |
KES-AMSTA | 1 |
| 2019 | Web Literature, Authorship Attribution and Editorial Workflow Ontologies
Matteo Cristani, Francesco Olivieri, Claudio Tomazzoli, Margherita Zorzi |
KES-AMSTA | 1 |
| 2019 | Non-monotonic Collective Decisions
Matteo Cristani, Francesco Olivieri, Guido Governatori |
PRIMA | 1 |
| 2019 | Revision of defeasible preferences
Guido Governatori, Francesco Olivieri, Matteo Cristani, Simone Scannapieco |
Int. J. Approx. Reason. | 3 |
| 2018 | A Formal Approach to Analyzing Cyber-Forensics Evidence
Erisa Karafili, Matteo Cristani, Luca Viganò 0001 |
ESORICS (1) | 2 |
| 2018 | A simple algorithm for the lexical classification of comparable adjectivesabstractLexical classification is one of the most widely investigated fields in (computational) linguistic and Natural language Processing. Adjectives play a significant role both in classification tasks and in applications as sentiment analysis. In this paper a simple algorithm for lexical classification of comparable adjectives, called MORE (coMparable fORm dEtector), is proposed. The algorithm is efficient in time. The method is a specific unsupervised learning technique. Results are verified against a reference standard built from 80 manually annotated lists of adjective. The algorithm exhibits an accuracy of 76%. Matteo Cristani, Ilaria Chitó, Claudio Tomazzoli, Margherita Zorzi |
KES | 1 |
| 2018 | It could rain: weather forecasting as a reasoning processabstractMeteorological forecasting is the process of providing reliable prediction about the future weathear within a given interval of time. Forecasters adopt a model of reasoning that can be mapped onto an integrated conceptual framework. A forecaster essentially precesses data in advance by using some models of machine learning to extract macroscopic tendencies such as air movements, pressure, temperature, and humidity differentials measured in ways that depend upon the model, but fundamentally, as gradients. Limit values are employed to transform these tendencies in fuzzy values, and then compared to each other in order to extract indicators, and then evaluate these indicators by means of priorities based upon distance in fuzzy values. We formalise the method proposed above in a workflow of evaluation steps, and propose an architecture that implements the reasoning techniques. Matteo Cristani, Francesco Domenichini, Francesco Olivieri, Claudio Tomazzoli, Margherita Zorzi |
KES | 1 |
| 2018 | ONTO-PLC: An ontology-driven methodology for converting PLC industrial plants to IoTabstractWe present the new methodology ONTO-PLC to deliver software programs on system-on-chip or single-board computers used to control industrial plants, as substitutes for programmable logic control technologies. The methodology is ontology-driven based on the abstract description of the plant at a level in which the plant itself is viewed as a set of instruments, each instrument being a set of machineries coordinated in functional terms by a control system, formed by sensors and actuators, under the control of an abstract model of behavior delivered by means of an extended finite state machine. Matteo Cristani, Florenc Demrozi, Claudio Tomazzoli |
KES | 1 |
| 2018 | Sending Messages in Social Networks
Matteo Cristani, Francesco Olivieri, Claudio Tomazzoli, Guido Governatori |
KES-AMSTA | 1 |
| 2018 | Towards a Logical Framework for Diagnostic Reasoning
Matteo Cristani, Francesco Olivieri, Claudio Tomazzoli, Margherita Zorzi |
KES-AMSTA | 1 |
| 2018 | Automatic Detection of Device Types by Consumption Curve
Claudio Tomazzoli, Matteo Cristani, Simone Scannapieco, Francesco Olivieri |
KES-AMSTA | 2 |
| 2018 | Resource-Driven Substructural Defeasible Logic
Francesco Olivieri, Guido Governatori, Matteo Cristani, Nick R. T. P. van Beest, Silvano Colombo Tosatto |
PRIMA | 3 |
| 2017 | Changes to temporary normsabstractNormative systems accommodate temporary norms of several types, which can also be modified in different, and codified ways. In this paper we address the problem of modifying temporary norms that are represented by means of the combination of two known formalisms in the current literature. The framework evolves from a known one, which provides a system of norms at two distinct layers, and represents changes at the two layers as means to provide room for the codified change types. This results in four novel operators that anticipate and extend norms in two different combined ways, by preserving or not the effects of the norms in the period of time generated by the temporal modifications. We study these new operators and show how they relate to the operators of annulment and abrogation analysed elsewhere. Matteo Cristani, Francesco Olivieri, Antonino Rotolo |
ICAIL | 1 |
| 2017 | Meaning Negotiation with Defeasible Logic
Matteo Cristani, Antonino Rotolo |
KES-AMSTA | 1 |
| 2016 | Defeasible Reasoning about Electric ConsumptionsabstractConflicting rules and rules with exceptions are very common in natural language specification to describe the behaviour of devices operating in a real-world context. This is common exactly because those specifications are processed by humans, and humans apply common sense and strategic reasoning about those rules. In this paper, we deal with the challenge of providing, step by step, a model of energy saving rule specification and processing methods that are used to reduce the consumptions of a system of devices. We argue that a very promising non-monotonic approach to such a problem can lie upon Defeasible Logic. Starting with rules specified at an abstract level, but compatibly with the natural aspects of such a specification (including temporal and power absorption constraints), we provide a formalism that generates the extension of a basic defeasible logic, which corresponds to turned on or off devices. Matteo Cristani, Claudio Tomazzoli, Erisa Karafili, Francesco Olivieri |
AINA | 1 |
| 2016 | Semantic Social Network Analysis Foresees Message FlowsabstractSocial Network Analysis is employed widely as a means to compute the probability that a given message flows through a social network. This approach is mainly grounded upon the correct usage of three basic graph-theoretic measures: degree centrality, closeness centrality and betweeness centrality. We show that, in general, those indices are not adapt to foresee the flow of a given message, that depends upon indices based on the sharing of interests and the trust about depth in knowledge of a topic. We provide an extended model, that is a simplified version of a more general model already documented in the literature, the Semantic Social Network Analysis, and show that by means of this model it is possible to exceed the drawbacks of general indices discussed above. Matteo Cristani, Claudio Tomazzoli, Francesco Olivieri |
ICAART (1) | 1 |
| 2016 | A Multimodal Approach to Relevance and Pertinence of Documents
Matteo Cristani, Claudio Tomazzoli |
IEA/AIE | 1 |
| 2016 | Sequence Semantics for Normative Agents
Guido Governatori, Francesco Olivieri, Erica Calardo, Antonino Rotolo, Matteo Cristani |
PRIMA | 5 |
| 2016 | The rationale behind the concept of goalabstractAbstract The paper proposes a fresh look at the concept of goal and advances that motivational attitudes like desire, goal and intention are just facets of the broader notion of (acceptable) outcome. We propose to encode the preferences of an agent as sequences of “alternative acceptable outcomes”. We then study how the agent's beliefs and norms can be used to filter the mental attitudes out of the sequences of alternative acceptable outcomes. Finally, we formalise such intuitions in a novel Modal Defeasible Logic and we prove that the resulting formalisation is computationally feasible. Guido Governatori, Francesco Olivieri, Simone Scannapieco, Antonino Rotolo, Matteo Cristani |
Theory Pract. Log. Program. | 5 |
| 2015 | Improving Energy Saving Techniques by Ambient Intelligence SchedulingabstractEnergy saving is one of the most challenging aspects of modern ambient intelligence technologies, for both domestic and business usages. In this paper we show how to combine Ambient Intelligence and Artificial Intelligence techniques to solve the problem of scheduling a set of devices under a given set of constraints, like limits to the maximal energy usage (Energy Span) and maximal energy absorption (Energy Peak). We provide a method that can be used to schedule the usage of devices in a given environment in a way that respects the input constraints. We adapt an existent approach to scheduling for Ambient Intelligence to a specific framework and exhibit a sample usage for a real life system, Elettra, that is in use in an industrial context. Matteo Cristani, Erisa Karafili, Claudio Tomazzoli |
AINA | 1 |
| 2015 | Proceedings in Adaptation, Learning and Optimization
Matteo Cristani, Francesco Olivieri, Katia Santacà |
IES | 1 |
| 2015 | Compliant Business Processes with Exclusive Choices from Agent Specification
Francesco Olivieri, Matteo Cristani, Guido Governatori |
PRIMA | 2 |
| 2014 | Strategic Argumentation is NP-CompleteabstractWe study the complexity of the Strategic Argumentation Problem for 2-player dialogue games where a player should decide what move (set of rules) to play at each turn in order to prove (disprove) a given thesis. We show that this is an NP-complete problem. Guido Governatori, Francesco Olivieri, Simone Scannapieco, Antonino Rotolo, Matteo Cristani |
ECAI | 5 |
| 2014 | A Multimodal Approach to Exploit Similarity in Documents
Matteo Cristani, Claudio Tomazzoli |
IEA/AIE (1) | 1 |
| 2013 | A complete tableau procedure for risk analysisabstractIn many real-life situations making a decision entails evaluating the risks associated with the decision, which in turn requires reasoning about events and their relations. In addition to the simpler and better-understood notions of causation and precondition, in this paper we focus on block (or prevention), which is the relation established between an event φ1and another event φ2such that the number of occurrences of φ2decreases whenever φ1occurs, and mitigation, where the occurrence of φ1reduces the “negative” (for the particular decision we are considering) consequences of the occurrence of φ2. By introducing two further counting operators and the notion of interval of observation, we give here a sound and complete tableau system along with a systematic tableau construction procedure. Matteo Cristani, Erisa Karafili, Luca Viganò 0001 |
CRiSIS | 1 |
| 2013 | Compliant Business Process Design by Declarative Specifications
Francesco Olivieri, Guido Governatori, Simone Scannapieco, Matteo Cristani |
PRIMA | 4 |
| 2013 | A Methodology for Plan Revision under Norm and Outcome Compliance
Simone Scannapieco, Guido Governatori, Francesco Olivieri, Matteo Cristani |
PRIMA | 4 |
| 2011 | Blocking Underhand Attacks by Hidden Coalitions
Matteo Cristani, Erisa Karafili, Luca Viganò 0001 |
ICAART (2) | 1 |
| 2010 | An Intelligent System for Gathering Rates of Local Taxes on the Web
Matteo Cristani, Nicoletta Gabrielli |
IEA/AIE (1) | 1 |
| 2009 | Learning as Meaning Negotiation: A Model Based on English Auction
Elisa Burato, Matteo Cristani |
KES-AMSTA | 2 |
| 2009 | Approximate solutions of moral dilemmas in multiple agent system
Matteo Cristani, Elisa Burato |
Knowl. Inf. Syst. | 1 |
| 2008 | Ontology-Driven Approximate Duplicate Elimination of Postal Addresses
Matteo Cristani, Alessio Gugole |
IEA/AIE | 1 |
| 2007 | Contract clause negotiation by game theoryabstractSeveral recent investigations in Artificial Intelligence and Law have dealt with the problem of "contract clause negotiation", often seen as a specific type of "meaning negotiation". Though a consistent effort has been spent in modelling situations in which two agents mediate the rules to govern a cooperation stipulated in a contract, there is still a lack of formalisation for such a task from a logical viewpoint, and specifically, no model exists, to the best of our knowledge, in the current literature, that represents the negotiation process directly using techniques of the Theory of zero-sum Games, although the majority of scholars admit that the behaviour of agents negotiating in contract definition are quite well modelled by that approach. In particular, we propose to model peer-to-peer meaning negotiation process by a zerosum game, known in Game Theory literature as Bargaining. This approach shows its usefulness in the development of a methodology for obtaining shared theories from distinct ones, and we apply it directly in a framework in which it is possible to represent Contract Clause Negotiation processes. Elisa Burato, Matteo Cristani |
ICAIL | 2 |
| 2007 | Modelling Social Attitudes of Agents
Matteo Cristani, Elisa Burato |
KES-AMSTA | 1 |
| 2005 | A Survey on Ontology Creation MethodologiesabstractIn the current literature of knowledge management and artificial intelligence, several different approaches to the problem have been carried out of developing domain ontologies from scratch. All these approaches deal fundamentally with three problems: (1) providing a collection of general terms describing classes and relations to be employed in the description of the domain itself; (2) organizing the terms into a taxonomy of the classes by the ISA relation; and (3) expressing in an explicit way the constraints that make the ISA pairs meaningful. Though a number of such approaches can be found, no systematic analysis of them exists which can be used to understand the inspiring motivation, the applicability context, and the structure of the approaches. In this paper, we provide a framework for analyzing the existing methodologies that compares them to a set of general criteria. In particular, we obtain a classification based upon the direction of ontology construction; bottom-up are those methodologies that start with some descriptions of the domain and obtain a classification, while top-down ones start with an abstract view of the domain itself, which is given a priori. The resulting classification is useful not only for theoretical purposes but also in the practice of deployment of ontologies in Information Systems, since it provides a framework for choosing the right methodology to be applied in the specific context, depending also on the needs of the application itself. Matteo Cristani, Roberta Cuel |
Int. J. Semantic Web Inf. Syst. | 1 |
| 2004 | Fundamental Issues of Aesthetic Knowledge Representation
Matteo Cristani, Francesco Bellomi |
ECAI | 1 |
| 2004 | The complexity of constraint satisfaction problems for small relation algebras
Matteo Cristani, Robin Hirsch |
Artif. Intell. | 1 |
| 2002 | Many-Sorted Preference Relations
Matteo Cristani |
KR | 1 |
| 2000 | Spatial Locations via Morpho-Mereology
Matteo Cristani, Anthony G. Cohn 0001, Brandon Bennett |
KR | 1 |
| 1999 | The Complexity of Reasoning about Spatial CongruenceabstractIn the recent literature of Artificial Intelligence, an intensive research effort has been spent, for various algebras of qualitative relations used in the representation of temporal and spatial knowledge, on the problem of classifying the computational complexity of reasoning problems for subsets of algebras. The main purpose of these researches is to describe a restricted set of maximal tractable subalgebras, ideally in an exhaustive fashion with respect to the hosting algebras. In this paper we introduce a novel algebra for reasoning about Spatial Congruence, show that the satisfiability problem in the spatial algebra MC-4 is NP-complete, and present a complete classification of tractability in the algebra, based on the individuation of three maximal tractable subclasses, one containing the basic relations. The three algebras are formed by 14, 10 and 9 relations out of 16 which form the full algebra. Matteo Cristani |
J. Artif. Intell. Res. | 1 |
| 1997 | On Finding a Solution in Temporal Constraint Satisfaction Problems
Alfonso Gerevini, Matteo Cristani |
IJCAI | 2 |