Pasar al contenido principal

SWEETLOGICS-UPV

TIN2010-21062-C02-02

•
Nombre agencia financiadora Ministerio de Ciencia e Innovación
Acrónimo agencia financiadora MICINN
Programa Programa Nacional de Proyectos de Investigación Fundamental
Subprograma Subprograma de Proyectos de Investigación Fundamental no Orientada
Convocatoria Proyectos I+D
Año convocatoria 2010
Plan Estatal 2008-2011 Plan Nacional de Investigación Científica, Desarrollo e Innovación Tecnológica
Unidad de gestión Subdirección General de Proyectos de Investigación
Centro beneficiario UNIVERSITAT POLITÈCNICA DE VALÈNCIA
Identificador persistente http://dx.doi.org/10.13039/501100004837

Resultados relacionados

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

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

Bridging the Gap between Distance and Generalization

  • Estruch Gregori, Vicente
  • 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
Distance-based and generalization-based methods are two families of artificial intelligence techniques that have been successfully used over a wide range of real-world problems. In the first case, general algorithms can be applied to any data representation by just changing the distance. The metric space sets the search and learning space, which is generally instance-oriented. In the second case, models can be obtained for a given pattern language, which can be comprehensible. The generality-ordered space sets the search and learning space, which is generally model-oriented. However, the concepts of distance and generalization clash in many different ways, especially when knowledge representation is complex (e.g., structured data). This work establishes a framework where these two fields can be integrated in a consistent way. We introduce the concept of distance-based generalization, which connects all the generalized examples in such a way that all of them are reachable inside the generalization by using straight paths in the metric space. This makes the metric space and the generality-ordered space coherent (or even dual). Additionally, we also introduce a definition of minimal distance-based generalization that can be seen as the first formulation of the Minimum Description Length (MDL)/Minimum Message Length (MML) principle in terms of a distance function. We instantiate and develop the framework for the most common data representations and distances, where we show that consistent instances can be found for numerical data, nominal data, sets, lists, tuples, graphs, first-order atoms, and clauses. As a result, general learning methods that integrate the best from distance-based and generalization-based methods can be defined and adapted to any specific problem by appropriately choosing the distance, the pattern language and the generalization operator., We would like to thank the anonymous reviewers for their insightful comments. This work has been partially supported by the EU (FEDER) and the Spanish MICINN, under grant TIN2010-21062-C02-02, 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)

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 Artículo científico (JournalArticle)

Order-Sorted Equality Enrichments Modulo Axioms

  • Gutiérrez Gil, Raúl|||0000-0002-3984-2868
  • Meseguer, Jose
  • Rocha, Camilo
Built-in equality and inequality predicates based on comparison of canonical forms in algebraic specifications are frequently used because they are handy and efficient. However, their use places algebraic specifications with initial algebra semantics beyond the pale of theorem proving tools based, for example, on explicit or inductionless induction techniques, and of other formal tools for checking key properties such as confluence, termination, and sufficient completeness. Such specifications would instead be amenable to formal analysis if an equationally-defined equality predicate enriching the algebraic data types were to be added to them. Furthermore, having an equationally-defined equality predicate is very useful in its own right, particularly in inductive theorem proving. Is it possible to effectively define a theory transformation epsilon bar right arrow epsilon(similar to) that extends an algebraic specification epsilon to a specification epsilon(similar to) having an equationally-defined equality predicate? This paper answers this question in the affirmative for a broad class of order-sorted conditional specifications epsilon that are sort-decreasing, ground confluent, and operationally terminating modulo axioms B and have a subsignature of constructors. The axioms B can consist of associativity, or commutativity, or associativity-commutativity axioms, so that the constructors are free modulo B. We prove that the transformation epsilon bar right arrow epsilon(similar to) preserves all the just-mentioned properties of epsilon. The transformation has been automated in Maude using reflection and is used as a component in many Maude formal tools. (C) 2014 Elsevier B.V. All rights reserved., This work has been supported in part by NSF Grants CCF 09-05584 and CNS 13-19109, the EU (FEDER) and the Spanish MINECO under Grants TIN 2010-21062-C02 and TIN 2013-45732-C4-1-P, and by the Generalitat Valenciana, ref. PROMETEO/2011/052. Raul Gutierrez is also partially supported by a Juan de la Cierva Fellowship from the Spanish MINECO, ref. JCI-2012-13528.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

A rewriting logic approach to the formal specification and verification of web applications

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Ballis, Demis
  • Romero, Daniel Omar
[EN] This paper develops a Rewriting Logic framework for the automatic specification and verification of Web applications that considers the critical aspects of concurrent Web interactions, browser navigation features (e.g., forward/back-ward navigation, page refresh, and new window/tab opening), and Web script evaluation. By encompassing the main features of the most popular Web scripting languages (e.g., PHP, ASP, and Java Servlets), our scripting language is powerful enough to model the dynamics of complex Web applications, where the interactions among Web servers and Web browsers are formalized through a landmark communicating protocol that abstracts HTTP. We provide a detailed characterization of browser actions via rewrite rules and show how our models can be naturally model-checked by using the Linear Temporal Logic of Rewriting (LTLR), which is a Linear Temporal Logic that is specifically designed for model-checking rewrite theories. The framework has been completely implemented in Maude, and we report on some successful experiments that we conducted using the Maude LTLR model-checker., This work has been partially supported by the EU (FEDER) and the Spanish MEC project ref. TIN2010-21062-C02-02, and by Generalitat Valenciana ref. PROMETE02011/052. This work was carried out during the tenure by Demis Ballis of an 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 no 246016. Daniel Romero was partially supported by FPI-MEC grant BES-2008-004860.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Estudio, informe, memoria (Report)

