Pasar al contenido principal

Resultados relacionados

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

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Proving Termination in the Context-Sensitive Dependency Pair Framework

  • Gutiérrez Gil, Raúl|||0000-0002-3984-2868
  • Lucas Alba, Salvador|||0000-0001-9923-2108
Partially supported by the EU (FEDER) and the Spanish MEC/MICINN, under grant TIN 2007-68093-C02-02.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Capítulo o parte de un libro (BookPart)

Protocol analysis modulo combination of theories: A case study in Maude-NPA

  • Sasse, Ralf
  • Meadows, Catherine
  • Meseguer, José
  • Escobar Román, Santiago|||0000-0002-3550-4781
There is a growing interest in formal methods and tools to analyze cryptographic protocols modulo algebraic properties of their underlying cryptographic functions. It is well-known that an intruder who uses algebraic equivalences of such functions can mount attacks that would be impossible if the cryptographic functions did not satisfy such equivalences. In practice, however, protocols use a collection of well-known functions, whose algebraic properties can naturally be grouped together as a union of theories E 1... ¿ n. Reasoning symbolically modulo the algebraic properties E 1... ¿ n requires performing (E 1... ¿ n)-unification. However, even if a unification algorithm for each individual E i is available, this requires combining the existing algorithms by methods that are highly non-deterministic and have high computational cost. In this work we present an alternative method to obtain unification algorithms for combined theories based on variant narrowing. Although variant narrowing is less efficient at the level of a single theory E i, it does not use any costly combination method. Furthermore, it does not require that each E i has a dedicated unification algorithm in a tool implementation. We illustrate the use of this method in the Maude-NPA tool by means of a well-known protocol requiring the combination of three distinct equational theories. © 2011 Springer-Verlag., R. Sasse and J. Meseguer have been partially supported by NSF Grants CNS0716638, CNS-0831064 and CNS-0904749. S. Escobar has been partially supported by the EU (FEDER) and the Spanish MEC/MICINN under grant TIN 2007-68093- C02-02. C. Meadows has been partially supported by NSF Grant CNS-0904749
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Using negotiable features for prescription problems

  • Bella Sanjuán, Antonio
  • Ferri Ramírez, César|||0000-0002-8975-1120
  • Hernández-Orallo, José|||0000-0001-9746-7632
  • Ramírez Quintana, María José|||0000-0002-0559-3568
Data mining is usually concerned on the construction of accurate models from data, which are usually applied to well-defined problems that can be clearly isolated and formulated independently from other problems. Although much computational effort is devoted for their training and statistical evaluation, model deployment can also represent a scientific problem, when several data mining models have to be used together, constraints appear on their application, or they have to be included in decision processes based on different rules, equations and constraints. In this paper we address the problem of combining several data mining models for objects and individuals in a common scenario, where not only we can affect decisions as the result of a change in one or more data mining models, but we have to solve several optimisation problems, such as choosing one or more inputs to get the best overall result, or readjusting probabilities after a failure. We illustrate the point in the area of customer relationship management (CRM), where we deal with the general problem of prescription between products and customers. We introduce the concept of negotiable feature, which leads to an extended taxonomy of CRM problems of greater complexity, since each new negotiable feature implies a new degree of freedom. In this context, we introduce several new problems and techniques, such as data mining model inversion (by ranging on the inputs or by changing classification problems into regression problems by function inversion), expected profit estimation and curves, global optimisation through a Monte Carlo method, and several negotiation strategies in order to solve this maximisation problem., This work has been partially supported by the EU (FEDER) and the Spanish MEC/MICINN, under grant TIN 2007-68093-C02, the Spanish project "Agreement Technologies" (Consolider Ingenio CSD2007-00022) and the GVA project PROMETEO/2008/051.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Capítulo o parte de un libro (BookPart)

Datalog-Based program analysis with BES and RWL

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Villanueva, Alicia|||0000-0003-1090-5009
  • Feliú Gabaldón, Marco Antonio
  • Joubert, Christophe
This paper describes two techniques for Datalog query evaluation and their application to object-oriented program analysis. The first technique transforms Datalog programs into an implicit Boolean Equation System (Bes) that can then be solved by using linear-time complexity algorithms that are available in existing, general purpose verification toolboxes such as Cadp. In order to improve scalability and to enable analyses involving advanced meta-programming features, we develop a second methodology that transforms Datalog programs into rewriting logic (Rwl) theories. This method takes advantage of the preeminent features and facilities that are available within the high-performance system Maude, which provides a very efficient implementation of Rwl. We provide evidence of the practicality of both approaches by reporting on some experiments with a number of real-world Datalog-based analyses. © 2011 Springer-Verlag., This work has been partially supported by the eu(feder), the Spanish mec/micinn under grants tin2007-68093-C02 and tin2010-21062-C02-02, and the Generalitat Valenciana under grant Emergentes gv/2009/024. M.A.Feliu was partially supported by the Spanish mec fpu grant AP2008-00608.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Proving Termination Properties with Muterm

  • Alarcón, Beatriz
  • Navarro-Marset, Rafael
  • Gutiérrez Gil, Raúl|||0000-0002-3984-2868
  • Lucas Alba, Salvador|||0000-0001-9923-2108
