Pasar al contenido principal

SISTEMAS DE INFERENCIA PARA INFORMACION INCONSISTENTE: FUNDAMENTOS LOGICOS

PID2019-111544GB-C21

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Convocatoria Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Año convocatoria 2019
Plan Estatal 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario AGENCIA ESTATAL CONSEJO SUPERIOR DE INVESTIGACIONES CIENTIFICAS (CSIC)

Resultados relacionados

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

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

Incomplete MaxSAT approaches for combinatorial testing

  • Ansótegui Gil, Carlos José
  • Manyà Serres, Felip
  • Ojeda Contreras, Jesús
  • Salvia Hornos, Josep M.
  • Torres, Eduard
We present a Satisfiability (SAT)-based approach for building Mixed Covering Arrays with Constraints of minimum length, referred to as the Covering Array Number problem. This problem is central in Combinatorial Testing for the detection of system failures. In particular, we show how to apply Maximum Satisfiability (MaxSAT) technology by describing efficient encodings for different classes of complete and incomplete MaxSAT solvers to compute optimal and suboptimal solutions, respectively. Similarly, we show how to solve through MaxSAT technology a closely related problem, the Tuple Number problem, which we extend to incorporate constraints. For this problem, we additionally provide a new MaxSAT-based incomplete algorithm. The extensive experimental evaluation we carry out on the available Mixed Covering Arrays with Constraints benchmarks and the comparison with state-of-the-art tools confirm the good performance of our approaches., We would like to thank specially Akihisa Yamada for the access to several benchmarks for our experiments and for solving some questions about his previous work on Combinatorial Testing with Constraints. This work was partially supported by Grant PID2019-109137GB-C21 funded by MCIN/AEI/10.13039/501100011033, PANDEMIES 2020 by Agencia de Gestio d’Ajuts Universitaris i de Recerca (AGAUR), Departament d’Empresa i Coneixement de la Generalitat de Catalunya; FONDO SUPERA COVID-19 funded by Crue-CSIC-SANTANDER, ISINC (PID2019-111544GB-C21), and the MICNN FPU fellowship (FPU18/02929).
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

A logico-geometric comparison of coherence for non-additive uncertainty measures

  • Corsi, Esther Anna
  • Flaminio, Tommaso
  • Hosni, Hykel
Figures (3).- Tables (2), We investigate the notion of coherence for (non-)additive uncertainty measures from a logico-geometric point of view. Our main result is to the effect that distinct criteria for coherence are not always matched by axiomatically distinct measures of uncertainty. In addition we introduce a metalogic within which this kind of result can be captured formally., Corsi and Hosni acknowledge funding by the Department of Philosophy “Piero Martinetti” of the University of Milan under the Project “Departments of Excellence 2023-2027” awarded by the Italian Ministry of Education, University and Research (MIUR). Flaminio acknowledges partial support by the MOSAIC project (EU H2020- MSCA-RISE- 2020 Project 101007627) and also by the Spanish project PID2019-111544GB-C21 funded by MCIN/AEI/10.13039/501100011033. Hosni also acknowledges funding from the Deutsche Forschungsgemeinschaft (DFG, grant LA 4093/3-1)., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

Algebras and relational frames for gödel modal logic and some of its extensions

  • Flaminio, Tommaso
  • Godo, Lluis
  • Menchón, Paula
  • Rodriguez, Ricardo O.
Gödel modal logics can be seen as extensions of intutionistic modal logics with the prelinearity axiom. In this paper we focus on the algebraic and relational semantics for Gödel modal logics that leverages on the duality between finite Gödel algebras and finite forests, i.e. finite posets whose principal downsets are totally ordered. We consider different subvarieties of the basic variety GAO of Gödel algebras with two modal operators (GAOs for short) and their corresponding classes of forest frames, either with one or two accessibility relations. These relational structures can be considered as prelinear versions of the usual relational semantics of intuitionistic modal logic. More precisely we consider two main extensions of finite Gödel algebras with operators: the one obtained by adding Dunn axioms, typically studied in the fragment of positive classical (and intuitionistic) logic, and the one determined by adding Fischer Servi axioms. We present Jónsson-Tarski like representation theorems for the different types of finite GAOs considered in the paper., Theauthors acknowledge partial support by the MOSAIC project (EU H2020-MSCA-RISE-2020 Project 101007627). Flaminio and Godo also acknowledge partial support by the Spanish project PID2019-111544GB-C21, Flaminio also acknowledges the Spanisn project PID2022- 141529NB-C22, and Godo the Spanish project PID2022-139835NB-C21, all of them funded by MCIN/AEI/10.13039/501100011033. Menchón acknowledges partial support by the Argentinean projects PIP 112-20200101301CO (CONICET) and PICT-2019-2019-00882 (ANPCyT). Finally, Rodriguez acknowledges partial support by the following Argentinean projects: PIP 112-20150100412CO (CONICET) and UBA-CyT-20020190100021BA., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

