The main objective of the project is the study and development of efficient systems that allow to extract information in the context of knowledge bases or sources that contain incomplete, vague or inconsistent information. From the theoretical point of view, we intend to advance in the study of appropriate logics to describe vague and uncertain information, mainly t-norm based fuzzy logics and modal extensions to reason about graded preferences and uncertainty, and fuzzy description logics as terminological knowledge representation languages involving fuzzy concepts and relations. On the other hand, we intend to advance the study of efficient systems for reasoning problems (e.g. consequence, subsumption) for these logics. these sources. In problems with inconsistent informa- tion, usual reasoning procedures can reach contradictory conclusions. So one of our goals is also to deepen in the application and development of logical argumentative models which present to the end user justified or warranted conclusions, and to extend these models to distributed environments, where knowledge is distributed between different agents. To limit the maximum response time of the reasoning systems we will also examine the application of efficient transformations based on the problems of satisfiability and maximum satisfiability, for which there are highly efficient algorithms. Finally, we will study the use of reasoning systems studied and developed in different application do- mains, such as effective reasoning in a graded BDI agent architecture, optimization with preferences, decision support in medical diagnosis and management of online political discussions.

MaToMUVI is a FP7-PEOPLE-2009-IRSES project (PIRSES-GA-2009- 247584)

This project pivots around the satisfiability problem for logical languages including propositional logic (SAT), constraint satisfaction problems (CSP), and the fuzzy extension of description logics (FDL). Our purpose is to advance in each of the three areas using the synergy between the four groups that was initiated by previous joint projects. The concrete goals of the proposal are the following.

In SAT we want to study the structure of instances arising in industry, and apply this knowledge to develop more efficient solvers, both for SAT and for MaxSAT. In CSP we want to contribute to the problem of classification of tractable constraint languages. We will also study algorithms for geometric instances of MaxCSP and random instances for SAT of interest in computational complexity theory. In FDL we will study the expressive power and the complexity of the fragments of first-order fuzzy logic that correspond to description logics, and algorithms for satisfiability with special attention to the case of finitely valued FDLs.

Within soft constraint reasoning, weighted CSP (WCSP) provide a very convenient framework for modeling and solving many real-world optimization problems. Motivated for the relevance of WCSP model, this project aims at developing efficient solving algorithms for this model. We diferentiate between the centralized approach, where a WCSP instance is kept in a single computer, and the more recent distributed approach, where the instance is distributed among different computers (but none of them contains the whole instance). We also give special attention to the boolean case (namely, when variables only have two values to chose from) because it extends the famous boolean satisfiability problem (SAT) that is ubiquous in Computer Science. SAT solvers have improved their performance dramatically in the last 15 years, and some of the techniques responsible of this sucess can also be incorporated to boolean WCSP (being Max-SAT the most popular problem of this class). In the centralized case, we intend to achieve the overall goal by enhancing existing search algorithms with sophisticated techniques such as backjumping, learning and adaptive inference, and by improving current implementations with tailored linear programming solvers and more advanced data structures. In the distributed case, we intend to achieve the goal by combining existing search algorithms with local consistency enforcement and inference. In the distributed context, we also want to collect and/or build sets of benchmarks in order to compare the different alternatives. This project combines two research groups with complementary expertise.

The main goal of the project is the study and development of efficient systems, able to cope with
information from knowledge sources consisting on incomplete information, hence, inconsistent and
vague information. On the one hand, we want to investigate the proper logics to describe such information types, mainly t-norm based logics and fuzzy extensions for description logics. On the other hand, we
will study efficient systems for automatic reasoning, able to infer valid information from the above
mentioned knowledge sources. As the obtained information may be inconsistent, the reasoning
procedures may conclude on wrong information, so, an objective will be to study the application
and development of argumentative models, able to justify the soundness of the obtained conclusions
in front of the final user. In order to bound the response time of the reasoning system we will explore
efficient transformations based on satisfiability and maximum satisfiability problems, that already
have highly efficient solving algorithms. Finally, through the worst-case and typical complexity
study, we will bound the solving hardness for some particular reasoning problems. For typical
case complexity, we will employ either generators of synthetic problems, or real problems obtained
from semantic web ontologies but including uncertainty and vagueness in the information encoded,
according to the studied fuzzy description logics of this project.

Funding: 81.554 €

Spanish AC project corresponding to the EUROCORES FP006 project "Logical Models for Reasoning under Vague Information (LoMoReVI)