A Condensed Goal-Independent Bottom-Up Fixpoint Semantics Modeling the Behavior of tccp

  • Comini, Marco
  • Titolo, Laura
  • Villanueva, Alicia|||0000-0003-1090-5009
In this paper, we present a new compositional bottom-up semantics for the Timed Concurrent Constraint Language (tccp in short) which is defined for the full language. In particular, is able to deal with the non- monotonic characteristic of tccp, which constitutes a substantial addi- tional technical difficulty w.r.t. other compositional denotational seman- tics present in literature (which do not tackle the full language). The semantics is proved to be (correct and) fully abstract w.r.t. the full behavior of tccp, including infinite computations. This is particularly important since tccp has been defined to model reactive systems and they may not terminate with a purpose. The overall of these features makes our proposal particularly suitable as the basis for the definition of semantic-based program manipulation tools (like analyzers, debuggers or verifiers), especially in the context of reactive systems.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

IQ tests are not for machines, yet

  • Dowe, David L.
  • Hernández-Orallo, José|||0000-0001-9746-7632
[EN] Complex, but specific, tasks¿such as chess or Jeopardy!¿are popularly seen as milestones for artificial intelligence (AI). However, they are not appropriate for evaluating the intelligence of machines or measuring the progress in AI. Aware of this delusion, Detterman has recently raised a challenge prompting AI researchers to evaluate their artefacts against IQ tests. We agree that the philosophy behind (human) IQ tests is a much better approach to machine intelligence evaluation than these specific tasks, and also more practical and informative than the Turing test. However, we have first to recall some work on machine intelligence measurement which has shown that some IQ tests can be passed by relatively simple programs. This suggests that the challenge may not be so demanding and may just work as a sophisticated CAPTCHA, since some types of tests might be easier than others for the current state of AI. Second, we show that an alternative, formal derivation of intelligence tests for machines is possible, grounded in (algorithmic) information theory. In these tests, we have a proper mathematical definition of what is being measured. Third, we re-visit some research done in the past fifteen years for effectively measuring machine intelligence¿since some assumptions about the subjects and their distribution no longer hold., This work was supported by the MEC projects EXPLORAINGENIO TIN 2009-06078-E, CONSOLIDER-INGENIO 26706 and TIN 2010-21062-C02-02, and GVA project PROMETEO/2008/051.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Rewriting-based repairing strategies for XML repositories

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Romero, Daniel
  • Ballis, Demis
  • Falaschi, M.
  • Frechina, Francisco
[EN] Keeping XML data in a consistent state w.r.t. both structure and content is a burdensome task. To maintain the consistency of ever-larger, complex XML repositories, suitable mechanisms that are able to x every possible inconsistency are needed. In this article, we present a methodology for semi-automatically repairing faulty XML repositories that can be integrated on top of an existing rewriting-based veri cation engine. As a formal basis for representing consistency criteria, we use a rule-based description formalism that is realized in the language Maude. Then, starting from a categorization of the kinds of errors that can be found during the veri cation process, we formulate a stepwise transformation procedure that achieves correctness and completeness of the XML repository w.r.t. its Maude formal speci cation while strictly observing the structure of the XML documents. With the aim of increasing the level of automation of our repair methodology, we also de ne two correction strategies and two completion strategies that reduce either the amount of information to be changed or the number of repair actions to be executed in order to deliver an XML repository that is both correct and complete. Finally, we describe a prototype implementation of the repairing tool, which we use for an experimental evaluation of our method with good results. ©2013 Elsevier Inc.All rights reserved., This work has been partially supported by the EU (FEDER) and the Spanish MEC project ref. TIN2010-21062-C02-02, 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 and D. Romero by FPI-MEC grant BES-2008-004860 We would like to thank the anonymous reviewers for their helpful comments.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Universal psychometrics: measuring cognitive abilities in the machine kingdom

  • Hernández-Orallo, José|||0000-0001-9746-7632
  • Dowe, David L.
  • Hernández Lloreda, M. Victoria
We present and develop the notion of ‘universal psychometrics’ as a subject of study, and eventually a discipline, that focusses on the measurement of cognitive abilities for the machine kingdom, which comprises any (cognitive) system, individual or collective, either artificial, biological or hybrid. Universal psychometrics can be built, of course, upon the experience, techniques and methodologies from (human) psychometrics, comparative cognition and related areas. Conversely, the perspective and techniques which are being developed in the area of machine intelligence measurement using (algorithmic) information theory can be of much broader applicability and implication outside artificial intelligence. This general approach to universal psychometrics spurs the re-understanding of most (if not all) of the big issues about the measurement of cognitive abilities, and creates a new foundation for (re)defining and mathematically formalising the concept of cognitive task, evaluable subject, interface, task choice, difficulty, agent response curves, etc. We introduce the notion of a universal cognitive test and discuss whether (and when) it may be necessary for exploring the machine kingdom. On the issue of intelligence and very general abilities, we also get some results and connections with the related notions of no-free-lunch theorems and universal priors, We thank the anonymous reviewers for their comments. This work was supported by the MEC-MINECO projects CONSOLIDER-INGENIO CSD2007-00022 and TIN 2010-21062-C02-02, GVA project PROMETEO/2008/051, the COST -European Cooperation in the field of Scientific and Technical Research IC0801 AT
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Contribución de congreso (ConferenceOutput)