Conditional Objects as Possibilistic Variables

  • Flaminio, Tommaso
  • Godo, Lluis
Symbolic and Quantitative Approaches to Reasoning with Uncertainty.- 17th European Conference, ECSQARU 2023, Arras, France, September 19–22, 2023, Proceedings.- Conference proceedings.- Published 19 November 2023, The interpretation of basic conditionals as three-valued objects initiated by de Finetti has been mainly developed and extended by Gilio and Sanfilippo and colleagues, who look at (compound) conditionals as probabilistic random quantities. Recently, it has been shown that this approach ends up providing a Boolean algebraic structure for the set of conditional objects. In this paper, we show how that this probabilistic-based approach can also be developed within the possibilistic framework, where conditionals are attached with possibilistic variables instead: variables attached with a (conditional) possibility distribution on its domain of plain events. The possibilistic expectation of these variables now provides a means of extending the original possibility distribution on events to (compound) conditional objects. Our main result shows that this possibilistic approach leads to exactly the same underlying Boolean algebraic structure for the set of conditionals., The authors also acknowledge support by the support by the MOSAIC project (EU H2020-MSCA-RISE-2020 Project 101007627) and by the Spanish projects PID2019-111544GB-C21 and PID2022-139835NB-C21 funded by MCIN/AEI/10.13039/501100011033., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Integrating multi-armed bandit with local search for MaxSAT

  • Zheng, Jiongzhi
  • He, Kun
  • Zhou, Jianrong
  • Jin, Yan
  • Li, Chu Min
  • Manyà, Felip
Partial MaxSAT (PMS) and Weighted PMS (WPMS) are two practical generalizations of the MaxSAT problem. In this paper, we introduce a new local search algorithm for these problems, named BandHS. It applies two multi-armed bandit (MAB) models to guide the search directions when escaping local optima. One MAB model is combined with all the soft clauses to help the algorithm select to satisfy appropriate soft clauses, while the other MAB model is combined with all the literals in hard clauses to help the algorithm select suitable literals to satisfy the hard clauses. These two models enhance the algorithm's search ability in both feasible and infeasible solution spaces. BandHS also incorporates a novel initialization method that prioritizes both unit and binary clauses when generating the initial solutions. Moreover, we apply our MAB approach to the state-of-the-art local search algorithm NuWLS and to the local search component of the incomplete solver NuWLS-c-2023. The extensive experiments conducted demonstrate the excellent performance and generalization capability of the proposed method. Additionally, we provide analyses on the type of problems where our MAB method works well or not, aiming to offer insights and suggestions for its application. Encouragingly, our MAB method has been successfully applied in core local search components in the winner of the WPMS complete track of MaxSAT Evaluation 2023, as well as the runners-up of the incomplete track of MaxSAT Evaluations 2022 and 2023., This work is supported by National Natural Science Foundation of China (U22B2017), Microsoft Research Asia (100338928), and grants PID2019-111544GB-C21, PID2022-139835NB-C21 and TED2021-129319B-I00 funded by MCIN/AEI/10.13039/501100011033., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

A first polynomial non-clausal class in many-valued logic

  • Escalada-Imaz, Gonzalo
The relevance of polynomial classes of formulas to deductive efficiency motivated their further research, and currently, a great number of such classes is known. Nevertheless, they have been exclusively sought in the setting of propositional logic and clausal form, which is of course expressively limiting for real-world applications. Along these lines and towards making tractability applicable beyond propositional clausal logic, firstly, we define the egular many-valued orn Non-Clausal (NC) class, or , obtained by suitably amalgamating both regular classes: Horn and NC. Then we show that recognizing whether any NC formula is Horn-NC takes only linear time. Secondly, we demonstrate that the relationship between and: (1) its subclass of regular Horn formulas is that syntactically subsumes the Horn class but semantically both classes are equivalent; and (2) its superclass of regular non-clausal formulas is that contains all non-clausal formulas whose clausal form is Horn. Thirdly, we define Regular Non-Clausal Unit-Resolution, or , and prove that is complete for and also checks its satisfiability in polynomial time. Altogether, is a class recognized and solved polynomially, which shows that our intended goal is reached since is many-valued, non-clausal and tractable. Fourthly, based on , we characterize extensive classes of Horn-NC-like formulas, super-classes of , which are composed of formulas that are logically equivalent to some formula in . We furnish syntactical patterns of such Horn-NC-like formulas, being outside and whose satisfiability test is also decidable in polynomial time. As and are, both, basic in the DPLL scheme, the most efficient in propositional logic, and can be extended to some other non-classical logics, we argue that they pave the way for efficient non-clausal DPLL-based approximate reasoning., Field: Tractable Approximate Automated Reasoning., The author is greatly indebted to the anonymous reviewer for his/her comprehensive review and his/her many scholarly insights and suggestions, which altogether have helped to substantially improve the paper. This work was supported by the Spanish project ISINC (PID2019-111544GB-C21) funded by MCIN/AEI/10.13039/501100011033., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