The main goal is to develop "formal systems combining fuzziness with both uncertainty and truthlikeness". Fuzziness refers to gradual and vague properties, and most successful information based models to reason with vague propositions are those systems of mathematical fuzzy logic called t-norm based fuzzy logics. On the other hand, uncertainty models deal with incomplete information, and from a logical point of view, uncertainty formalisms are captured by intensional, modal-like logics, ... which are non-truth functional. Truthlikeness, probably the less known of the above three notions, can be regarded as a special case of the more general concept of similarity and its logical counterpart as some form of similarity-based reasoning, where the truthlike value of a sentence is considered as its degree of proximity to the truth (even though it may not be true).

We think that defining modal many-valued logical systems is the right way to attack this combination problem, and this will fill an existing gap in the literature. Our efforts will be devoted to semantic issues. In particular we will study the adaptation of the dialogue game semantics for fuzzy logics, which is also a common focus of interest of the other two partners of the full Eurocores project (Prague and Vienna), to some modal expansions of t-norm based fuzzy logics relevant to the above mentioned combinations. Additional issues over the above t-norm based logical systems that we will develop are fuzzy description logics, temporal and dynamic extensions of modal many-valued logics, as well as flexible inconsistency handling mechanisms such as (i) revision/merging operators which have been scarcely considered in the literature in the many-valued context, or (ii) argumentation models in the presence of vagueness/uncertainty.

Constraint reasoning techniques, developed in the context of AI research, have successfully solved many real problems. Although it is a mature field, there are many important active lines of research such as open CSPs, distributed CSPs, quantified CSPs and soft constraint problems. Another well-known AI topic is Planning. It has recently gained new strenth in the research community due to its reformulation in terms of graphs, search and constraint satisfaction. In this project we want to make progress in the open lines of research of both fields. We also want to exploit the close relation between constraint processing and planning. Our objectives are:

• Constraint reasoning. Our goal is to contribute to the efficient resolution of the new paradigms (open, distributed and quantified CSPs) as well as continue our work on soft constraints, where we have already made relevant contributions, extending the results to closely related models such as clausal formulas or bayesian networks. Since the problem is in general untractable, we also want to identify tractable classes (soluble in polynomial time).
• Planning. Our goal is to refine the methods based on heuristic search for planning. We also want to study and develop the combination of search and inference. We want to exploit the existence of symmetries to decrease the solving effort, which is a well-known topic in the constraint community.

We present this project as a continuation of REPLI (TIC2002-04470-C03) motivated by the good results and experience that was achieved. We have now a larger and more experienced team of researchers. The benefits of the project will be the accomplishment of the previous goals as well as the integration of different research groups with complementary expertise.

Constraint reasoning techniques, developed in the context of AI research, have successfully solved many real problems. Although it is a mature field, there are many important active lines of research such as open CSPs, distributed CSPs, quantified CSPs and soft constraint problems. Another well-known AI topic is Planning. It has recently gained new strenth in the research community due to its reformulation in terms of graphs, search and constraint satisfaction. In this project we want to make progress in the open lines of research of both fields. We also want to exploit the close relation between constraint processing and planning. Our objectives are:
Constraint reasoning. Our goal is to contribute to the efficient resolution of the new paradigms (open, distributed and quantified CSPs) as well as continue our work on soft constraints, where we have already made relevant contributions, extending the results to closely related models such as clausal formulas or bayesian networks. Since the problem is in general untractable, we also want to identify tractable classes (soluble in polynomial time).

Planning

Our goal is to refine the methods based on heuristic search for planning. We also want to study and develop the combination of search and inference. We want to exploit the existence of symmetries to decrease the solving effort, which is a well-known topic in the constraint community.

We present this project as a continuation of REPLI (TIC2002-04470-C03) motivated by the good results and experience that was achieved. We have now a larger and more experienced team of researchers. The benefits of the project will be the accomplishment of the previous goals as well as the integration of different research groups with complementary expertise.

The project, planned as a continuation of project LOGFAC (TIC2001-1577-C03-01), has three basic objectives. The first one is to continue the logic and algebraic study of t-norm based many-valued logics in the frame of both residuated and substructural logics. The second one is the formalization, within the framework of the above logics, of several deductive soft computing mechanisms, based on fuzzy logic, to deal with fuzziness and imprecision. The last one is to continue theoretical and experimental research on algorithms for the satisfiability problem in many-valued logics and their application to computational problems, in particular to constraint satisfaction problems with hard and soft constraints problems.