Pasar al contenido principal

RAZONAMIENTO, SATISFACCION Y OPTIMIZACION

TIN2015-71799-C2-1-P

•
Nombre agencia financiadora Ministerio de Economía y Competitividad
Acrónimo agencia financiadora MINECO
Programa Programa Estatal de Fomento de la Investigación Científica y Técnica de Excelencia
Subprograma Subprograma Estatal de Generación de Conocimiento
Convocatoria Proyectos de I+D (Excelencia / Generación de Conocimiento)
Año convocatoria 2015
Plan Estatal 2013-2016 Plan Estatal de Investigación Científica y Técnica y de Innovación
Unidad de gestión Secretaría de Estado de Educación, Formación Profesional y Universidades
Centro beneficiario AGENCIA ESTATAL CONSEJO SUPERIOR DE INVESTIGACIONES CIENTIFICAS (CSIC)
Identificador persistente http://dx.doi.org/10.13039/501100003329

Resultados relacionados

Resultados totales (Incluyendo duplicados): 32
Encontrada(s) 1 página(s)

Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Community Structure in Industrial SAT Instances

  • Ansótegui Gil, Carlos José
  • Bonet, Maria Luisa
  • Giráldez-Cru, Jesús
  • Levy, Jordi
Modern SAT solvers have experienced a remarkable progress on solving industrial instances. It is believed that most of these successful techniques exploit the underlying structure of industrial instances. Recently, there have been some attempts to analyze the structure of industrial SAT instances in terms of complex networks, with the aim of explaining the success of SAT solving techniques, and possibly improving them. In this paper, we study the community structure, or modularity, of industrial SAT instances. In a graph with clear community structure, or high modularity, we can find a partition of its nodes into communities such that most edges connect variables of the same community. Representing SAT instances as graphs, we show that most application benchmarks are characterized by a high modularity. On the contrary, random SAT instances are closer to the classical Erdös-Rényi random graph model, where no structure can be observed. We also analyze how this structure evolves by the effects of the execution of a CDCL SAT solver, and observe that new clauses learned by the solver during the search contribute to destroy the original structure of the formula. Motivated by this observation, we finally present an application that exploits the community structure to detect relevant learned clauses, and we show that detecting these clauses results in an improvement on the performance of the SAT solver. Empirically, we observe that this improves the performance of several SAT solvers on industrial SAT formulas, especially on satisfiable instances., This work is partially supported by the EU H2020 Research and Innovation Programme under the LOGISTAR project (Grant Agreement No. 769142), MINECO-FEDER projects RASO (TIN2015-71799-C2-1-P) and TASSAT3 (TIN2016-76573-C2-2-P), the Spanish Ministerio de Econom´ıa y Competitividad under the EXASOCO project (ref. PGC2018-101216- B-I00), including European Regional Development Funds (ERDF). The third author is also supported by a MICINN Juan de la Cierva fellowship (ref. FJCI-2017-32420).
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Generating SAT instances with community structure

  • Giráldez-Crú, Jesús
  • Levy, Jordi
Nowadays, modern SAT solvers are able to efficiently solve many industrial, or real-world, SAT instances. However, the process of development and testing of new SAT solving techniques is conditioned to the finite and reduced number of known industrial benchmarks. Therefore, new models of random SAT instances generation that capture realistically the features of real-world problems can be beneficial to the SAT community. In many works, the structure of industrial instances has been analyzed representing them as graphs and studying some of their properties, like modularity. In this work, we use the notion of modularity to define a new model of generation of random SAT instances with community structure, called Community Attachment. For high values of modularity (i.e., clear community structure), we realistically model pseudo-industrial random SAT formulas. This model also generates SAT instances very similar to classical random formulas using a low value of modularity. We also prove that the phase transition point, if exists, is independent on the modularity. We evaluate the adequacy of this model to real industrial SAT problems in terms of SAT solvers performance, and show that modern solvers do actually exploit this community structure. Finally, we use this generator to observe the connections between the modularity of the instance and some components of the solver, such as the variable branching heuristics or the clause learning mechanism., This work is partially supported by the MINECO/FEDER project RASO (TIN2015-71799-C2-1-P) and the CSIC project 201450E045, Peer Reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Expanding FL e w with a Boolean connective

  • Ertola-Biraben, Rodolfo C.
  • Esteva, Francesc
  • Godo, Lluis
We expand FL e w with a unary connective whose algebraic counterpart is the operation that gives the greatest complemented element below a given argument. We prove that the expanded logic is conservative and has the Finite Model Property. We also prove that the corresponding expansion of the class of residuated lattices is an equational class. © 2016, Springer-Verlag Berlin Heidelberg., The authors are thankful to annonymous reviewer for his/her comments that have helped to improve the final layout of this paper. The authors have been funded by the EU H2020-MSCA-RISE-2015 Project 689176–SYSMICS. Esteva and Godo have been also funded by the FEDER/MINECO Spanish project TIN2015-71799-C2-1-P, Peer Reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