An elementary belief function logic

  • Dubois, Didier
  • Godo, Lluis
  • Prade, Henri
Non-additive uncertainty theories, typically possibility theory, belief functions and imprecise probabilities share a common feature with modal logic: the duality properties between possibility and necessity measures, belief and plausibility functions as well as between upper and lower probabilities extend the duality between possibility and necessity modalities to the graded environment. It has been shown that the all-or-nothing version of possibility theory can be exactly captured by a minimal epistemic logic (MEL) that uses a very small fragment of the KD modal logic, without resorting to relational semantics. Independently, a belief function logic has been obtained by extending the modal logic S5 to probabilistic graded modalities using Łukasiewicz logic, albeit using relational semantics. This paper shows that a simpler belief function logic can be devised by adding Łukasiewicz logic on top of MEL. It allows for a more natural semantics in terms of Shafer basic probability assignments., Godo acknowledges partial support by Europea Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 101007627 and by the Agencia Estatal de Investigación AEI/10.13039/501100011033 under the grant PID2019-111544GB-C21., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

The possibilistic horn non-clausal knowledge bases

  • Escalada-Imaz, Gonzalo
Non-clausal deduction in classical logic is one of the oldest areas in artificial intelligence. It first appeared in the sixties and consequently a large body of research has been devoted to it. Within the last decades, computing with non-clausal formulas has been considered in several fields, and in particular, in answer set programming, wherein non-clausal or nested logic programs were conceived in 1999. Possibilistic logic is the most extended approach to handle uncertain and partially inconsistent information. Here, we generalize some well-known clausal outcomes in possibilistic reasoning to the non-clausal setting, concretely the objective of our proposal is: (i) to extend available insights from clausal to non-clausal form; (ii) to show that possibilistic reasoning admits feasible classes also at the non-clausal level; (iii) to combine the high expressiveness of non-clausal possibilistic logic with the highest efficient (polynomial) reasoning mechanisms; and (iii) to suggest that some meaningful subclasses of possibilistic nested programs can be efficiently processed. Firstly, we define the class of Possibilistic Horn Non-Clausal formulas, or , which covers the classes: possibilistic Horn and propositional Horn-NC. is shown to be non-clausal, analogous to the standard Horn class. Secondly, we define Possibilistic Non-Clausal Unit-Resolution, or , and prove that correctly computes the inconsistency degree of Horn-NC bases. is formulated in a clausal-like manner, which eases its understanding, formal proofs and future extension towards full non-clausal resolution. Thirdly, we prove that computing the inconsistency degree of Horn-NC bases takes polynomial time. Although there already exist tractable classes in possibilistic logic, all of them are clausal, and thus, turns out to be the first characterized polynomial non-clausal class within possibilistic reasoning. We discuss that our approach serves as a starting point to developing uncertain non-clausal reasoning on the basis of both methodologies: DPLL and resolution., The author would like to express his gratitude to the anonymous reviewers for their help to significantly improve on previous versions of the paper. This work was supported by the Spanish project ISINC (PID2019-111544GB-C21) funded by MCIN/AEI/10.13039/501100011033., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Counterfactuals as modal conditionals, and their probability

  • Rosella, Giuliano
  • Flaminio, Tommaso
  • Bonzio, Stefano
In this paper we propose a semantic analysis of Lewis' counterfactuals. By exploiting the structural properties of the recently introduced boolean algebras of conditionals, we show that counterfactuals can be expressed as formal combinations of a conditional object and a normal necessity modal operator. Specifically, we introduce a class of algebras that serve as modal expansions of boolean algebras of conditionals, together with their dual relational structures. Moreover, we show that Lewis' semantics based on sphere models can be reconstructed in this framework. As a consequence, we establish the soundness and completeness of a slightly stronger variant of Lewis' logic for counterfactuals with respect to our algebraic models. In the second part of the paper, we present a novel approach to the probability of counterfactuals showing that it aligns with the uncertainty degree assigned by a belief function, as per Dempster-Shafer theory, to its associated conditional formula. Furthermore, we characterize the probability of a counterfactual in terms of Gärdenfors' imaging rule for the probabilistic update., The authors thank the anonymous referees and journal editors for their comments, suggestions, and constructive criticism. The authors are also indebted to Lluis Godo and Jan Sprenger for their help. Flaminio acknowledges partial support by the Spanish project PID2019-111544GB-C21 funded by MCIN/AEI/10.13039/501100011033 and Bonzio by the INdAM, GNSAGA - Gruppo Nazionale per le Strutture Algebriche, Geometriche e le loro Applicazioni. Flaminio and Bonzio acknowledge partial support by the MOSAIC project EU H2020-MSCA-RISE-2020 Project 101007627., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

