Pasar al contenido principal

LOGICA PARA PROBLEMAS COMBINATORIOS

TIN2015-66293-R

•
Nombre agencia financiadora Ministerio de Economía y Competitividad
Acrónimo agencia financiadora MINECO
Programa Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Convocatoria Proyectos I+D+i Retos de Investigación
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 Dirección General de Investigación Científica y Técnica
Centro beneficiario UNIVERSITAT DE GIRONA
Identificador persistente http://dx.doi.org/10.13039/501100003329

Resultados relacionados

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

DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Higher-Order Pattern Anti-Unification in Linear Time

  • Baumgartner, Alexander
  • Kutsia, Temur
  • Levy, Jordi
  • Villaret, Mateu
We present a rule-based Huet’s style anti-unification algorithm for simply typed lambda-terms, which computes a least general higher-order pattern generalization. For a pair of arbitrary terms of the same type, such a generalization always exists and is unique modulo α-equivalence and variable renaming. With a minor modification, the algorithm works for untyped lambda-terms as well. The time complexity of both algorithms is linear., This research has been partially supported by the Austrian Science Fund (FWF) project SToUT (P 24087-N18), the Upper Austrian Government strategic program “Innovatives OÖ 2010plus”, the MINECO projects RASO (TIN2015-71799-C2-1-P) and HeLo (TIN2012-33042), the MINECO/FEDER UE project LoCoS (TIN2015-66293-R) and the UdG project MPCUdG2016/055., 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 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
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Higher-Order Pattern Anti-Unification in Linear Time

  • Baumgartner, Alexander
  • Kutsia, Temur
  • Levy, Jordi
  • Villaret i Ausellé, Mateu
We present a rule-based Huet’s style anti-unification algorithm for simply typed lambda-terms, which computes a least general higher-order pattern generalization. For a pair of arbitrary terms of the same type, such a generalization always exists and is unique modulo α-equivalence and variable renaming. With a minor modification, the algorithm works for untyped lambda-terms as well. The time complexity of both algorithms is linear, This research has been partially supported by the Austrian Science Fund (FWF) project SToUT (P 24087-N18), the Upper Austrian Government strategic program “Innovatives OÖ 2010plus”, the MINECO projects RASO (TIN2015-71799-C2-1-P) and HeLo (TIN2012-33042), the MINECO/FEDER UE project LoCoS (TIN2015-66293-R) and the UdG project MPCUdG2016/055
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Resource Analysis driven by (Conditional) Termination Proofs

  • Albert, Elvira
  • Bofill Arasa, Miquel
  • Borralleras, Cristina
  • Martín-Martín, Enrique
  • Rubio, Albert
When programs feature a complex control flow, existing techniques for resource analysis produce cost relation systems (CRS) whose cost functions retain the complex flow of the program and, consequently, might not be solvable into closed-form upper bounds. This paper presents a novel approach to resource analysis that is driven by the result of a termination analysis. The fundamental idea is that the termination proof encapsulates the flows of the program which are relevant for the cost computation so that, by driving the generation of the CRS using the termination proof, we produce a linearly-bounded CRS (LB-CRS). A LB-CRS is composed of cost functions that are guaranteed to be locally bounded by linear ranking functions and thus greatly simplify the process of CRS solving. We have built a new resource analysis tool, named MaxCore, that is guided by the VeryMax termination analyzer and uses CoFloCo and PUBS as CRS solvers. Our experimental results on the set of benchmarks from the Complexity and Termination Competition 2019 for C Integer programs show that MaxCore outperforms all other resource analysis tools, This work was funded partially by the Spanish MICINN/FEDER, UE projects RTI2018-094403-BC31, RTI2018-094403-B-C33 and RTI2018-095609-B-I00, the MINECO project TIN2015-69175-C4-2-R, the MINECO/FEDER, UE projects TIN2015-69175-C4-3-R and TIN2015-66293-R, and by the CM project S2018/TCS-4314