Pasar al contenido principal

Resultados relacionados

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

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Capítulo o parte de un libro (BookPart)

Stochastic tasks: difficulty and Levin search

  • Hernández-Orallo, José|||0000-0001-9746-7632
We establish a setting for asynchronous stochastic tasks that account for episodes, rewards and responses, and, most especially, the computational complexity of the algorithm behind an agent solving a task. This is used to determine the difficulty of a task as the (logarithm of the) number of computational steps required to acquire an acceptable policy for the task, which includes the exploration of policies and their verification. We also analyse instance difficulty, task compositions and decompositions., This work has been partially supported by the EU (FEDER) and the Spanish MINECO under grants TIN 2010-21062-C02-02, PCIN-2013-037 and TIN 2013-45732-C4-1-P, and by Generalitat Valenciana PROMETEOII 2015/013.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Capítulo o parte de un libro (BookPart)

ACUOS: A System for Modular ACU Generalization with Subtyping and Inheritance

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Escobar Román, Santiago|||0000-0002-3550-4781
  • Espert Real, Javier
  • Meseguer, José
Computing generalizers is relevant in a wide spectrum of automated reasoning areas where analogical reasoning and inductive inference are needed. The ACUOS system computes a complete and minimal set of semantic generalizers (also called “anti-unifiers”) of two structures in a typed language modulo a set of equational axioms. By supporting types and any (modular) combination of associativity (A), commutativity (C), and unity (U) algebraic axioms for function symbols, ACUOS allows reasoning about typed data structures, e.g. lists, trees, and (multi-)sets, and typical hierarchical/structural relations such as is a and part of. This paper discusses the modular ACU generalization tool ACUOS and illustrates its use in a classical artificial intelligence problem., This work has been partially supported by the EU (FEDER) and the Spanish MINECO under grants TIN 2010-21062-C02-02 and TIN 2013-45732-C4-1-P, by Generalitat Valenciana PROMETEO2011/052, and by NSF Grant CNS 13-10109. J. Espert has also been supported by the Spanish FPU grant FPU12/06223.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Capítulo o parte de un libro (BookPart)

Models for logics and conditional constraints in automated proofs of termination

  • Lucas Alba, Salvador|||0000-0001-9923-2108
  • Meseguer, José
Reasoning about termination of declarative programs, which are described by means of a computational logic, requires the definition of appropriate abstractions as semantic models of the logic, and also handling the conditional constraints which are often obtained. The formal treatment of such constraints in automated proofs, often using numeric interpretations and (arithmetic) constraint solving can greatly benefit from appropriate techniques to deal with the conditional (in)equations at stake. Existing results from linear algebra or real algebraic geometry are useful to deal with them but have received only scant attention to date. We investigate the definition and use of numeric models for logics and the resolution of linear and algebraic conditional constraints as unifying techniques for proving termination of declarative programs., Developed during a sabbatical year at UIUC. Supported by projects NSF CNS13-19109, MINECO TIN2010-21062-C02-02 and TIN2013-45732-C4-1-P, and GV BEST/2014/026 and PROMETEO/2011/052.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Capítulo o parte de un libro (BookPart)

Asymmetric Unification: A New Unification Paradigm for Cryptographic Protocol Analysis

  • Erbatur, Serdar
  • Kapur, Deepak
  • Liu, Zhiqiang
  • Lynch, Christopher A.
  • Meadows, Catherine
  • Meseguer, José
  • Narendran, Paliath
  • Santiago Pinazo, Sonia
  • Sasse, Ralf
  • Escobar Román, Santiago|||0000-0002-3550-4781
We present a new paradigm for unification arising out of a technique commonly used in cryptographic protocol analysis tools that employ unification modulo equational theories. This paradigm relies on: (i) a decomposition of an equational theory into (R,E) where R is confluent, terminating, and coherent modulo E, and (ii) on reducing unification problems to a set of problems s=?ts=?t under the constraint that t remains R/E-irreducible. We call this method asymmetric unification. We first present a general-purpose generic asymmetric unification algorithm. and then outline an approach for converting special-purpose conventional unification algorithms to asymmetric ones, demonstrating it for exclusive-or with uninterpreted function symbols. We demonstrate how asymmetric unification can improve performanceby running the algorithm on a set of benchmark problems. We also give results on the complexity and decidability of asymmetric unification., S. Escobar and S. Santiago were partially supported by EU (FEDER) and the Spanish MEC/MICINN under grant TIN 2010-21062-C02-02, and by Generalitat Valenciana PROMETEO2011/052. The following authors were partially supported by NSF: S. Escobar, J. Meseguer, and R. Sasse under CNS 09-04749 and CCF 09- 05584; D. Kapur under CNS 09-05222; C. Lynch, Z. Liu, and C. Meadows under CNS 09-05378, and P. Narendran and S. Erbatur under CNS 09-05286. Part of the S. Erbatur’s work was supported while with the Department of Computer Science, University at Albany, and part of R. Sasse’s work was supported while with the Department of Computer Science, University of Illinois at Urbana-Champaign.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Capítulo o parte de un libro (BookPart)