On the existence of free models in fuzzy universal Horn classes

  • Costa, Vicent
  • Dellunde, Pilar
This paper is a contribution to the study of the universal Horn fragment of predicate fuzzy logics, focusing on some relevant notions in logic programming. We introduce the notion of term structure associated to a set of formulas in the fuzzy context and we show the existence of free models in fuzzy universal Horn classes. We prove that every equality-free consistent universal Horn fuzzy theory has a Herbrand model. © 2016 Elsevier B.V., This project has received funding from the European Union's Horizon 2020 research and innovation program under the Marie Sklodowska-Curie grant agreement No 689176 (SYSMICS project). Pilar Dellunde is also partially supported by the project RASO TIN2015-71799-C2-1-P (MINECO/FEDER) and the grant 2014SGR-118 from the Generalitat de Catalunya., Peer Reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Towards a probability theory for product logic: States, integral representation and reasoning

  • Flaminio, Tommaso
  • Godo, Lluis
  • Ugolini, Sara
The aim of this paper is to extend probability theory from the classical to the product t-norm fuzzy logic setting. More precisely, we axiomatize a generalized notion of finitely additive probability for product logic formulas, called state, and show that every state is the Lebesgue integral with respect to a unique regular Borel probability measure. Furthermore, the relation between states and measures is shown to be one–one. In addition, we study geometrical properties of the convex set of states and show that extremal states, i.e., the extremal points of the state space, are the same as the truth-value assignments of the logic. Finally, we axiomatize a two-tiered modal logic for probabilistic reasoning on product logic events and prove soundness and completeness with respect to probabilistic spaces, where the algebra is a free product algebra and the measure is a state in the above sense. © 2017 Elsevier Inc., The authors acknowledge partial support by the SYSMICS project ( EU H2020-MSCA-RISE-2015 Project 689176). Also, Flaminio and Godo acknowledge partial support by the FEDER/MINECO project TIN2015-71799-C2-1-P, Peer Reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Contribución de congreso (ConferenceOutput)

An Effective Learnt Clause Minimization Approach for CDCL SAT Solvers

  • Luo, Mao
  • Li, Chu Min
  • Xiao, Fan
  • Manyà, Felip
  • Lü, Zhipeng
Learnt clauses in CDCL SAT solvers often contain redundant literals. This may have a negative impact on performance because redundant literals may deteriorate both the effectiveness of Boolean constraint propagation and the quality of subsequent learnt clauses. To overcome this drawback, we define a new inprocessing SAT approach which eliminates redundant literals from learnt clauses by applying Boolean constraint propagation. Learnt clause minimization is activated before the SAT solver triggers some selected restarts, and affects only some learnt clauses during the search process. Moreover, we conducted an empirical evaluation on instances coming from the hard combinatorial and application categories of recent SAT competitions. The results show that a remarkable number of additional instances are solved when the approach is incorporated into five of the best performing CDCL SAT solvers. Copyright © 2018, IJCAI, Research partially supported by the National Natural Science Foundation of China (Grants no. 61370183, 61370184, 61472147), the Generalitat de Catalunya grant AGAUR 2014-SGR-118, and the MINECO-FEDER project RASO TIN2015-71799-C2-1-P., Peer Reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Contribución de congreso (ConferenceOutput)

An Exact Algorithm for the Maximum Weight Clique Problem in Large Graphs

  • Jiang, Hua
  • Li, Chu Min
  • Manyà, Felip
We describe an exact branch-and-bound algorithm for the maximum weight clique problem (MWC), called WLMC, that is especially suited for large vertex-weighted graphs. WLMC incorporates two original contributions: a preprocessing to derive an initial vertex ordering and to reduce the size of the graph, and incremental vertex-weight splitting to reduce the number of branches in the search space. Experiments on representative large graphs from real-world applications show that WLMC greatly outperforms relevant exact and heuristic MWC algorithms, and refute the prevailing hypothesis that exact MWC algorithms are less adequate for large graphs than heuristic algorithms. Copyright © 2017, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved., This work is supported by NSFC Grants No. 61272014, No.61370183, No. 61472147 and No. 61370184, the MeCS platform of the University of Picardie Jules Verne and the HPC platform of Jianghan Univeristy. The third author was supported by Mobility Grant PRX16/00215 of the Ministerio de Educación, Cultura y Deporte, the Generalitat de Catalunya grant AGAUR 2014-SGR-118, and the MINECO-FEDER project RASO TIN2015-71799-C2-1-P, Peer Reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

On the relation between modal and multi-modal logics over Lukasiewicz logic

  • Esteva, Francesc
  • Godo, Lluis
  • Rodriguez, Ricardo O.