Proving Operational Termination of Declarative Programs in General Logics

  • Lucas Alba, Salvador|||0000-0001-9923-2108
  • Meseguer, José
A declarative program P is a *theory* in a given computational logic L, so that *computation* with such a program is efficiently implemented as *deduction* in L. That is why *inference systems* are crucial: they both (i) *define* the logical semantics of a language in its underlying logic L, and (ii) *specify* the *execution* of programs in a correct implementation. The notion of *operational termination* (OT) of a declarative program P identifies termination with *absence of infinite inference* with P. We further develop the OT notion for declarative programs in general logics with schematic inference systems and characterize OT in terms of *chains of proof jumps*. We also generalize the dependency pair framework to an arbitrary schematic logic L, so that methods for proving declarative programs OT become available for a very wide range of declarative languages. We illustrate the usefulness of the general OT methods we propose by three case studies in three logics: that of Conditional Term Rewriting Systems, the Typed Lambda Calculus, and Membership Rewriting Logic. In particular, we show how various programs that could not be proved terminating with existing methods can be proved OT with the methods presented here., Partially supported by NSF grant CNS 13-19109. Salvador Lucas’ research was developed during a sabbatical year at the UIUC and was also supported by the EU (FEDER), Spanish MINECO projects TIN2010-21062-C02-02 and TIN 2013-45732-C4-1-P, and GV grant BEST/2014/026 and project PROMETEO/2011/052.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Completeness of Context-Sensitive Rewriting

  • Lucas Alba, Salvador|||0000-0001-9923-2108
Restrictions of rewriting may turn normal forms of some terms unreachable, leading to incomplete computations. Context-sensitive rewriting (csr) is the restriction of rewriting that only permits reductions on arguments selected by a replacement map μ, which associates a subset μ(f ) of argument indices with each function symbol f . Hendrix and Meseguer defined an algebraic semantics for Term Rewriting Systems (TRSs) executing csr that can be used to reason about programs written in programming languages like CafeOBJ and Maude, where such replacement restrictions can be specified in programs. Semantic completeness of csr was also defined. In this paper we show that canonical replacement maps, which play a prominent role in simulating rewriting computations with csr, are necessary for completeness in important classes of TRSs. © 2014 Elsevier B.V. All rights reserved., Supported by NSF CNS 13-19109, MINECO project TIN2010-21062-C02-02, GV (Generalitat Valenciana) Grants BEST/2014/026 and PROMETEO/2011/052.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Abstract Diagnosis for tccp using a Linear Temporal Logic

  • Comini, Marco
  • Titolo, Laura
  • Villanueva, Alicia|||0000-0003-1090-5009
[EN] Automatic techniques for program verification usually suffer the well-known state explosion problem. Most of the classical approaches are based on browsing the structure of some form of model (which represents the behavior of the program) to check if a given specification is valid. This implies that a part of the model has to be built, and sometimes the needed fragment is quite huge. In this work, we provide an alternative automatic decision method to check whether a given property, specified in a linear temporal logic, is valid w.r.t. a tccp program. Our proposal (based on abstract interpretation techniques) does not require to build any model at all. Our results guarantee correctness but, as usual when using an abstract semantics, completeness is lost., 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. prometeo2011/052.
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 Artículo científico (JournalArticle)

On environment difficulty and discriminating power

  • Hernández-Orallo, José|||0000-0001-9746-7632
This paper presents a way to estimate the difficulty and discriminating power of any task instance. We focus on a very general setting for tasks: interactive (possibly multiagent) environments where an agent acts upon observations and rewards. Instead of analysing the complexity of the environment, the state space or the actions that are performed by the agent, we analyse the performance of a population of agent policies against the task, leading to a distribution that is examined in terms of policy complexity. This distribution is then sliced by the algorithmic complexity of the policy and analysed through several diagrams and indicators. The notion of environment response curve is also introduced, by inverting the performance results into an ability scale. We apply all these concepts, diagrams and indicators to two illustrative problems: a class of agent-populated elementary cellular automata, showing how the difficulty and discriminating power may vary for several environments, and a multiagent system, where agents can become predators or preys, and may need to coordinate. Finally, we discuss how these tools can be applied to characterise (interactive) tasks and (multi-agent) environments. These characterisations can then be used to get more insight about agent performance and to facilitate the development of adaptive tests for the evaluation of agent abilities., I thank the reviewers for their comments, especially those aiming at a clearer connection with the field of multi-agent systems and the suggestion of better approximations for the calculation of the response curves. The implementation of the elementary cellular automata used in the environments is based on the library 'CellularAutomaton' by John Hughes for R [58]. I am grateful to Fernando Soler-Toscano for letting me know about their work [65] on the complexity of 2D objects generated by elementary cellular automata. I would also like to thank David L. Dowe for his comments on a previous version of this paper. This work was supported by the MEC/MINECO projects CONSOLIDER-INGENIO CSD2007-00022 and TIN 2010-21062-C02-02, GVA project PROMETEO/2008/051, the COST - European Cooperation in the field of Scientific and Technical Research IC0801 AT, 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 Economia y Competitividad in Spain (PCIN-2013-037).
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 Artículo científico (JournalArticle)