C-tests revisited: back and forth with complexity

  • Hernández-Orallo, José|||0000-0001-9746-7632
We explore the aggregation of tasks by weighting them using a difficulty function that depends on the complexity of the (acceptable) policy for the task (instead of a universal distribution over tasks or an adaptive test). The resulting aggregations and decompositions are (now retrospectively) seen as the natural (and trivial) interactive generalisation of the C-tests., This work has been partially supported by the EU (FEDER) and the Spanish MINECO under grants TIN 2010-21062-C02-02, PCIN-2013-037 and TIN 2013-45732-C4-1-P, and by Generalitat Valenciana PROMETEOII 2015/013.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Capítulo o parte de un libro (BookPart)

Analysis of the IBM CCA Security API Protocols in Maude-NPA

  • González Burgueño, Antonio
  • Santiago Pinazo, Sonia
  • Meadows, Catherine
  • Meseguer, Jose
  • Escobar Román, Santiago|||0000-0002-3550-4781
Standards for cryptographic protocols have long been attractive candidates for formal verification. It is important that such standards be correct, and cryptographic protocols are tricky to design and subject to non-intuitive attacks even when the underlying cryptosystems are secure. Thus a number of general-purpose cryptographic protocol analysis tools have been developed and applied to protocol standards. However, there is one class of standards, security application programming interfaces (security APIs), to which few of these tools have been applied. Instead, most work has concentrated on developing special-purpose tools and algorithms for specific classes of security APIs. However, there can be much advantage gained from having general-purpose tools that could be applied to a wide class of problems, including security APIs. One particular class of APIs that has proven difficult to analyze using general-purpose tools is that involving exclusive-or. In this paper we analyze the IBM 4758 Common Cryptographic Architecture (CCA) protocol using an advanced automated protocol verification tool with full exclusive-or capabilities, the Maude-NPA tool. This is the first time that API protocols have been satisfactorily specified and analyzed in the Maude-NPA, and the first time XOR-based APIs have been specified and analyzed using a general-purpose unbounded session cryptographic protocol verification tool that provides direct support for AC theories. We describe our results and indicate what further research needs to be done to make such protocol analysis generally effective., Antonio González-Burgueño, Sonia Santiago and Santiago Escobar have been partially supported by the EU (FEDER) and the Spanish MINECO under grants TIN 2010-21062-C02-02 and TIN 2013-45732-C4-1-P, and by Generalitat Valenciana PROMETEO2011/052. José Meseguer has been partially supported by NSF Grant CNS 13-10109.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Capítulo o parte de un libro (BookPart)

Automatic inference of specifications using matching logic

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Villanueva, Alicia|||0000-0003-1090-5009
  • Feliú Gabaldón, Marco Antonio
Formal specifications can be used for various software engineering activities ranging from finding errors to documenting software and automatic test-case generation. Automatically discovering specifications for heap-manipulating programs is a challenging task. In this paper, we propose a technique for automatically inferring formal specifications from C code which is based on the symbolic execution and automated reasoning tandem "MATCHING LOGIC /K framework". We implemented our technique for a fragment of C, called KERNELC, in the automated tool KINDSPEC, which generates axioms that describe the precise input/output behavior of C routines that handle pointer-based structures, i.e., result values and state change. These specifications can be written either in MATCHING LOGIC itself, which is useful for further automated analysis within the K formal environment, or in sugared axiomatic form, which favors better human inspection. Since we rely on rewriting logic K semantics specification of programming languages, our approach can be easily extended to any language for which a formal semantics in K is given., This work has been partially supported by the EU (FEDER) and the Spanish MEC/MICINN, ref. TIN 2010-21062-C02-0, and by Generalitat Valenciana, ref. PROMETEO 2011/052.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Capítulo o parte de un libro (BookPart)

