Pasar al contenido principal

Resultados relacionados

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

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

Symbolic Analysis of Maude Theories with Narval

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Escobar Román, Santiago|||0000-0002-3550-4781
  • Sapiña-Sanchis, Julia|||0000-0003-2994-6986
  • Ballis, Demis
[EN] Concurrent functional languages that are endowed with symbolic reasoning capabilities such as Maude offer a high-level, elegant, and efficient approach to programming and analyzing complex, highly nondeterministic software systems. Maude's symbolic capabilities are based on equational unification and narrowing in rewrite theories, and provide Maude with advanced logic programming capabilities such as unification modulo user-definable equational theories and symbolic reachability analysis in rewrite theories. Intricate computing problems may be effectively and naturally solved in Maude thanks to the synergy of these recently developed symbolic capabilities and classical Maude features, such as: (i) rich type structures with sorts (types), subsorts, and overloading; (ii) equational rewriting modulo various combinations of axioms such as associativity, commutativity, and identity; and (iii) classical reachability analysis in rewrite theories. However, the combination of all of these features may hinder the understanding of Maude symbolic computations for non-experienced developers. The purpose of this article is to describe how programming and analysis of Maude rewrite theories can be made easier by providing a sophisticated graphical tool called Narval that supports the fine-grained inspection of Maude symbolic computations., This work has been partially supported by the EU (FEDER) and the Spanish MCIU under grant RTI2018-094403-B-C32, by the Spanish Generalitat Valenciana under grants PROMETEO/2019/098 and APOSTD/2019/127, and by the US Air Force Office of Scientific Research under award number FA9550-17-1-0286.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Static correction of Maude programs with assertions

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Sapiña-Sanchis, Julia|||0000-0003-2994-6986
  • Ballis, D.
[Otros] In this paper, we present a novel transformation method for Maude programs featuring both automatic program diagnosis and correction. The input of our method is a reference specification of the program behavior that is given in the form of assertions together with an overly general program whose execution might violate the assertions. Our correction technique translates into a refined program in which every computation is also a computation in that satisfies the assertions of . The technique is first formalized for topmost rewrite theories, and then we generalize it to larger classes of rewrite theories that support nested structured configurations. Our technique copes with infinite space states and does not require the knowledge of any failing run. We report experiments that assess the effectiveness of assertion-driven correction., This work has been partially supported by the EU (FEDER) and the Spanish Ministerio de Economia y Competitividad under grant TIN2015-69175-C4-1-R, and by Generalitat Valenciana PROMETEOII/2015/013 and PROMETEO/2019/098
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Proving and disproving confluence of context-sensitive rewriting

  • Lucas Alba, Salvador|||0000-0001-9923-2108
  • Gutiérrez Gil, Raúl|||0000-0002-3984-2868
  • Vítores-Vicente, Miguel
[EN] Context-sensitive rewriting is a restriction of term rewriting where reductions are allowed on specific arguments of function symbols only, and then in particular positions of terms. Confluence is an abstract property of reduction relations guaranteeing that two diverging reduction sequences can always be joined into a common reduct. In this paper we investigate confluence of context-sensitive rewriting and present some novel results. In particular, a characterization of local confluence of context-sensitive rewriting as the joinability of an extended class of critical pairs which we introduce here. We also show that the treatment of joinability of critical pairs using theorem proving and solving feasibility problems is useful to automatically prove and disprove confluence of context-sensitive rewriting. Our techniques have been implemented in a new tool, CONFident. We show by means of benchmarks the impact of the new techniques discussed in the paper., Partially supported by grant RTI2018-094403-B-C32 funded by MCIN/AEI/10.13039/501100011033 and by "ERDF A way of making Europe", and PROMETEO/2019/098
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Contribución de congreso (ConferenceOutput)

When AI Difficulty is Easy: The Explanatory Power of Predicting IRT Difficulty

  • Martínez-Plumed, Fernando|||0000-0003-2902-6477
  • C. Monserrat|||0000-0003-1790-8085
  • Hernández-Orallo, José|||0000-0001-9746-7632
  • Castellano, David