Trabajo presentado en eI IEEE International Conference on Fuzzy Systems (FUZZ 2017), 9-12 July 2017., In a previous paper, it was shown that the (minimal) modal logic MŁ n c with fuzzy accessibility relations over the finite-valued Łukasiewicz logic Ł n and a corresponding multi-modal logic mMŁ n c (with a modality □ a for each value a in the n-valued Ł n -chain) had the same expressive power when the language is extended with truth-constants. In this paper we partially extend these results when replacing the underlying logic Ł n by the infinite-valued Łukasiewicz logic (with rational truth constants in the language). We prove that the (standard) tautologies of the modal logic MŁ n c (resp. mMŁ c ) are in fact the common tautologies of all the logics MŁ n c (resp. all the logics mMŁn) when letting n vary over N. This fact opens the door to show an alternative proof of the finite model property for these logics and hence their decidability., They acknowledge partial support by the H2020-MSCA-RISE-2015 project SYSMICS, the Spanish MINECO project RASO (TIN2015-71799-C2-1-P) and the Argentinean project PIP CONICET 11220150100412CO., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Corrigendum to “Towards a probability theory for product logic: States, integral representation and reasoning” [Int. J. Approx. Reason. 93 (2018) 199–218]

  • Flaminio, Tommaso
  • Godo, Lluis
  • Ugolini, Sara
The aim of this short note is to report on a counter-example by Stefano Aguzzoli (private communication) showing that a claim made in a recent paper of ours [2, Proposition 5.2], stating that the class of states of a free product algebra is closed, is in fact not true. That claim was used in turn in the proof of one of the main results of the same paper [2, Theorem 5.4]. However, we also provide in this note an alternative proof for that result, so that it keeps holding true., The authors acknowledge partial support by the SYSMICS project (EU H2020-MSCA-RISE-2015 Project 689176). Also, Flaminio acknowledges partial support by the Spanish Ramon y Cajal research program RYC-2016-19799; Flaminio and Godo acknowledge partial support by the FEDER/MINECO project TIN2015-71799-C2-1-P., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

On the relation between possibilistic logic and modal logics of belief and knowledge

  • Banerjee, Mohua
  • Dubois, Didier
  • Godo, Lluis
  • Prade, Henri
Possibilistic logic and modal logic are knowledge representation frameworks sharing some common features, such as the duality between possibility and necessity, and the decomposability of necessity for conjunctions, as well as some obvious differences since possibility theory is graded. At the semantic level, possibilistic logic relies on possibility distributions and modal logic on accessibility relations. In the last 30 years, there have been a series of attempts for bridging the two frameworks in one way or another. In this paper, we compare the relational semantics of epistemic logics (such as KD45 and S5) with simpler possibilistic semantics of a fragment of such logics that only uses modal formulas of depth 1. This minimal epistemic logic handles both all-or-nothing beliefs and explicitly ignored facts. We also contrast epistemic logic with the S5-based rough set logic. Finally, this paper presents extensions of generalized possibilistic logic with objective and non-nested multimodal formulas, in the style of modal logics KD45 and S5., Godo is supported by the MINECO/FEDER project RASO [TIN2015-71799-C2-1-P]., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

A new upper bound for the maximum weight clique problem

  • Li, Chu Min
  • Liu, Yanli
  • Jiang, Hua
  • Manyà, Felip
  • Li, Yu
The maximum weight clique problem (MWCP) for a vertex-weighted graph is to find a complete subgraph in which the sum of vertex weights is maximum. The main goal of this paper is to develop an efficient branch-and-bound algorithm to solve the MWCP. As a crucial aspect of branch-and-bound MWCP algorithms is the incorporation of a tight upper bound, we first define a new upper bound for the MWCP, called UBWC, that is based on a novel notion called weight cover. The idea of a weight cover is to compute a set of independent sets of the graph and define a weight function for each independent set so that the weight of each vertex of the graph is covered by such weight functions. We then propose a new branch-and-bound MWCP algorithm called WC-MWC that uses UBWC to reduce the number of branches of the search space that must be traversed by incrementally constructing a weight cover for the graph. Finally, we present experimental results that show that UBWC reduces the search space much more than previous upper bounds, and the new algorithm WC-MWC outperforms some of the best performing exact and heuristic MWCP algorithms on both small/medium graphs and real-world massive graphs., Work supported by the National Natural Science Foundation of China (grants 61272014, 61370183, 61472147 and 61370184), the platforms Matrics of University of Picardie Jules Verne and HPC of Jianghan Univeristy, the Spanish Ministry of Economy and Competitiveness–FEDER (grant TIN2015-71799-C2-1-P)., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

A branching heuristic for SAT solvers based on complete implication graphs

  • Xiao, Fan
  • Li, Chu Min
  • Luo, Mao
  • Manyà, Felip
  • Lü, Zhipeng
  • Li, Yu