Compression and intelligence: social environments and communication

  • Dowe, David L.
  • Das, Paramjit K,
  • Hernández-Orallo, José|||0000-0001-9746-7632
Compression has been advocated as one of the principles which pervades inductive inference and prediction - and, from there, it has also been recurrent in definitions and tests of intelligence. However, this connection is less explicit in new approaches to intelligence. In this paper, we advocate that the notion of compression can appear again in definitions and tests of intelligence through the concepts of `mind-reading¿ and `communication¿ in the context of multi-agent systems and social environments. Our main position is that two-part Minimum Message Length (MML) compression is not only more natural and effective for agents with limited resources, but it is also much more appropriate for agents in (co-operative) social environments than one-part compression schemes - particularly those using a posterior-weighted mixture of all available models following Solomonoff¿s theory of prediction. We think that the realisation of these differences is important to avoid a naive view of `intelligence as compression¿ in favour of a better understanding of how, why and where (one-part or two-part, lossless or lossy) compression is needed., We thank the anonymous reviewers for their helpful comments, and we thank Kurt Kleiner for some challenging and ultimately very helpful questions in the broad area of this work. We also acknowledge the funding from the Spanish MEC and MICINN for projects TIN2009-06078-E/TIN, Consolider-Ingenio CSD2007-00022 and TIN2010-21062-C02, and Generalitat Valenciana for Prometeo/2008/051.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Capítulo o parte de un libro (BookPart)

Effective symbolic protocol analysis via equational irreducibility conditions

  • Erbatur, Serdar
  • Kapur, Deepak
  • Liu, Zhiqiang
  • Lynch, Christopher
  • Meadows, Catherine
  • Meseguer, José
  • Narendran, Paliath
  • Santiago Pinazo, Sonia
  • Sasse, Ralf
  • Escobar Román, Santiago|||0000-0002-3550-4781
We address a problem that arises in cryptographic protocol analysis when the equational properties of the cryptosystem are taken into account: in many situations it is necessary to guarantee that certain terms generated during a state exploration are in normal form with respect to the equational theory. We give a tool-independent methodology for state exploration, based on unification and narrowing, that generates states that obey these irreducibility constraints, called contextual symbolic reachability analysis, prove its soundness and completeness, and describe its implementation in the Maude-NPA protocol analysis tool. Contextual symbolic reachability analysis also introduces a new type of unification mechanism, which we call asymmetric unification, in which any solution must leave the right side of the solution irreducible. We also present experiments showing the effectiveness of our methodology., S. Escobar and S. Santiago have been partially supported by the EU (FEDER) and the Spanish MEC/MICINN under grant TIN 2010-21062-C02-02, and by Generalitat Valenciana PROMETEO2011/052. The following authors have been partially supported by NSF: S. Escobar, J. Meseguer and R. Sasse under grants CCF 09- 05584, CNS 09-04749, and CNS 09-05584; D. Kapur under grant CNS 09-05222; C. Lynch, Z. Liu, and C. Meadows under grant CNS 09-05378, and P. Narendran and S. Erbatur under grant CNS 09-05286.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Capítulo o parte de un libro (BookPart)

On more realistic environment distributions for defining, evaluating and developing intelligence

  • Hernández-Orallo, José|||0000-0001-9746-7632
  • Dowe, David L.
  • España Cubillo, Sergio
  • Hernández-Lloreda, M. Victoria
  • Insa Cabrera, Javier
One insightful view of the notion of intelligence is the ability to perform well in a diverse set of tasks, problems or environments. One of the key issues is therefore the choice of this set, which can be formalised as a `distribution¿. Formalising and properly defining this distribution is an important challenge to understand what intelligence is and to achieve artificial general intelligence (AGI). In this paper, we agree with previous criticisms that a universal distribution using a reference universal Turing machine (UTM) over tasks, environments, etc., is perhaps amuch too general distribution, since, e.g., the probability of other agents appearing on the scene or having some social interaction is almost 0 for many reference UTMs. Instead, we propose the notion of Darwin-Wallace distribution for environments, which is inspired by biological evolution, artificial life and evolutionary computation. However, although enlightening about where and how intelligence should excel, this distribution has so many options and is uncomputable in so many ways that we certainly need a more practical alternative. We propose the use of intelligence tests over multi-agent systems, in such a way that agents with a certified level of intelligence at a certain degree are used to construct the tests for the next degree. This constructive methodology can then be used as a more realistic intelligence test and also as a testbed for developing and evaluating AGI systems., We thank the anonymous reviewers for their helpful comments. We also thank the funding from the Spanish MEC and MICINN for projects TIN2009-06078-E/TIN, Consolider-Ingenio CSD2007-00022 and TIN2010-21062- C02, for MEC FPU grant AP2006-02323, and Generalitat Valenciana for Prometeo/2008/051
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Capítulo o parte de un libro (BookPart)