[EN] MU-TERM is a tool which can be used to verify a number of termination properties of (variants of) Term Rewriting Systems (TRSs): termination of rewriting, termination of innermost rewriting, termination of order-sorted rewriting, termination of context-sensitive rewriting, termination of innermost context-sensitive rewriting and termination of rewriting modulo specific axioms. Such termination properties are essential to prove termination of programs in sophisticated rewriting-based programming languages. Specific methods have been developed and implemented in MU-TERM in order to efficiently deal with most of them. In this paper, we report on these new features of the tool., Partially supported by EU (FEDER) and MICINN grant TIN 2007-68093-C02-02.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

SAT modulo linear arithmetic for Solving Polynomial Constraints

  • Borralleras, Cristina
  • Oliveras, Albert
  • Rodriguez-Carbonell, Enric
  • Rubio, Albert
  • Lucas Alba, Salvador|||0000-0001-9923-2108
Polynomial constraint solving plays a prominent role in several areas of hardware and software analysis and verification, e.g.; termination proving, program invariant generation and hybrid system verification, to name a few. In this paper we propose a new method for solving non-linear constraints based on encoding the problem into an SMT problem considering only linear arithmetic. Unlike other existing methods, our method focuses on proving satisfiability of the constraints rather than on proving unsatisfiability, which is more relevant in several applications as we illustrate with several examples. Nevertheless, we also present new techniques based on the analysis of unsatisfiable cores that allow one to efficiently prove unsatisfiability too for a broad class of problems. The power of our approach is demonstrated by means of extensive experiments comparing our prototype with state-of-the-art tools on benchmarks taken both from the academic and the industrial world. © 2010 Springer Science+Business Media B.V., This work has been partially supported by the EU (FEDER) and the Spanish MEC/MICINN, under grants TIN 2007-68093-C02-01 and TIN 2007-68093-C02-02.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Context-Sensitive Dependency Pairs

  • Alarcón, Beatriz
  • Gutiérrez Gil, Raúl|||0000-0002-3984-2868
  • Lucas Alba, Salvador|||0000-0001-9923-2108
[EN] Termination is one of the most interesting problems when dealing with context-sensitive rewrite systems. Although a good number of techniques for proving termination of context-sensitive rewriting (CSR) have been proposed so far, the adaptation to CSR of the dependency pair approach, one of the most powerful techniques for proving termination of rewriting, took some time and was possible only after introducing some new notions like collapsing dependency pairs, which are specific for CSR. In this paper, we develop the notion of context-sensitive dependency pair (CSDP) and show how to use CSDPs in proofs of termination of CSR. The implementation and practical use of the developed techniques yield a novel and powerful framework which improves the current state-of-the-art of methods for automatically proving termination of CSR. (c) 2010 Elsevier Inc. All rights reserved., This work has been partially supported by the EU (FEDER) and the Spanish MEC/MICINN, under Grants TIN 2007-68093-C02 and HA 2006-0007. Beatriz Alarcon was partially supported by the Spanish MEC/MICINN under FPU Grant AP2005-3399. Raul Gutierrez was partially supported by the Spanish MEC/MICINN Grant TIN 2004-7943-C04-02.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Improving Context-Sensitive Dependency Pairs

  • Alarcón, Beatriz
  • Emmes, Fabian
  • Fuhs, Carsten
  • Giesl, Jürgen
  • Schneider-Kamp, Peter
  • Thiemann, René
  • Gutiérrez Gil, Raúl|||0000-0002-3984-2868
  • Lucas Alba, Salvador|||0000-0001-9923-2108
[EN] Context-sensitive dependence pairs (CS-DPs) are currently the most powerful method for automated termination analysis of context-sensitive rewriting. However, compared to DPs for ordinary rewriting, CS-DPs suffer from two main drawbacks: (a) CS-DPs can be collapsing. This complicates the handling of CS-DPs and makes them less powerful in practice. (b) There does not exist a "DP framework" for CS-DPs which would allow one to apply them in a flexible and modular way. This paper solves drawback (a) by introducing a new definition of CS-DPs. With our definition, CS-DPs are always non-collapsing and thus, they can be handled like ordinary DPs. This allows us to solve drawback (b) as well, i.e., we extend the existing DP framework for ordinary DPs to context sensitive rewriting. We implemented our results in the tool AProVE and successfully evaluated them on a large collection of examples., Authors from Valencia were partially supported by the EU (FEDER) and the Spanish MEC/MICINN, under grants TIN 2007-68093-C02-02 and HA 2006-0007. B. Alarcón was partially supported by the Spanish MEC/MICINN under FPU grant AP2005-3399. R. Gutiérrez was partially supported by the Spanish MEC/MICINN, under grant TIN 2004-7943-C04-02. Authors from Aachen were supported by the DAAD under grant D/06/12785 and by the DFG under grant GI 274/5-2.