The performance of modern conflict-driven clause learning (CDCL) SAT solvers strongly depends on branching heuristics. State-of-the-art branching heuristics, such as variable state independent decaying sum (VSIDS) and learning rate branching (LRB), are computed and maintained by aggregating the occurrences of the variables in conflicts. However, these heuristics are not sufficiently accurate at the beginning of the search because they are based on very few conflicts. We propose the distance branching heuristic, which, given a conflict, constructs a complete implication graph and increments the score of a variable considering the longest distance between the variable and the conflict rather than the simple presence of the variable in the graph. We implemented the proposed distance branching heuristic in Maple_LCM and Glucose-3.0, two of the best CDCL SAT solvers, and used the resulting solvers to solve instances from the application and crafted tracks of the 2014 and 2016 SAT competitions and the main track of the 2017 SAT competition. The empirical results demonstrate that using the proposed distance branching heuristic in the initialization phase of Maple_LCM and Glucose-3.0 solvers improves performance. The Maple_LCM solver with the proposed distance branching heuristic in the initialization phase won the main track of the 2017 SAT competition., This work was partially supported by National Natural Science Foundation of China (Grant Nos. 61370183, 61370184, 61472147), Matrics Platform of the Université de Picardie Jules Verne, and MINECO-FEDER Project RASO (Grant No. TIN2015-71799-C2-1-P), Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Maximality in finite-valued Lukasiewicz logics defined by order filters

  • Coniglio, Marcelo E.
  • Esteva, Francesc
  • Gispert, Joan
  • Godo, Lluis
In this paper we consider the logics L-n i obtained from the (n+1)-valued Łukasiewicz logics Ł- n+1 by taking the order filter generated by i/n as the set of designated elements. In particular, the conditions of maximality and strong maximality among them are analyzed. We present a very general theorem that provides sufficient conditions for maximality between logics. As a consequence of this theorem, it is shown that L-n i is maximal w.r.t. CPL whenever n is prime. Concerning strong maximality (i.e. maximality w.r.t. rules instead of only axioms), we provide algebraic arguments in order to show that the logics L-n i are not strongly maximal w.r.t. CPL, even for n prime. Indeed, in such case, we show that there is just one extension between L-n i and CPL obtained by adding to L-n i a kind of graded explosion rule. Finally, using these results, we show that the logics L-n i with n prime and i/n < 1/2 are ideal paraconsistent logics., The authors also acknowledge partial support by the H2020 MSCA-RISE-2015 project SYSMICS. M.E. Coniglio was also financially supported by an individual research grant from CNPq, Brazil (308524/2014-4). F. Esteva and L. Godo also acknowledge partial support by the Spanish MINECO/FEDER project RASO (TIN2015- 71799-C2-1-P). J. Gispert also acknowledges partial support by the Spanish MINECO/FEDER projects (MTM2016-74892 and MDM-2014-044) and grant 2017-SGR-95 of Generalitat de Catalunya, Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

New complexity results for Lukasiewicz logic

  • Bofill, Miquel
  • Manyà, Felip
  • Vidal, Amanda
  • Villaret, Mateu
One aspect that has been poorly studied in multiple-valued logics, and in particular in Łukasiewicz logic, is the generation of instances of varying difficulty for evaluating, comparing and improving satisfiability solvers. With the ultimate goal of finding challenging benchmarks for Łukasiewicz satisfiability solvers, we start by defining a natural and intuitive class of clausal forms (simple Ł-clausal forms) and studying their complexity. Since we prove that the satisfiability problem of simple Ł-clausal forms can be solved in linear time, we then define two new classes of clausal forms (Ł-clausal forms and restricted Ł-clausal forms) that truly exploit the non-lattice operations of Łukasiewicz logic and whose satisfiability problems are NP-complete when clauses have at least three literals, and admit linear-time algorithms when clauses have at most two literals. We also define an efficient satisfiability preserving translation of Łukasiewicz logic formulas into Ł-clausal forms. Finally, we describe a random generator of Ł-clausal forms and report on an empirical investigation in which we identify an easy-hard-easy pattern and a phase transition phenomenon for Ł-clausal forms., This work was supported by Project LOGISTAR from the EU H2020 Research and Innovation Programme under Grant Agreement No. 769142, MINECO-FEDER Projects RASO (TIN2015-71799-C2-1-P) and LoCos (TIN2015-66293-R), and the UdG Project MPCUdG2016/055. Vidal acknowledges the support from the Project GA17-04630S of the Czech Science Foundation (GAČR)., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Practical reasoning using values: an argumentative approach based on a hierarchy of values

  • Teze, Juan Carlos L.
  • Perello-Moragues, Antoni
  • Godo, Lluis
  • Noriega, Pablo
Values are at the heart of human decision-making. They are used to decide whether something or some state of affairs is good or not, and they are also used to address the moral dilemma of the right thing to do under given circumstances. Both uses are present in several everyday situations, from the design of a public policy to the negotiation of employee benefit packages. Both uses of values are specially relevant when one intends to design or validate that artificial intelligent systems behave in a morally correct way. In real life, the choice of policy components or the agreed upon benefit package are processes that involve argumentation. Likewise, the design and deployment of value-driven artificial entities may be well served by embedding practical reasoning capabilities in these entities or using argumentation for their design and certification processes. In this paper, we propose a formal framework to support the choice of actions of a value-driven agent and arrange them into plans that reflect the agent’s preferences. The framework is based on defeasible argumentation. It presumes that agent values are partially ordered in a hierarchy that is used to resolve conflicts between incommensurable values., Teze acknowledges partial support by CONICET, Universidad Nacional del Sur (UNS), and Universidad Nacional de Entre Ríos (UNER), Argentina. Perelló-Moragues is supported with an AGAUR industrial doctoral grant sponsored by FCC AQUALIA, IIIA-CSIC, and UAB. Godo, Perelló-Moragues and Noriega acknowledge the AppPhil project (funded by Caixa Bank, RecerCaixa 2017) and the Spanish FEDER/ MINECO project CIMBVAL (TIN2017-89758-R). Godo’s work is also supported by the Spanish FEDER/ MINECO project RASO (TIN2015-71799-C2-1-P)., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Syntactic characterizations of classes of first-order structures in mathematical fuzzy logic

  • Badia, Guillermo
  • Costa, Vicent
  • Dellunde, Pilar
  • Noguera, Carles