Learning with con gurable operators and RL-based heuristics

  • Martínez-Plumed, Fernando|||0000-0003-2902-6477
  • 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
In this paper, we push forward the idea of machine learning systems for which the operators can be modi ed and netuned for each problem. This allows us to propose a learning paradigm where users can write (or adapt) their operators, according to the problem, data representation and the way the information should be navigated. To achieve this goal, data instances, background knowledge, rules, programs and operators are all written in the same functional language, Erlang. Since changing operators a ect how the search space needs to be explored, heuristics are learnt as a result of a decision process based on reinforcement learning where each action is de ned as a choice of operator and rule. As a result, the architecture can be seen as a `system for writing machine learning systems' or to explore new operators., This work was supported by the MEC projects CONSOLIDER-INGENIO 26706 and TIN 2010-21062-C02-02, GVA project PROMETEO/2008/051, and the REFRAME project granted by the European Coordinated Research on Long-term Challenges in Information and Communication Sciences & Technologies ERA-Net (CHIST-ERA), and funded by the Ministerio de Econom´ıa y Competitividad in Spain. Also, F. Mart´ınez-Plumed is supported by FPI-ME grant BES-2011-045099
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Capítulo o parte de un libro (BookPart)

Inspecting rewriting logic computations (in a parametric and stepwise way)

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Sapiña-Sanchis, Julia|||0000-0003-2994-6986
  • Ballis, Demis
  • Frechina, F.
Trace inspection is concerned with techniques that allow the trace content to be searched for specific components. This paper presents a rich and highly dynamic, parameterized technique for the trace inspection of Rewriting Logic theories that allows the non-deterministic execution of a given unconditional rewrite theory to be followed up in different ways. Using this technique, an analyst can browse, slice, filter, or search the traces as they come to life during the program execution. Starting from a selected state in the computation tree, the navigation of the trace is driven by a user-defined, inspection criterion that specifies the required exploration mode. By selecting different inspection criteria, one can automatically derive a family of practical algorithms such as program steppers and more sophisticated dynamic trace slicers that facilitate the dynamic detection of control and data dependencies across the computation tree. Our methodology, which is implemented in the Anima graphical tool, allows users to capture the impact of a given criterion thereby facilitating the detection of improper program behaviors., This work has been partially supported by the EU (FEDER), the Spanish MEC project ref. TIN2010-21062-C02-02, the Spanish MICINN complementary action ref. TIN2009-07495-E, and by Generalitat Valenciana ref. PROMETEO2011/052. This work was carried out during the tenure of D. Ballis’ ERCIM “Alain Bensoussan ”Postdoctoral Fellowship. The research leading to these results has received funding from the European Union Seventh Framework Programme (FP7/2007-2013) under grant agreement n. 246016. F. Frechina was supported by FPU-ME grant AP2010-5681.
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 Capítulo o parte de un libro (BookPart)

Strong and weak operational termination of order-sorted rewrite theories

  • Lucas Alba, Salvador|||0000-0001-9923-2108
  • Meseguer, José
This paper presents several new results on conditional term rewriting within the general framework of order-sorted rewrite theories (OSRTs) which contains the more restricted framework of conditional term rewriting systems (CTRSs) as a special case. The results uncover some subtle issues about conditional termination. We first of all generalize a previous known result characterizing the operational termination of a CTRS by the quasi-decreasing ordering notion to a similar result for OSRTs. Second, we point out that the notions of *irreducible* term and of *normal form*, which coincide for unsorted rewriting are *totally different* for conditional rewriting and formally characterize that difference. We then define the notion of a *weakly operationally terminating* (or *weakly normalizing*) OSRT, give several evaluation mechanisms to compute normal forms in such theories, and investigate general conditions under which the rewriting-based operational semantics and the initial algebra semantics of a confluent OSRT coincide thanks to a notion of *canonical term algebra*. Finally, we investigate appropriate conditions and proof methods to ensure good executability properties of an OSRT for computing normal forms., Research partially supported by NSF grant CNS 13-19109. Salvador Lucas’ research was developed during a sabbatical year at the CS Dept. of the UIUC and was also partially supported by Spanish MECD grant PRX12/00214, MINECO project TIN2010-21062-C02-02, and GV grant BEST/2014/026 and project PROMETEO/2011/052.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Capítulo o parte de un libro (BookPart)

Comparing humans and AI agents

  • Insa Cabrera, Javier
  • Dowe, David L.
  • España Cubillo, Sergio
  • Henánez-Lloreda, M. Victoria
  • Hernández-Orallo, José|||0000-0001-9746-7632
Comparing humans and machines is one important source of information about both machine and human strengths and limitations. Most of these comparisons and competitions are performed in rather specific tasks such as calculus, speech recognition, translation, games, etc. The information conveyed by these experiments is limited, since it portrays that machines are much better than humans at some domains and worse at others. In fact, CAPTCHAs exploit this fact. However, there have only been a few proposals of general intelligence tests in the last two decades, and, to our knowledge, just a couple of implementations and evaluations. In this paper, we implement one of the most recent test proposals, devise an interface for humans and use it to compare the intelligence of humans and Q-learning, a popular reinforcement learning algorithm. The results are highly informative in many ways, raising many questions on the use of a (universal) distribution of environments, on the role of measuring knowledge acquisition, and other issues, such as speed, duration of the test, scalability, etc., We thank the anonymous reviewers for their helpful comments. We also thank José Antonio Martín H. for helping us with several issues about the RL competition, RL-Glue and reinforcement learning in general. We are also grateful to all the subjects who took the test. We also thank the funding from the Spanish MEC and MICINN for projects TIN2009-06078- E/TIN, Consolider-Ingenio CSD2007-00022 and TIN2010-21062-C02, for MEC FPU grant AP2006-02323, and Generalitat Valenciana for Prometeo/2008/051
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Capítulo o parte de un libro (BookPart)

Multidimensional Prediction Models When the Resolution Context Changes

  • Martínez Usó, Adolfo
  • Hernández-Orallo, José|||0000-0001-9746-7632
Multidimensional data is systematically analysed at multiple granularities by applying aggregate and disaggregate operators (e.g., by the use of OLAP tools). For instance, in a supermarket we may want to predict sales of tomatoes for next week, but we may also be interested in predicting sales for all vegetables (higher up in the product hierarchy) for next Friday (lower down in the time dimension). While the domain and data are the same, the operating context is different. We explore several approaches for multidimensional data when predictions have to be made at different levels (or contexts) of aggregation. One method relies on the same resolution, another approach aggregates predictions bottom-up, a third approach disaggregates predictions top-down and a final technique corrects predictions using the relation between levels. We show how these strategies behave when the resolution context changes, using several machine learning techniques in four application domains., This work was supported by the Spanish MINECO under grants TIN 2010-21062-C02-02 and TIN 2013-45732-C4-1-P, and the REFRAME project, granted by the European Coordinated Research on Longterm Challenges in Information and Communication Sciences Technologies ERA-Net (CHIST-ERA), and funded by MINECO in Spain (PCIN-2013-037) and by Generalitat Valenciana PROMETEOII2015/013.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Capítulo o parte de un libro (BookPart)

Evaluating a reinforcement learning algorithm with a general intelligence test

  • Insa Cabrera, Javier
  • Dowe, David L.
  • Hernández-Orallo, José|||0000-0001-9746-7632
In this paper we apply the recent notion of anytime universal intelligence tests to the evaluation of a popular reinforcement learning algorithm, Q-learning. We show that a general approach to intelligence evaluation of AI algorithms is feasible. This top-down (theory-derived) approach is based on a generation of environments under a Solomonoff universal distribution instead of using a pre-defined set of specific tasks, such as mazes, problem repositories, etc. This first application of a general intelligence test to a reinforcement learning algorithm brings us to the issue of task-specific vs. general AI agents. This, in turn, suggests new avenues for AI agent evaluation and AI competitions, and also conveys some further insights about the performance of specific algorithms. © 2011 Springer-Verlag., We are grateful for the funding from the Spanish MEC and MICINN for projects TIN2009-06078-E/TIN, Consolider-Ingenio CSD2007-00022 and TIN2010-21062-C02, for MEC FPU grant AP2006-02323, and Generalitat Valenciana for Prometeo/2008/051.