Debugging of Web Applications with Web-TLR

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Espert Real, Javier
  • Frechina Navarro, Francisco
  • Romero, Daniel Omar
  • Ballis, Demis
[EN] Web-TLR is a Web verification engine that is based on the well-established Rewriting Logic--Maude/LTLR tandem for Web system specification and model-checking. In Web-TLR, Web applications are expressed as rewrite theories that can be formally verified by using the Maude built-in LTLR model-checker. Whenever a property is refuted, a counterexample trace is delivered that reveals an undesired, erroneous navigation sequence. Unfortunately, the analysis (or even the simple inspection) of such counterexamples may be unfeasible because of the size and complexity of the traces under examination. In this paper, we endow Web-TLR with a new Web debugging facility that supports the efficient manipulation of counterexample traces. This facility is based on a backward trace-slicing technique for rewriting logic theories that allows the pieces of information that we are interested to be traced back through inverse rewrite sequences. The slicing process drastically simplifies the computation trace by dropping useless data that do not influence the final result. By using this facility, the Web engineer can focus on the relevant fragments of the failing application, which greatly reduces the manual debugging effort and also decreases the number of iterative verifications., This work has been partially supported by the EU (FEDER) and the Spanish MEC TIN2010-21062-C02-02 project, by Generalitat Valenciana, ref. PROMETEO2011/052, and by the Italian MUR under grant RBIN04M8S8, FIRB project, Internationalization 2004. Daniel Romero is also supported by FPI–MEC grant BES–2008–004860
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 Artículo científico (JournalArticle)

Aggregative quantification for regression

  • 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
The problem of estimating the class distribution (or prevalence) for a new unlabelled dataset (from a possibly different distribution) is a very common problem which has been addressed in one way or another in the past decades. This problem has been recently reconsidered as a new task in data mining, renamed quantification when the estimation is performed as an aggregation (and possible adjustment) of a single-instance supervised model (e.g., a classifier). However, the study of quantification has been limited to classification, while it is clear that this problem also appears, perhaps even more frequently, with other predictive problems, such as regression. In this case, the goal is to determine a distribution or an aggregated indicator of the output variable for a new unlabelled dataset. In this paper, we introduce a comprehensive new taxonomy of quantification tasks, distinguishing between the estimation of the whole distribution and the estimation of some indicators (summary statistics), for both classification and regression. This distinction is especially useful for regression, since predictions are numerical values that can be aggregated in many different ways, as in multi-dimensional hierarchical data warehouses. We focus on aggregative quantification for regression and see that the approaches borrowed from classification do not work. We present several techniques based on segmentation which are able to produce accurate estimations of the expected value and the distribution of the output variable. We show experimentally that these methods especially excel for the relevant scenarios where training and test distributions dramatically differ., We would like to thank the anonymous reviewers for their careful reviews, insightful comments and very useful suggestions. This work was supported by the MEC/MINECO projects CONSOLIDER-INGENIO CSD2007-00022 and TIN 2010-21062-C02-02, GVA project PROME-TEO/2008/051, the COST-European Cooperation in the field of Scientific and Technical Research IC0801 AT, 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 Economia y Competitividad in Spain.
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 Artículo científico (JournalArticle)

A Modular Order-sorted Equational Generalization Algorithm

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Escobar Román, Santiago|||0000-0002-3550-4781
  • Espert Real, Javier
  • Meseguer, José
Generalization, also called anti-unification, is the dual of unification. Given terms t and t , a generalizer is a term t of which t and t are substitution instances. The dual of a most general unifier (mgu) is that of least general generalizer (lgg). In this work, we extend the known untyped generalization algorithm to, first, an order-sorted typed setting with sorts, subsorts, and subtype polymorphism; second, we extend it to work modulo equational theories, where function symbols can obey any combination of associativity, commutativity, and identity axioms (including the empty set of such axioms); and third, to the combination of both, which results in a modular, order-sorted equational generalization algorithm. Unlike the untyped case, there is in general no single lgg in our framework, due to order-sortedness or to the equational axioms. Instead, there is a finite, minimal and complete set of lggs, so that any other generalizer has at least one of them as an instance. Our generalization algorithms are expressed by means of inference systems for which we give proofs of correctness. This opens up new applications to partial evaluation, program synthesis, and theorem proving for typed equational reasoning systems and typed rulebased languages such as ASF+SDF, Elan, OBJ, Cafe-OBJ, and Maude. © 2014 Elsevier Inc. All rights reserved. 1., M. Alpuente, S. Escobar, and J. Espert 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. J. Meseguer has been supported by NSF Grants CNS 09-04749, and CCF 09-05584.
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 Artículo científico (JournalArticle)

Formal methods for industrial critical systems, preface to the special section

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Joubert ., Christophe
  • Kowalewski, S.
  • Roveri, M.