This paper is a contribution to graded model theory, in the context of mathematical fuzzy logic. We study characterizations of classes of graded structures in terms of the syntactic form of their first-order axiomatization. We focus on classes given by universal and universal–existential sentences. In particular, we prove two amalgamation results using the technique of diagrams in the setting of structures valued on a finite MTL-algebra, from which analogues of the Loś–Tarski and the Chang–Loś–Suszko preservation theorems follow., Open access funding provided by Austrian Science Fund (FWF). The authors are indebted to two anonymous referees and to the editor for their critical and interesting remarks that have helped improving the presentation the paper. Costa, Dellunde, and Noguera received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Curie Grant Agreement No. 689176 (SYSMICS project). Badia is supported by the Project I 1923-N25 (New perspectives on residuated posets) of the Austrian Science Fund (FWF). Costa is also supported by the Grant for the recruitment of early-stage research staff (FI-2017) from the Generalitat de Catalunya. Dellunde is also partially supported by the Project RASO TIN2015-71799-C2-1-P, CIMBVAL TIN2017-89758-R, and the Grant 2017SGR-172 from the Generalitat de Catalunya. The research leading to these results has received funding from AppPhil-RecerCaixa. Finally, Noguera is also supported by the Project GA17-04630S of the Czech Science Foundation (GAČR), Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

T-generable indistinguishability operators and their use for feature selection and classification

  • Armengol, Eva
  • Boixader, Dionis
  • García-Cerdaña, Àngel
  • Recasens, Jordi
T-generable indistinguishability operators are operators E that can be expressed in the form , where T is a t-norm and is the fuzzy relation generated by the fuzzy subset μ. In this paper we analyse their relation with powers with respect to the t-norm T and with quasi-arithmetic means. For non-strict continuous Archimedean t-norms they are completely characterised as generable by crisp equivalence relations. These fuzzy relations are used to define a method, called JADE, useful for feature selection and classification tasks. JADE is based on minimising the distance between two indistinguishability measures: the one given by weighting the attribute-values describing the domain objects and the other one given by the correct classification taken as an equivalence relation. The preliminary experiments we carried out with JADE are promising concerning the accuracy in solving classification tasks. We also report some issues of the method that could be improved in the future., This research is partially funded by the projects RASO (TIN2015-71799-C2-1-P) and RPREF (CSIC Intramural 201650E044) and the grants 2014-SGR-118 and 2014-SGR-788 from the Generalitat de Catalunya., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Three characterizations of strict coherence on infinite-valued events

  • Flaminio, Tommaso
This article builds on a recent paper coauthored by the present author, H. Hosni and F. Montagna. It is meant to contribute to the logical foundations of probability theory on many-valued events and, specifically, to a deeper understanding of the notion of strict coherence. In particular, we will make use of geometrical, measure-theoretical and logical methods to provide three characterizations of strict coherence on formulas of infinite-valued Lukasiewicz logic., The author acknowledges partial support by the Spanish Ramón y Cajal research program RYC-2016-19799; the Spanish FEDER/MINECO project TIN2015- 71799-C2-1-P and the SYSMICS project (EU H2020-MSCA-RISE-2015, Project 689176), Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Contribución de congreso (ConferenceOutput)

A two-stage MaxSAT reasoning approach for the maximum weight clique problem

  • Jiang, Hua
  • Min Li, Chu
  • Liu, Yanli
  • Manyà, Felip
Trabajo presentado en la The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18), celebrada en Hilton New Orleans Riverside, New Orleans (Estados Unidos), del 2 al 7 febrero de 2018, MaxSAT reasoning is an effective technology used in modern branch-and-bound (BnB) algorithms for the Maximum Weight Clique problem (MWC) to reduce the search space. However, the current MaxSAT reasoning approach for MWC is carried out in a blind manner and is not guided by any relevant strategy. In this paper, we describe a new BnB algorithm for MWC that incorporates a novel two-stage MaxSAT reasoning approach. In each stage, the MaxSAT reasoning is specialised and guided for different tasks. Experiments on an extensive set of graphs show that the new algorithm implementing this approach significantly outperforms relevant exact and heuristic MWC algorithms in both small/medium and massive real-world graphs., This work is supported by NSFC Grant No. 61272014, No.61472147, No. 61370183 and No. 61370184, the Metrics platform of University of Picardie Jules Verne, the HPC platform of JHUN, and the MINECO-FEDER project RASO TIN2015-71799-C2-1-P., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Contribución de congreso (ConferenceOutput)