[EN] One of challenges of artificial intelligence as a whole is robustness. Many issues such as adversarial examples, out of distribution performance, Clever Hans phenomena, and the wider areas of AI evaluation and explainable AI, have to do with the following question: Did the system fail because it is a hard instance or because something else? In this paper we address this question with a generic method for estimating IRT-based instance difficulty for a wide range of AI domains covering several areas, from supervised feature-based clas- sification to automated reasoning. We show how to estimate difficulty systematically using off-the-shelf machine learning regression models. We illustrate the usefulness of this estima- tion for a range of applications., This work has been partially supported by the EU (FEDER) and Spanish MINECO grant RTI2018-094403-B-C32 funded by MCIN/AEI/10.13039/501100011033 and by ERDF A way of making Europe , Generalitat Valenciana under grant PROMETEO/2019/098, EU s Horizon 2020 research and innovation programme under grant agreement No. 952215 (TAILOR), the Future of Life Institute, FLI, under grant RFP2-152, US DARPA HR00112120007 (RECoG-AI), the AI-Watch and HUMAINT projects by DG CONNECT and DG JRC of the European Commission, and INNEST/2021/317 (Project cofunded by the European Union with the Programa Operativo del Fondo Europeo de Desarrollo Regional (FEDER) de la Comunitat Valenciana 2014-2020).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

The origins of the halting problem

  • Lucas Alba, Salvador|||0000-0001-9923-2108
[EN] The halting problem is a prominent example of undecidable problem and its formulation and undecidability proof is usually attributed to Turing's 1936 landmark paper. Copeland noticed in 2004, though, that it was so named and, apparently, first stated in a 1958 book by Martin Davis. We provide additional arguments partially supporting this claim as follows: (i) with a focus on computable (real) numbers with infinitely many digits (e.g., pi), in his paper Turing was not concerned with halting machines; (ii) the two decision problems considered by Turing concern the ability of his machines to produce specific kinds of outputs, rather than reaching a halting state, something which was missing from Turing's notion of computation; and (iii) from 1936 to 1958, when considering the literature of the field no paper refers to any "halting problem" of Turing Machines until Davis' book. However, there were important preliminary contributions by (iv) Church, for whom termination was part of his notion of computation (for the lambda-calculus), and (v) Kleene, who essentially formulated, in his 1952 book, what we know as the halting problem now., Partially supported by the EU (FEDER), and projects RTI2018-094403-B-C32, PROMETEO/2019/098.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

The teaching size: computable teachers and learners for universal languages

  • Telle, Jan Arne
  • Hernández-Orallo, José|||0000-0001-9746-7632
  • Ferri Ramírez, César|||0000-0002-8975-1120
[EN] The theoretical hardness of machine teaching has usually been analyzed for a range of concept languages under several variants of the teaching dimension: the minimum number of examples that a teacher needs to figure out so that the learner identifies the concept. However, for languages where concepts have structure (and hence size), such as Turing-complete languages, a low teaching dimension can be achieved at the cost of using very large examples, which are hard to process by the learner. In this paper we introduce the teaching size, a more intuitive way of assessing the theoretical feasibility of teaching concepts for structured languages. In the most general case of universal languages, we show that focusing on the total size of a witness set rather than its cardinality, we can teach all total functions that are computable within some fixed time bound. We complement the theoretical results with a range of experimental results on a simple Turing-complete language, showing how teaching dimension and teaching size differ in practice. Quite remarkably, we found that witness sets are usually smaller than the programs they identify, which is an illuminating justification of why machine teaching from examples makes sense at all., We would like to thank the anonymous referees for their helpful comments. This work was supported by the EU (FEDER) and the Spanish MINECO under grant RTI2018-094403-B-C32, and the Generalitat Valenciana PROMETEO/2019/098. This work was done while the first author visited Universitat Politecnica de Valencia and also while the third author visited University of Bergen (covered by Generalitat Valenciana BEST/2018/027 and University of Bergen). J. Hernandez-Orallo is also funded by an FLI grant RFP2-152.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

AUTOMAT[R]IX: learning simple matrix pipelines

  • Contreras-Ochando, Lidia
  • Ferri Ramírez, César|||0000-0002-8975-1120
  • Hernández-Orallo, José|||0000-0001-9746-7632