[EN] This special issue contains improved versions of selected papers from the workshops on Formal Methods for Industrial Critical Systems (FMICS) held in Eindhoven, The Netherlands, in November 2009 and in Antwerp, Belgium, in September 2010. These were, respectively, the 14th and 15th of a series of international workshops organized by an open working group supported by ERCIM (European Research Consortium for Informatics and Mathematics) that promotes research in all aspects of formal methods (see details in http://www.inrialpes.fr/vasy/fmics/). The FMICS workshops that have produced this special issue considered papers describing original, previously unpublished research and not simultaneously submitted for publication elsewhere, and dealing with the following themes: Design, specification, code generation and testing based on formal methods. Methods, techniques and tools to support automated analysis, certification, debugging, learning, optimization and transformation of complex, distributed, real-time and embedded systems. Verification and validation methods that address shortcomings of existing methods with respect to their industrial applicability (e.g., scalability and usability issues). Tools for the development of formal design descriptions. Case studies and experience reports on industrial applications of formal methods, focusing on lessons learned or new research directions. Impact and costs of the adoption of formal methods. Application of formal methods in standardization and industrial forums. The selected papers are the result of several evaluation steps. In response to the call for papers, FMICS 2009 received 24 papers and FMICS 2010 received 33 papers, with 10 and 14 accepted, respectively, which were published by Springer- Verlag in the series Lecture Notes in Computer Science (volumes 5825 [1] and 6371 [2]). Each paper was reviewed by at least three anonymous referees which provided full written evaluations. After the workshops, the authors of 10 papers were invited to submit extended journal versions to this special issue. These papers passed two review phases, and finally 7 were accepted to be included in the journal., his work has been partially supported by the EU (FEDER) and the Spanish MEC TIN2010-21062-C02-02 project, MICINN INNCORPORA-PTQ program, and by Generalitat Valenciana, ref. PROMETEO2011/052.
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 Contribución de congreso (ConferenceOutput)

Towards an Incremental and Modular Termination Analysis of Context-Sensitive Rewriting Systems (Work in Progress)

  • Gutiérrez Gil, Raúl|||0000-0002-3984-2868
  • Lucas Alba, Salvador|||0000-0001-9923-2108
Modularity is essential in software development, where a piece of software is often designed and implemented as a composition of simpler modules. So, if we want to prove that a program satisfies a given property, a modular approach becomes natural. With the development and successful use of the Dependency Pair Framework, which rather focuses on the decomposition of termination problems, less attention has been payed to modularity issues (which rather require the opposite approach). But the modular analysis of termination is still paramount for software developers. In this paper, we analyze modularity of context-sensitive rewrite systems. A modularity analysis was carried out by Gramlich and Lucas in 2002, but a correct notion of context-sensitive dependency pair (CS-DP) was not obtained until 2006. In this paper, we analyze modularity using CS-DPs., Partially supported by the EU (FEDER), MINECO projects TIN2010-21062-C02-02 and TIN 2013-45732-C4-1-P, and project PROMETEO/2011/052. Salvador Lucas’ research was developed during a sabbatical year at the CS Dept. of the UIUC and was also partially supported by NSF grant CNS 13-19109, Spanish MECD grant PRX12/00214, and GV grant BEST/2014/026. Raúl Gutiérrez is also partially supported by a Juan de la Cierva Fellowship from the Spanish MINECO, ref. JCI-2012-13528.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Exploring Conditional Rewriting Logic Computations

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Sapiña-Sanchis, Julia|||0000-0003-2994-6986
  • Ballis, Demis
  • Frechina Navarro, Francisco
[EN] Trace exploration is concerned with techniques that allow computation traces to be dynamically searched for specific contents. Depending on whether the exploration is carried backward or forward, trace exploration techniques allow provenance tracking or impact tracking to be done. The aim of provenance tracking is to show how (parts of) a program output depends on (parts of) its input and to help estimate which input data need to be modified to accomplish a change in the outcome. The aim of impact tracking is to identify the scope and potential consequences of changing the program input. Rewriting Logic (RWL) is a logic of change that supplements (an extension of) the equational logic by adding rewrite rules that are used to describe (nondeterministic) transitions between states. In this paper, we present a rich and highly dynamic, parameterized technique for the forward inspection of RWL computations that allows the nondeterministic execution of a given conditional rewrite theory to be followed up in different ways. With this technique, an analyst can browse, slice, filter, or search the traces as they come to life during the program execution. 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, This work has been partially supported by the EU (FEDER) and 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, and J. Sapina was supported by FPI-UPV grant SP2013-0083.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Folding variant narrowing and optimal variant termination

  • Escobar Román, Santiago|||0000-0002-3550-4781
  • Sasse, Ralf
  • Meseguer, José
Automated reasoning modulo an equational theory E is a fundamental technique in many applications. If E can be split as a disjoint union E u Ax in such a way that E is confluent, terminating, sort-decreasing, and coherent modulo a set of equational axioms Ax, narrowing with E modulo Ax provides a complete E-unification algorithm. However, except for the hopelessly inefficient case of full narrowing, little seems to be known about effective narrowing strategies in the general modulo case beyond the quite depressing observation that basic narrowing is incomplete modulo AC. Narrowing with equations E modulo axioms Ax can be turned into a practical automated reasoning technique by systematically exploiting the notion of E, Ax-variants of a term. After reviewing such a notion, originally proposed by Comon-Lundh and Delaune, and giving various necessary and/or sufficient conditions for it, we explain how narrowing strategies can be used to obtain narrowing algorithms modulo axioms that are: (i) variant-complete (generate a complete set of variants for any input term), (ii) minimal (such a set does not have redundant variants), and (iii) are optimally variant-terminating (the strategy will terminate for an input term t iff t has a finite complete set of variants). We define a strategy called folding variant narrowing that satisfies above properties (i)-(iii); in particular, when E u Ax has the finite variant property, that is, when any term t has a finite complete set of variants, this strategy terminates on any input term and provides a finitary E u Ax-unification algorithm. We also explain how folding variant narrowing has a number of interesting applications in areas such as unification theory, cryptographic protocol verification, and proofs of termination, confluence and coherence of a set of rewrite rules R modulo an equational theory E. © 2012 Elsevier Inc. All rights reserved, S. Escobar has 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. R. Sasse and J. Meseguer have been partially supported by NSF Grants CNS 07-16638, CNS 08-31064, CNS 09-04749, and CCF 09-05584.
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 Artículo científico (JournalArticle)

Normal forms and normal theories in conditional rewriting

  • Lucas Alba, Salvador|||0000-0001-9923-2108
  • Meseguer, Jose
We present several new concepts and results on conditional term rewriting within the general framework of order-sorted rewrite theories (OSRTs), which support types, subtypes and rewriting modulo axioms, and contains the more restricted framework of conditional term rewriting systems (CTRSs) as a special case. The concepts shed light on several subtle issues about conditional rewriting and conditional termination. We point out that the notions of irreducible term and of normal form, which coincide for unconditional rewriting, have been conflated for conditional rewriting but are in fact totally different notions. Normal form is a stronger concept. We call any rewrite theory where all irreducible terms are normal forms a normal theory. We argue that normality is essential to have good executability and computability properties. Therefore we call all other theories abnormal, freaks of nature to be avoided. The distinction between irreducible terms and normal forms helps in clarifying various notions of strong and weak termination. We show that abnormal theories can be terminating in various, equally abnormal ways; and argue that any computationally meaningful notion of strong or weak conditional termination should be a property of normal theories. In particular we define the notion of a weakly operationally terminating (or weakly normalizing) OSRT, discuss 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, weakly normalizing OSRT coincide thanks to a notion of canonical term algebra. Finally, we investigate appropriate conditions and proof methods to ensure that a rewrite theory is normal; and characterize the stronger property of a rewrite theory being operationally terminating in terms of a natural generalization of the notion of quasidecreasing order. (C) 2015 Elsevier Inc. All rights reserved., We thank the anonymous referees for their constructive criticism and helpful comments. This work has been partially supported by NSF grant CNS 13-19109. Salvador Lucas' research was developed during a sabbatical year at UIUC and was also supported by the EU (FEDER), Spanish MINECO projects TIN2010-21062-C02-02 and TIN 2013-45732-C4-1-P, and GV grant BEST/2014/026 and project PROMETEO/2011/052.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

State space reduction in the Maude-NRL Protocol Analyzer

  • Escobar Román, Santiago|||0000-0002-3550-4781
  • Meadows, Cahterine
  • Meseguer, José
  • Santiago Pinazo, Sonia
The Maude-NRL Protocol Analyzer (Maude-NPA) is a tool and inference system for reasoning about the security of cryptographic protocols in which the cryptosystems satisfy different equational properties. It both extends and provides a formal framework for the original NRL Protocol Analyzer, which supported equational reasoning in a more limited way. Maude-NPA supports a wide variety of algebraic properties that includes many crypto-systems of interest such as, for example, one-time pads and Diffie–Hellman. Maude-NPA, like the original NPA, looks for attacks by searching backwards from an insecure attack state, and assumes an unbounded number of sessions. Because of the unbounded number of sessions and the support for different equational theories, it is necessary to develop ways of reducing the search space and avoiding infinite search paths. In order for the techniques to prove useful, they need not only to speed up the search, but should not violate completeness, so that failure to find attacks still guarantees security. In this paper we describe some state space reduction techniques that we have implemented in Maude-NPA. We also provide completeness proofs, and experimental evaluations of their effect on the performance of Maude-NPA., We would like to thank Antonio Gonzalez for his help in providing several protocol specifications in Maude-NPA. 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. J. Meseguer and S. Escobar have been partially supported by NSF grants CNS 09-04749, and CCF 09-05584.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

On the effect of calibration in classifier combination

  • 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
A general approach to classifier combination considers each model as a probabilistic classifier which outputs a class membership posterior probability. In this general scenario, it is not only the quality and diversity of the models which are relevant, but the level of calibration of their estimated probabilities as well. In this paper, we study the role of calibration before and after classifier combination, focusing on evaluation measures such as MSE and AUC, which better account for good probability estimation than other evaluation measures. We present a series of findings that allow us to recommend several layouts for the use of calibration in classifier combination. We also empirically analyse a new non-monotonic calibration method that obtains better results for classifier combination than other monotonic calibration methods., We thank the anonymous reviewers for their comments, which have helped to improve this paper significantly. This work was supported by the MEC/MINECO projects CONSOLIDER-INGENIO CSD2007-00022, COST action IC0801 and TIN 2010-21062-C02-02, GVA project PROMETEO/2008/051, and the RE-FRAME 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 Economia y Competitividad in Spain.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Clustering and internal resources: moderation and mediation effects

  • Belso Martínez, José Antonio
  • Molina Morales, Francesc Xavier
  • Mas Verdú, Francisco|||0000-0002-0902-9462
[EN] Purpose ¿ This paper aims to address a central question in strategy: how do internal resources firms mediate the effect of the external resources on the firms' performance? Design/methodology/approach ¿ The research was conducted in a sample of 173 Spanish innovative firms located in the Valencia region. Following the literature, the growth of the firm has been used as the main performance indicator. The paper considers the application in this context of the particular and new analysis techniques to combine mediator and moderator effects. Findings ¿ The research shows firms with higher internal resources exploit better external resources. The results confirm that knowledge intensive business services providers, as a form of external resources, exercise a positive influence on innovative firms' performance through the mediating effect of firms' internal assets. Research limitations/implications ¿ First, the study uses only two well-known internal resources and capabilities indicators. Second, the paper applies a strict and simple measure to the growth of innovative firms. Third, another limitation of this research relates to the sample and population of companies. Practical implications ¿ The study shows that the partial mediating effect exercised by internal resources and capabilities on growth, becomes more intense when new firms benefit from cluster location. Originality/value ¿ This study represents a new step toward closing the analytical gap in the existing literature on the potential interactions between external resources and new firm's internal attributes, and their combined effects on performance., Financial support was provided by Spanish Ministry of Education and Science (project ECO2008-04708) and Ministry of Science and Innovation (Project ECO2010-20557).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

On potential cognitive abilities in the machine kingdom

  • Hernández-Orallo, José
  • Dowe, David L.
Animals, including humans, are usually judged on what they could become, rather than what they are. Many physical and cognitive abilities in the ‘animal kingdom’ are only acquired (to a given degree) when the subject reaches a certain stage of development, which can be accelerated or spoilt depending on how the environment, training or education is. The term ‘potential ability’ usually refers to how quick and likely the process of attaining the ability is. In principle, things should not be different for the ‘machine kingdom’. While machines can be characterised by a set of cognitive abilities, and measuring them is already a big challenge, known as ‘universal psychometrics’, a more informative, and yet more challenging, goal would be to also determine the potential cognitive abilities of a machine. In this paper we investigate the notion of potential cognitive ability for machines, focussing especially on universality and intelligence. We consider several machine characterisations (non-interactive and interactive) and give definitions for each case, considering permanent and temporal potentials. From these definitions, we analyse the relation between some potential abilities, we bring out the dependency on the environment distribution and we suggest some ideas about how potential abilities can be measured. Finally, we also analyse the potential of environments at different levels and briefly discuss whether machines should be designed to be intelligent or potentially intelligent., We thank the anonymous reviewers for their comments, which have helped to significantly improve this paper. This work was supported by the MEC-MINECO projects CONSOLIDER-INGENIO CSD2007-00022 and TIN 2010-21062-C02-02, GVA project PROMETEO/2008/051, the COST - European Cooperation in the field of Scientific and Technical Research IC0801 AT. Finally, we thank three pioneers ahead of their time(s). We thank Ray Solomonoff (1926-2009) and Chris Wallace (1933-2004) for all that they taught us, directly and indirectly. And, in his centenary year, we thank Alan Turing (1912-1954), with whom it perhaps all began.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

How universal can an intelligence test be?

  • Dowe, David L.
  • Hernández-Orallo, José|||0000-0001-9746-7632
[EN] The notion of a universal intelligence test has been recently advocated as a means to assess humans, non-human animals and machines in an integrated, uniform way. While the main motivation has been the development of machine intelligence tests, the mere concept of a universal test has many implications in the way human intelligence tests are understood, and their relation to other tests in comparative psychology and animal cognition. From this diversity of subjects in the natural and artificial kingdoms, the very possibility of constructing a universal test is still controversial. In this paper we rephrase the question of whether universal intelligence tests are possible or not into the question of how universal intelligence tests can be, in terms of subjects, interfaces and resolutions. We discuss the feasibility and difficulty of universal tests depending on several levels according to what is taken for granted: the communication milieu, the resolution, the reward system or the agent itself. We argue that such tests must be highly adaptive, i.e., that tasks, resolution, rewards and communication have to be adapted according to how the evaluated agent is reacting and performing. Even so, the most general expression of a universal test may not be feasible (and, at best, might only be theoretically semi-computable). Nonetheless, in general, we can analyse the universality in terms of some traits that lead to several levels of universality and set the quest for universal tests as a progressive rather than absolute goal., This work was supported by the MEC/MINECO (projects CONSOLIDER-INGENIO CSD2007-00022 and TIN 2010-21062-C02-02), the GVA (project PROMETEO/2008/051) and the COST-European Cooperation in the field of Scientific and Technical Research (project IC0801 AT).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

ROC curves for regression

  • Hernández-Orallo, José|||0000-0001-9746-7632
Receiver Operating Characteristic (ROC) analysis is one of the most popular tools for the visual assessment and understanding of classifier performance. In this paper we present a new representation of regression models in the so-called regression ROC (RROC) space. The basic idea is to represent over-estimation against under-estimation. The curves are just drawn by adjusting a shift, a constant that is added (or subtracted) to the predictions, and plays a similar role as a threshold in classification. From here, we develop the notions of optimal operating condition, convexity, dominance, and explore several evaluation metrics that can be shown graphically, such as the area over the RROC curve (AOC). In particular, we show a novel and significant result: the AOC is equivalent to the error variance. We illustrate the application of RROC curves to resource estimation, namely the estimation of software project effort., I would like to thank Peter Flach and Nicolas Lachiche for some very useful comments and corrections on earlier versions of this paper, especially the suggestion of drawing normalised curves (dividing x-axis and y-axis by n). This work was supported by the MEC/MINECO projects CONSOLIDER-INGENIO CSD2007-00022 and TIN 2010-21062-C02-02, GVA project Prometeo/2008/051, the COST - European Cooperation in the field of Scientific and Technical Research IC0801 AT, 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 respective national research councils and ministries.
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 Artículo científico (JournalArticle)

Using conditional trace slicing for improving Maude programs

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Ballis, Demis
  • Frechina, F.
  • Romero, Daniel Omar
[EN] Understanding the behavior of software is important for the existing software to be improved. In this paper, we present a trace slicing technique that is suitable for analyzing complex, textually-large computations in rewriting logic, which is a general framework efficiently implemented in the Maude language that seamlessly unifies a wide variety of logics and models of concurrency. Given a Maude execution trace T and a slicing criterion for the trace (i.e., a piece of information that we want to observe in the final computation state), we traverse T from back to front and the backward dependence of the observed information is incrementally computed at each execution step. At the end of the traversal, a simplified trace slice is obtained by filtering out all the irrelevant data that do not impact on the data of interest. By narrowing the size of the trace, the slicing technique favors better inspection and debugging activities since most tedious and irrelevant inspections that are routinely performed during diagnosis and bug localization can be eliminated automatically. Moreover, cutting down the execution trace can expose opportunities for further improvement, which we illustrate by means of several examples that we execute by using iJulienne, a trace slicer that implements our conditional slicing technique and is endowed with a trace querying mechanism that increases flexibility and reduction power., This work has been partially supported by the EU (FEDER) and the Spanish MEC project ref. TIN2010-21062-C02-02, 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 No. 246016. F. Frechina was supported by FPU-ME grant AP2010-5681 and D. Romero by FPI-MEC grant BES-2008-004860.
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.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Computer models solving intelligence test problems: Progress and implications

  • Hernández-Orallo, José|||0000-0001-9746-7632
  • Martínez-Plumed, Fernando|||0000-0003-2902-6477
  • Schmid, Ute
  • Siebers, Michael
  • Dowe, David L
While some computational models of intelligence test problems were proposed throughout the second half of the XXth century, in the first years of the XXIst century we have seen an increasing number of computer systems being able to score well on particular intelligence test tasks. However, despite this increasing trend there has been no general account of all these works in terms of how they relate to each other and what their real achievements are. Also, there is poor understanding about what intelligence tests measure in machines, whether they are useful to evaluate AI systems, whether they are really challenging problems, and whether they are useful to understand (human) intelligence. In this paper, we provide some insight on these issues, in the form of nine specific questions, by giving a comprehensive account of about thirty computer models, from the 1960s to nowadays, and their relationships, focussing on the range of intelligence test tasks they address, the purpose of the models, how general or specialised these models are, the AI techniques they use in each case, their comparison with human performance, and their evaluation of item difficulty. As a conclusion, these tests and the computer models attempting them show that AI is still lacking general techniques to deal with a variety of problems at the same time. Nonetheless, a renewed attention on these problems and a more careful understanding of what intelligence tests offer for AI may help build new bridges between psychometrics, cognitive science, and AI; and may motivate new kinds of problem repositories. © 2015 Elsevier B.V. All rights reserved., This work has been partially supported by the EU (FEDER) and the Spanish MINECO under grants TIN 2010-21062-C02-02, TIN 2013-45732-C4-1-P and FPI-ME grant BES-2011-045099, and by Generalitat Valenciana PROMETEOII/2015/013. We thank the editor and reviewers for their thorough and insightful comments.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Probabilistic reframing for cost-sensitive regression

  • Hernández-Orallo, José|||0000-0001-9746-7632
Common-day applications of predictive models usually involve the full use of the available contextual information. When the operating context changes, one may fine-tune the by-default (incontextual) prediction or may even abstain from predicting a value (a reject). Global reframing solutions, where the same function is applied to adapt the estimated outputs to a new cost context, are possible solutions here. An alternative approach, which has not been studied in a comprehensive way for regression in the knowledge discovery and data mining literature, is the use of a local (e.g., probabilistic) reframing approach, where decisions are made according to the estimated output and a reliability, confidence, or probability estimation. In this article, we advocate for a simple two-parameter (mean and variance) approach, working with a normal conditional probability density. Given the conditional mean produced by any regression technique, we develop lightweight “enrichment” methods that produce good estimates of the conditional variance, which are used by the probabilistic (local) reframing methods. We apply these methods to some very common families of costsensitive problems, such as optimal predictions in (auction) bids, asymmetric loss scenarios, and rejection rules., This work was supported by the MEC/MINECO projects CONSOLIDER-INGENIO CSD2007-00022 and TIN 2010-21062-C02-02, and TIN 2013-45732-C4-1-P and GVA projects PROMETEO/2008/051 and PROMETEO2011/052. Finally, part of this work was motivated by the REFRAME project (http://www.reframe-d2k.org) granted by the European Coordinated Research on Long-term Challenges in Information and Communication Sciences & Technologies ERA-Net (CHIST-ERA) and funded by Ministerio de Economia y Competitividad in Spain (PCIN-2013-037).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Estudio, informe, memoria (Report)

Abstract Diagnosis for tccp using a Linear Temporal Logic

  • Comini, Marco
  • Titolo, Laura
  • Villanueva, Alicia|||0000-0003-1090-5009
Automatic techniques for program verification usually suffer the well-known state explosion problem. Most of the classical approaches are based on browsing the structure of some form of model (which rep- resents the behavior of the program) to check if a given specification is valid. This implies that a part of the model has to be built, and some- times the needed fragment is quite huge. In this work, we provide an alternative automatic decision method to check whether a given property, specified in a linear temporal logic, is valid w.r.t. a tccp program. Our proposal (based on abstract interpreta- tion techniques) does not require to build any model at all. Our results guarantee correctness but, as usual when using an abstract semantics, completeness is lost.