Connecting systems of Mathematical fuzzy logic with fuzzy concept lattices

  • Codara, Pietro
  • Esteva, Francesc
  • Godo, Lluis
  • Valota, Diego
Trabajo presentado en el 17th International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU) celebrado en Cádiz (España) del 11 al 15 de junio de 2018, In this paper our aim is to explore a new look at formal systems of fuzzy logics using the framework of (fuzzy) formal concept analysis (FCA). Let L be an extension of MTL complete with respect to a given L-chain. We investigate two possible approaches. The first one is to consider fuzzy formal contexts arising from L where attributes are identified with L-formulas and objects with L-evaluations: every L-evaluation (object) satisfies a formula (attribute) to a given degree, and vice-versa. The corresponding fuzzy concept lattices are shown to be isomorphic to quotients of the Lindenbaum algebra of L. The second one, following an idea in a previous paper by two of the authors for the particular case of Gödel fuzzy logic, is to use a result by Ganter and Wille in order to interpret the (lattice reduct of the) Lindenbaum algebra of L-formulas as a (classical) concept lattice of a given context., The authors are thankful to the anonymous reviewers for their helpful comments. Pietro Codara is supported by the INdAM-Marie Curie Cofund project LaVague (FP7-PEOPLE-2012-COFUND 600198). Francesc Esteva and Lluis Godo acknowledge partial support by the FEDER/MINECO project TIN2015-71799- C2-1-P., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Contribución de congreso (ConferenceOutput)

Logics for strict-coherence and Carnap-regular probability functions

  • Flaminio, Tommaso
Trabajo presentado en el 17th International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU) celebrado en Cádiz (España) del 11 al 15 de junio de 2018, In this paper we provide a characterization of strict coherence in terms of the logical consistency of suitably defined formulas in fuzzy-modal logics for probabilistic reasoning. As a direct consequence of our characterization, we also show the decidability for the problem of checking the strict coherence of rational-valued books on classical events. Further, we introduce a fuzzy modal logic that captures Carnap-regular probability functions, that is normalized and finitely additive measures which maps to 0 only the impossible event., The author acknowledges partial support by the Spanish Ramon y Cajal research program RYC-2016-19799; the Spanish FEDER/MINECO project TIN2015-71799-C2-1-P and the SYSMICS project (EU H2020-MSCA-RISE-2015 Project 689176)., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Contribución de congreso (ConferenceOutput)

Term-graph anti-unification

  • Baumgartner, Alexander
  • Kutsia, Temur
  • Levy, Jordi
  • Villaret, Mateu
Trabajo presentado en el 3rd International Conference on Formal Structures for Computation and Deduction (FSCD), celebrado en Oxford (Inglaterra), del 9 al 12 de julio de 2018, We study anti-unification for possibly cyclic, unranked term-graphs and develop an algorithm, which computes a minimal complete set of generalizations for them. For bisimilar graphs the algorithm computes the join in the lattice generated by a functional bisimulation. These results generalize anti-unification for ranked and unranked terms to the corresponding term-graphs, and solve also anti-unification problems for rational terms and dags. Our results open a way to widen anti-unification based code clone detection techniques from a tree representation to a graph representation of the code., Supported by the Austrian Science Fund (FWF) under the projects P 28789-N32 and J 3909-N31, by MINECO/FEDER projects TIN2015-71799-C2-1-P (RASO) and TIN2015-66293-R (LoCos), and by UdG project MPCUdG2016/055., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Contribución de congreso (ConferenceOutput)

On implication-free reducts of MVn-algebras

  • Coniglio, Marcelo E.
  • Esteva, Francesc
  • Flaminio, Tommaso
  • Godo, Lluis
Trabajo presentado en Logic, Algebra and Truth Degrees (LATD 2018), celebrado en Bern (Suiza), del 27 al 31 de agosto de 2018, The authors acknowledge partial support by the H2020 MSCA-RISE-2015project SYSMICS. Coniglio also acknowledges support by the CNPq grant 308524/2014-4. Flaminio acknowledges support by the Ramon y Cajal research program RYC-2016-19799. Esteva, Flaminio and Godo also acknowledge the FEDER/MINECO project TIN2015-71799-C2-1-P, Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Contribución de congreso (ConferenceOutput)

An argumentative recommendation approach based on contextual aspects

  • Lionel Teze, Juan Carlos
  • Godo, Lluis
  • Simari, Guillermo