[EN] Matrices are a very common way of representing and working with data in data science and artificial intelligence. Writing a small snippet of code to make a simple matrix transformation is frequently frustrating, especially for those people without an extensive programming expertise. We present AUTOMAT[R]IX, a system that is able to induce R program snippets from a single (and possibly partial) matrix transformation example provided by the user. Our learning algorithm is able to induce the correct matrix pipeline snippet by composing primitives from a library. Because of the intractable search space-exponential on the size of the library and the number of primitives to be combined in the snippet, we speed up the process with (1) a typed system that excludes all combinations of primitives with inconsistent mapping between input and output matrix dimensions, and (2) a probabilistic model to estimate the probability of each sequence of primitives from their frequency of use and a text hint provided by the user. We validate AUTOMAT[R]IX with a set of real programming queries involving matrices from Stack Overflow, showing that we can learn the transformations efficiently, from just one partial example, We thank the anonymous reviewers for their comments, which have improved the paper significantly. This research was supported by the EU (FEDER) and the Spanish MINECO RTI2018-094403B-C32 and the Generalitat Valenciana PROMETEO/2019/098. L. Contreras-Ochando was also supported by the Spanish MECD Grant (FPU15/03219). J. Hernandez-Orallo is also funded by FLI (RFP2-152).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Applications and extensions of context-sensitive rewriting

  • Lucas Alba, Salvador|||0000-0001-9923-2108
[EN] Context-sensitive rewriting is a restriction of term rewriting which is obtained by imposing replacement restrictions on the arguments of function symbols. It has proven useful to analyze computational properties of programs written in sophisticated rewriting-based programming languages such asCafeOBJ, Haskell, Maude, OBJ*, etc. Also, a number of extensions(e.g., to conditional rewritingor constrained equational systems) and generalizations(e.g., controlled rewritingor forbidden patterns) of context-sensitive rewriting have been proposed. In this paper, we provide an overview of these applications and related issues. (C) 2021 Elsevier Inc. All rights reserved., Partially supported by the EU (FEDER), and projects RTI2018-094403-B-C32 and PROMETEO/2019/098.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Imposing Assertions in Maude via Program Transformation

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Sapiña-Sanchis, Julia|||0000-0003-2994-6986
  • Ballis, Demis
[EN] Program transformation is widely used for producing correct mutations of a given program so as to satisfy the user's intent that can be expressed by means of some sort of specification (e.g. logical assertions, functional specifications, reference implementations, summaries, examples). This paper describes an automated correction methodology for Maude programs that is based on program transformation and can be used to enforce a safety policy, given by a set A of system assertions, in a Maude program R that might disprove some of the assertions. The outcome of the technique is a safe program refinement R' of R in which every computation is a good run, i.e., it satisfies the assertions in A. Furthermore, the transformation ensures that no good run of R is removed from R'. Advantages of this correction methodology can be summarized as follows. A fully automatic program transformation featuring both program diagnosis and repair that preserves all executability requirements. A simple logical notation to declaratively express invariant properties and other safety constraints through assertions. No dynamic information is required to infer program fixes: the methodology is static and does not need to collect any error symptom at runtime., This work has been partially supported by the EU (FEDER) and the Spanish MINECO under grant RTI2018-094403-B-C32, and by Generalitat Valenciana under grant PROMETEO/2019/098.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Contribución de congreso (ConferenceOutput)

An Optimizing Protocol Transformation for Constructor Finite Variant Theories in Maude-NPA

  • Aparicio-Sánchez, Damián
  • Escobar Román, Santiago|||0000-0002-3550-4781
  • Gutiérrez Gil, Raúl|||0000-0002-3984-2868
  • Sapiña-Sanchis, Julia|||0000-0003-2994-6986
[EN] Maude-NPA is an analysis tool for cryptographic security protocols that takes into account the algebraic properties of the cryptosystem. Maude-NPA can reason about a wide range of cryptographic properties. However, some algebraic properties, and protocols using them, have been beyond Maude-NPA capabilities, either because the cryptographic properties cannot be expressed using its equational unification features or because the state space is unmanageable. In this paper, we provide a protocol transformation that can safely get rid of cryptographic properties under some conditions. The time and space difference between verifying the protocol with all the crypto properties and verifying the protocol with a minimal set of the crypto properties is remarkable. We also provide, for the first time, an encoding of the theory of bilinear pairing into Maude-NPA that goes beyond the encoding of bilinear pairing available in the Tamarin tool, Partially supported by the EU (FEDER) and the Spanish MCIU under grant RTI2018-094403-B-C32, by the Spanish Generalitat Valenciana under grant PROMETEO/2019/098, and by the US Air Force Office of Scientific Research under award number FA9550-17-1-0286. Julia Sapiña has been supported by the Generalitat Valenciana APOSTD/2019/127 grant