MaxSAT resolution for regular propositional logic

  • Coll, Jordi
  • Li, Chu Min
  • Manyà, Felip
  • Yangin, Elifnaz
[Data availability] No data was used for the research described in the article., Proof systems for SAT are unsound for MaxSAT because they preserve satisfiability but fail to preserve the minimum number of unsatisfied clauses. Consequently, there has been a need to define cost-preserving resolution-style proof systems for MaxSAT. In this paper, we present the first MaxSAT resolution proof system specifically defined for regular propositional clausal forms and prove its soundness and completeness. The defined proof system provides an exact approach to solving Regular MaxSAT and Weighted Regular MaxSAT with variable elimination algorithms., This work has been supported by the French Agence Nationale de la Recherche, reference ANR-19-CHIA-0013-01, and grants PID2019-111544GB-C21 and TED2021-129319B-I00 funded by MCIN/AEI/10.13039/501100011033., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

On conditional probabilities and their canonical extensions to Boolean algebras of compound conditionals

  • Flaminio, Tommaso
  • Gilio, Angelo
  • Godo, Lluis
  • Sanfilippo, Giuseppe
[Data availability] No data was used for the research described in the article., In this paper we investigate canonical extensions of conditional probabilities to Boolean algebras of conditionals. Before entering into the probabilistic setting, we first prove that the lattice order relation of every Boolean algebra of conditionals can be characterized in terms of the well-known order relation given by Goodman and Nguyen. Then, as an interesting methodological tool, we show that canonical extensions behave well with respect to conditional subalgebras. As a consequence, we prove that a canonical extension and its original conditional probability agree on basic conditionals. Moreover, we verify that the probability of conjunctions and disjunctions of conditionals in a recently introduced framework of Boolean algebras of conditionals are in full agreement with the corresponding operations of conditionals as defined in the approach developed by two of the authors to conditionals as three-valued objects, with betting-based semantics, and specified as suitable random quantities. Finally we discuss relations of our approach with nonmonotonic reasoning based on an entailment relation among conditionals., The authors are grateful to the anonymous reviewers for their helpful comments and suggestions. Flaminio and Godo acknowledge partial support by the MOSAIC project (EU H2020-MSCA-RISE-2020 Project 101007627) and also by the Spanish project PID2019-111544GB-C21/AEI/10.13039/501100011033. Sanfilippo acknowledges support by the FFR 2023 project of University of Palermo, Italy., Peer reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Incomplete MaxSAT approaches for combinatorial testing

  • Ansótegui Gil, Carlos José
  • Manyà Serres, Felip
  • Ojeda Contreras, Jesús
  • Salvia Hornos, Josep M.
  • Torres, Eduard
We present a Satisfiability (SAT)-based approach for building Mixed Covering Arrays with Constraints of minimum length, referred to as the Covering Array Number problem. This problem is central in Combinatorial Testing for the detection of system failures. In particular, we show how to apply Maximum Satisfiability (MaxSAT) technology by describing efficient encodings for different classes of complete and incomplete MaxSAT solvers to compute optimal and suboptimal solutions, respectively. Similarly, we show how to solve through MaxSAT technology a closely related problem, the Tuple Number problem, which we extend to incorporate constraints. For this problem, we additionally provide a new MaxSAT-based incomplete algorithm. The extensive experimental evaluation we carry out on the available Mixed Covering Arrays with Constraints benchmarks and the comparison with state-of-the-art tools confirm the good performance of our approaches., We would like to thank specially Akihisa Yamada for the access to several benchmarks for our experiments and for solving some questions about his previous work on Combinatorial Testing with Constraints. This work was partially supported by Grant PID2019-109137GB-C21 funded by MCIN/AEI/10.13039/501100011033, PANDEMIES 2020 by Agencia de Gestio d’Ajuts Universitaris i de Recerca (AGAUR), Departament d’Empresa i Coneixement de la Generalitat de Catalunya; FONDO SUPERA COVID-19 funded by Crue-CSIC-SANTANDER, ISINC (PID2019-111544GB-C21), and the MICNN FPU fellowship (FPU18/02929).