Trabajo presentado en el 12th International Scalable Uncertainty Management (SUM 2018), celebrado en Milán (Italia), del 3 al 5 de octubre de 2018, Argumentation-based recommender systems constitute an interesting tool to provide reasoned recommendations in complex domains with unresolved contradictory information situations and incomplete information. In these systems, the use of contextual information becomes a central issue in order to come up with personalized recommendations. An argumentative recommender system that offers mechanisms to handle contextual aspects of the recommendation domain provides an important ability that can be exploited by the user. However, in most of existing works, this issue has not been extensively studied. In this work, we propose an argumentation-based formalization for dealing with this issue. We present a general framework that allows the design of recommender systems capable of handling queries that can include (possibly inconsistent) contextual information under which recommendations should be computed. To answer a query, in the proposed argumentationbased approach, the system first selects alternative instances according to the user’s supplied contextual information, and then makes recommendations, in both cases through a defeasible argumentative analysis., This work has been partially supported by EU H2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No. 690974 for the project MIREL: MIning and REasoning with Legal texts, and by funds provided by CONICET, Universidad Nacional del Sur by PGI-UNS (grant 24/N040), and Universidad Nacional de Entre Rıos. Godo acknowledges the Spanish FEDER/MINECO project TIN2015-71799- C2-1-P., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Contribución de congreso (ConferenceOutput)

Inferring quantitative preferences: beyond logical deduction

  • Martínez, Vanina
  • Godo, Lluis
  • Simari, Gerardo I.
Trabajo presentado en el 12th International Scalable Uncertainty Management (SUM 2018), celebrado en Milán (Italia), del 3 al 5 de octubre de 2018, In this paper we consider a hybrid possibilistic-probabilistic alternative approach to Probabilistic Preference Logic Networks (PPLNs). Namely, we first adopt a possibilistic model to represent the beliefs about uncertain strict preference statements, and then, by means of a pignistic probability transformation, we switch to a probabilistic-based credulous inference of new preferences for which no explicit (or transitive) information is provided. Finally, we provide a tractable approximate method to compute these probabilities., Martinez and Simari have been partially supported by EU H2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No. 690974 for the project MIREL: MIning and REasoning with Legal texts; and funds provided by Universidad Nacional del Sur (UNS), Agencia Nacional de Promocion Cientifica y Tecnologica, and CONICET, Argentina. Godo acknowledges the EU H2020 project SYSMICS (MSCA-RISE-2015 Project 689176) and the Spanish FEDER/MINECO project TIN2015-71799-C2-1-P, Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Contribución de congreso (ConferenceOutput)

Clause Branching in MaxSAT and MinSAT

  • Argelich, Josep
  • Li, Chu Min
  • Manyà, Felip
  • Zhu, Zhu
Trabajo presentado en el 21st International Conference of the Catalan Association for Artificial Intelligence (CCIA 2018), celebrada en Roses (España) del 8 al 10 de Octubre de 2018, We describe a new exact procedure, inspired on recent works on tableaux, for simultaneously solving MaxSAT and MinSAT. The main novelty of our procedure is that it implements a clause branching rule that preserves both the minimum and the maximum number of clauses than can be unsatisfied. Moreover, we prove the correctness of the procedure, and provide a review of the different types of branchings which are available for MaxSAT and MinSAT. We also give some preliminary experimental results that show that the new branching rule, when implemented into an existing branch-and-bound MaxSAT solver, produces substantial gains on industrial instances of the MaxSAT Evaluation., This work was supported by Project LOGISTAR from the EU H2020 Research and Innovation Programme under Grant Agreement No. 769142, and MINECO-FEDER projects RASO (TIN2015-71799-C2-1-P/2-P)., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

A MaxSAT-Based approach to the team composition problem in a classroom

  • Manyà, Felip
  • Negrete, Santiago
  • Roig, Carme
  • Soler, Joan Ramon
Given a classroom containing a fixed number of students and a fixed number of tables that can be of different sizes, as well as a list of preferred classmates to sit with for each student, the team composition problem in a classroom (TCPC) is the problem of finding an assignment of students to tables in such a way that preferences are maximally-satisfied. In this paper, we formally define the TCPC, prove that it is NP-hard and define a MaxSAT model of the problem. Moreover, we report on the results of an empirical investigation that show that solving the TCPC with MaxSAT solvers is a promising approach., This work was supported by the Generalitat de Catalunya grant AGAUR 2014-SGR-118, and the MINECO-FEDER project RASO TIN2015-71799-C2-1-P. The second author is supported by grant PSPA-PNB-CGVyDI.324.2016 from Universidad Autónoma Metropolitana (Cuajimalpa), Mexico., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

Experiences using decision tees for knowledge discovery

  • Armengol, Eva
  • García-Cerdaña, Àngel
  • Dellunde, Pilar
Knowledge discovery is the process of identifying useful patterns from large data sets. There are two families of approaches to be used for knowledge discovery: clustering, when the classes of domain objects are not known; and inductive learning algorithms, when the classes are known and the goal is to construct a domain model useful to identify new unseen objects. Clustering algorithms have also been proposed to analyze the data when the classes are known. However, to our knowledge, inductive learning methods are not used to analyze the available data but only for prediction. What we propose here is a methodology, namely FTree, that uses a decision tree to analyze both the available data identifying patterns and some important aspects of the domain (at least from the domain’s part represented by the data at hand) such as similarity between classes, separability, characterization of classes and even some possible errors on data., This research is partially funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 689176 (SYSMICS project), the projects RASO (TIN2015-71799-C2-1-P) and RPREF (CSIC Intramural 201650E044) and the grants 2014-SGR-118 and 2014-SGR-788 from the Generalitat de Catalunya., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

A modal account of preference in a fuzzy setting

  • Esteva, Francesc
  • Godo, Lluis
  • Vidal, Amanda
In this paper we first consider the problem of extending fuzzy (weak and strict) preference relations, represented by fuzzy preorders on a set to a fuzzy preferences on subsets, and we characterise different possibilities. Based on their properties, we then semantically define and axiomatize several two-tiered graded modal logics to reason about the corresponding different notions of fuzzy preferences., Esteva and Godo acknowledges partial support by the Spanish FEDER/MINECO project TIN2015-71799-C2-1-P. Vidal acknowledges partial support by the joint project of the Austrian Science Fund (FWF) I1897-N25 and the Czech Science Foundation (GACR) 15-34650L, and by the institutional grant RVO:67985807., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Contribución de congreso (ConferenceOutput)

Phase Transition in Realistic Random SAT Models

  • Ansotegui, Carlos
  • Bonet, María Luisa
  • Levy, Jordi
Phase-transition in random SAT formulas is one of the properties best studied by theoretical SAT researchers. There exists a constant rk depending on k such that, if we choose randomly a k-SAT formula over n variables and m clauses, it will be satisfiable with high probability, if m/n < r, and unsatisfiable, otherwise. However, this criterion is useless in practice, because real-world or industrial instances have some properties not shown in random formulas. In the last years, several models of realistic random formulas have been proposed. Here we discuss about the phase transition in these models, and about the size of unsatisfiability proofs. We observe that in these models, like in real-world formulas, there is not a sharp phase transition, the transition occurs for smaller values of r, and the proofs on unsatisfiable formulas are smaller than in the classical random model. We also discuss about the strategies used by modern SAT solvers to exploit these properties., Research partially supported by the EU H2020 Research and Innovation Program under the LOGISTAR project (Grant Agreement No. 769142) and the MINECO-FEDER projects RASO (TIN2015-71799-C2-1-P) and TASSAT 3 (TIN2016-76573-C2-2-P).
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Community Structure in Industrial SAT Instances

  • Ansótegui Gil, Carlos José
  • Bonet, Maria Luisa
  • Giráldez-Cru, Jesús
  • Levy, Jordi
Modern SAT solvers have experienced a remarkable progress on solving industrial instances. It is believed that most of these successful techniques exploit the underlying structure of industrial instances. Recently, there have been some attempts to analyze the structure of industrial SAT instances in terms of complex networks, with the aim of explaining the success of SAT solving techniques, and possibly improving them. In this paper, we study the community structure, or modularity, of industrial SAT instances. In a graph with clear community structure, or high modularity, we can find a partition of its nodes into communities such that most edges connect variables of the same community. Representing SAT instances as graphs, we show that most application benchmarks are characterized by a high modularity. On the contrary, random SAT instances are closer to the classical Erdös-Rényi random graph model, where no structure can be observed. We also analyze how this structure evolves by the effects of the execution of a CDCL SAT solver, and observe that new clauses learned by the solver during the search contribute to destroy the original structure of the formula. Motivated by this observation, we finally present an application that exploits the community structure to detect relevant learned clauses, and we show that detecting these clauses results in an improvement on the performance of the SAT solver. Empirically, we observe that this improves the performance of several SAT solvers on industrial SAT formulas, especially on satisfiable instances., This work is partially supported by the EU H2020 Research and Innovation Programme under the LOGISTAR project (Grant Agreement No. 769142), MINECO-FEDER projects RASO (TIN2015-71799-C2-1-P) and TASSAT3 (TIN2016-76573-C2-2-P), the Spanish Ministerio de Econom´ıa y Competitividad under the EXASOCO project (ref. PGC2018-101216- B-I00), including European Regional Development Funds (ERDF). The third author is also supported by a MICINN Juan de la Cierva fellowship (ref. FJCI-2017-32420).
Dipòsit Digital de Documents de la UAB
Publicación Artículo científico (JournalArticle)

Syntactic characterizations of classes of first-order structures in mathematical fuzzy logic

  • Badia, Guillermo
  • Costa, Vicent|||0000-0001-6352-7238
  • Dellunde i Clavé, Pilar|||0000-0002-8198-5475
  • Noguera, Carles
This paper is a contribution to graded model theory, in the context of mathematical fuzzy logic. We study characterizations of classes of graded structures in terms of the syntactic form of their first-order axiomatization. We focus on classes given by universal and universal-existential sentences. In particular, we prove two amalgamation results using the technique of diagrams in the setting of structures valued on a finite MTL-algebra, from which analogues of the Łoś-Tarski and the Chang-Łoś-Suszko preservation theorems follow.