Skip to main content

RAZONAMIENTO FORMAL PARA TECNOLOGIAS FACILITADORAS Y EMERGENTES

RTI2018-094403-B-C32

•
Funding agency name Agencia Estatal de Investigación
Funding agency acronym AEI
Program Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Call Proyectos I+D+i Retos de Investigación
Call year 2018
State Plan 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Beneficiary centre UNIVERSITAT POLITÈCNICA DE VALÈNCIA

Resultados relacionados

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

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

The 2D Dependency Pair Framework for Conditional Rewrite Systems¿Part II: Advanced Processors and Implementation Techniques

  • Lucas Alba, Salvador|||0000-0001-9923-2108
  • Gutiérrez Gil, Raúl|||0000-0002-3984-2868
  • Meseguer, José
[EN] Proving termination of programs in `real-life¿ rewriting-based languages like CafeOBJ, Haskell, Maude, etc., is an important subject of research. To advance this goal, faithfully cap- turing the impact in the termination behavior of the main language features (e.g., conditions in program rules) is essential. In Part I of this work, we have introduced a 2D Dependency Pair Framework for automatically proving termination properties of Conditional Term Rewriting Systems. Our framework relies on the notion of processor as the main practical device to deal with proofs of termination properties of conditional rewrite systems. Processors are used to decompose and simplify the proofs in a divide and conquer approach. With the basic proof framework defined in Part I, here we introduce new processors to further improve the abil- ity of the 2D Dependency Pair Framework to deal with proofs of termination properties of conditional rewrite systems. We also discuss relevant implementation techniques to use such processors in practice., Partially supported by the EU (FEDER) and projects RTI2018-094403-B-C32, PROMETEO/2019/098, SP20180225. Jose Meseguer was supported by grants NSF CNS 13-19109 and NRL N00173-17-1-G002. Salvador Lucas' research was partly developed during a sabbatical year at the UIUC.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Symbolic Analysis of Maude Theories with Narval

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

Static correction of Maude programs with assertions

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

Proving semantic properties as first-order satisfiability

  • Lucas Alba, Salvador|||0000-0001-9923-2108
[EN] The semantics of computational systems (e.g., relational and knowledge data bases, query-answering systems, programming languages, etc.) can often be expressed as (the specification of) a logical theory Th. Queries, goals, and claims about the behavior or features of the system can be expressed as formulas ¿ which should be checked with respect to the intended model of Th, which is often huge or even incomputable. In this paper we show how to prove such semantic properties ¿ of Th by just finding a model A of Th¿{¿}¿Z¿, where Z¿ is an appropriate (possibly empty) theory depending on ¿ only. Applications to relational and deductive databases, rewriting-based systems, logic programming, and answer set programming are discussed., Partially supported by the EU (FEDER), and projects RTI2018-094403-B-C32, PROMETE0/2019/098, and SP20180225.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Proving and disproving confluence of context-sensitive rewriting

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

Programming and symbolic computation in Maude

  • Durán, Francisco
  • Eker, Steven
  • NARCISO MARTÍ OLIET
  • José Meseguer
  • Rubén Rubio
  • Talcott, Carolyn
  • Escobar Román, Santiago|||0000-0002-3550-4781
[EN] Rewriting logic is both a flexible semantic framework within which widely different concurrent systems can be naturally specified and a logical framework in which widely different logics can be specified. Maude programs are exactly rewrite theories. Maude has also a formal environment of verification tools. Symbolic computation is a powerful technique for reasoning about the correctness of concurrent systems and for increasing the power of formal tools. We present several new symbolic features of Maude that enhance formal reasoning about Maude programs and the effectiveness of formal tools. They include: (i) very general unification modulo user-definable equational theories, and (ii) symbolic reachability analysis of concurrent systems using narrowing. The paper does not focus just on symbolic features: it also describes several other new Maude features, including: (iii) Maude's strategy language for controlling rewriting, and (iv) external objects that allow flexible interaction of Maude object-based concurrent systems with the external world. In particular, meta-interpreters are external objects encapsulating Maude interpreters that can interact with many other objects. To make the paper self-contained and give a reasonably complete language overview, we also review the basic Maude features for equational rewriting and rewriting with rules, Maude programming of concurrent object systems, and reflection. Furthermore, we include many examples illustrating all the Maude notions and features described in the paper., Duran has been partially supported by MINECO/FEDER project TIN2014-52034-R. Escobar has been partially supported by the EU (FEDER) and the MCIU under grant RTI2018-094403-B-C32, by the Spanish Generalitat Valenciana under grant PROMETE0/2019/098, and by the US Air Force Office of Scientific Research under award number FA9550-17-1-0286. MartiOliet and Rubio have been partially supported by MCIU Spanish project TRACES (TIN2015-67522-C3-3-R). Rubio has also been partially supported by a MCIU grant FPU17/02319. Meseguer and Talcott have been partially supported by NRL Grant N00173 -17-1-G002. Talcott has also been partially supported by ONR Grant N00014-15-1-2202.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Analysing the Predictability of Language Model Performance

  • Schellaert, Wout Willy M.
  • Martínez-Plumed, Fernando|||0000-0003-2902-6477
  • Hernández-Orallo, José|||0000-0001-9746-7632
[EN] Can a language model predict for which questions another language model will answer successfully? We investigate the extent to which performance prediction is possible and dissect various factors that influence it. Our experimental setting fine-tunes DeBERTa models, which we call assessors, on the evaluation results of generative language models with up to 128 billion parameters, which we refer to as subject systems. Our analysis spans more than 100 tasks from BIG-bench. We find that the assessors can match and even exceed the subjects' confidence in both refinement and calibration, anticipating failures at near perfect levels for some tasks. We also find that for performance prediction it can be beneficial to learn from the scores on multiple tasks or to learn from the scores of multiple subjects, but both depend on the task at hand. Lastly, we find that large and small subject systems are equally predictable, showing promise for the scalability of the predictability problem., This work was funded by valgrAI, the Future of Life Institute (FLI) under grant RFP2-152, the EU (FEDER) and Spanish grant RTI2018-094403-B-C32 funded by MCIN/AEI/10.13039/501100011033 and by CIPROM/2022/6 funded by Generalitat Valenciana, FISCALTICS (I+D+i PID2022-140110OA-I00) granted by MICIU/AEI/10.13039/501100011033, the Spanish grant PID2021-122830OB-C42 (SFERA) funded by MCIN/AEI/10.13039/501100011033 and 'ERDF A way of making Europe, as well as the European Union under agreement INNEST/2021/317 (Neurocalcat) and by the Vic. Inv. of the Universitat Politecnica de Valencia under DOCEMPR21, DOCEMPR22, and DOCEMPR23'.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Making sense of sensory input

  • Evans, Richard
  • Welbl, Johannes
  • Kohli, Pushmeet
  • Sergot, Marek
  • Hernández-Orallo, José|||0000-0001-9746-7632
[EN] This paper attempts to answer a central question in unsupervised learning: what does it mean to "make sense" of a sensory sequence? In our formalization, making sense involves constructing a symbolic causal theory that both explains the sensory sequence and also satisfies a set of unity conditions. The unity conditions insist that the constituents of the causal theory - objects, properties, and laws - must be integrated into a coherent whole. On our account, making sense of sensory input is a type of program synthesis, but it is unsupervised program synthesis. Our second contribution is a computer implementation, the APPERCEPTION ENGINE, that was designed to satisfy the above requirements. Our system is able to produce interpretable human-readable causal theories from very small amounts of data, because of the strong inductive bias provided by the unity conditions. A causal theory produced by our system is able to predict future sensor readings, as well as retrodict earlier readings, and impute (fill in the blanks of) missing sensory readings, in any combination. In fact, it is able to do all three tasks simultaneously. We tested the engine in a diverse variety of domains, including cellular automata, rhythms and simple nursery tunes, multi-modal binding problems, occlusion tasks, and sequence induction intelligence tests. In each domain, we test our engine's ability to predict future sensor values, retrodict earlier sensor values, and impute missing sensory data. The APPERCEPTION ENGINE performs well in all these domains, significantly out-performing neural net baselines. We note in particular that in the sequence induction intelligence tests, our system achieved human-level performance. This is notable because our system is not a bespoke system designed specifically to solve intelligence tests, but a general-purpose system that was designed to make sense of any sensory sequence. (C) 2020 The Author(s). Published by Elsevier B.V., We are very grateful to Andrew Cropper, Jessica Hamrick, Mark Law, Matko Bo.snjak, Murray Shanahan, Nando de Freitas, and the anonymous reviewers for extensive feedback. JHO has been partially supported by the Future of Life Institute, FLI, under grant RFP2-152, the EU (FEDER) and Spanish MINECO grant RTI2018-094403-B-C32 and Generalitat Valenciana under grant PROMETEO/2019/098.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

The origins of the halting problem

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

Optimization of Rewrite Theories by Equational Partial Evaluation

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Escobar Román, Santiago|||0000-0002-3550-4781
  • Sapiña-Sanchis, Julia|||0000-0003-2994-6986
  • Ballis, D.
[EN] In this paper, we develop an automated optimization framework for rewrite theories that supports sorts, subsort overloading, equations and algebraic axioms with free/nonfree constructors, and rewrite rules modeling concurrent system transitions whose state structure is defined by means of the equations. The main idea of the framework is to make the system computations more efficient by partially evaluating the equations to the specific calls that are required by the transition rules. This can be particularly useful for automatically optimizing rewrite theories that contain overly general equational theories which perform unnecessary and costly computations involving pattern matching and/or unification modulo equations and axioms. The transformation is based on a suitable unfolding operator parameter that relies on the symbolic operational engine of Maude's equational theories, called folding variant narrowing, together with a generic abstraction operator. Depending on the properties of the rewrite theory, the unfolding and abstraction operators must be fine-tuned to achieve the biggest optimization possible while ensuring termination and total correctness of the transformation. We formalize two instances of our scheme for the case when the rewrite theory either has an infinite number of most general variants or a finite number of most general variants. Finally, we discuss some experimental results which demonstrate that the proposed optimization technique pays off in practice.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Futures of artificial intelligence through technology readiness levels

  • Martínez-Plumed, Fernando|||0000-0003-2902-6477
  • Gómez, Emilia
  • Hernández-Orallo, José
[EN] Artificial Intelligence (AI) offers the potential to transform our lives in radical ways. However, the main unanswered questions about this foreseen transformation are its depth, breadth and timelines. To answer them, not only do we lack the tools to determine what achievements will be attained in the near future, but we even ignore what various technologies in present-day AI are capable of. Many so-called breakthroughs in AI are associated with highly-cited research papers or good performance in some particular benchmarks. However, research breakthroughs do not directly translate into a technology that is ready to use in real-world environments. In this paper, we present a novel exemplar-based methodology to categorise and assess several AI technologies, by mapping them onto Technology Readiness Levels (TRL) (representing their depth in maturity and availability). We first interpret the nine TRLs in the context of AI, and identify several categories in AI to which they can be assigned. We then introduce a generality dimension, which represents increasing layers of breadth of the technology. These two dimensions lead to the new readiness-vs-generality charts, which show that higher TRLs are achievable for low-generality technologies, focusing on narrow or specific abilities, while high TRLs are still out of reach for more general capabilities. We include numerous examples of AI technologies in a variety of fields, and show their readiness-vs-generality charts, serving as exemplars. Finally, we show how the timelines of several AI technology exemplars at different generality layers can help forecast some short-term and mid-term trends for AI., This material is based upon work supported by the EU (FEDER), and the Spanish MINECO under grant RTI2018-094403-B-C3, the Generalitat Valenciana PROMETEO/2019/098. F. Martinez-Plumed acknowledges funding of the AI-Watch project by DG CONNECT and DG JRC of the European Commission. J. Hernandez-Orallo is funded by an Future of Life Institute (FLI) grant RFP2-152.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Twenty Years Beyond the Turing Test: Moving Beyond the Human Judges Too

  • Hernández-Orallo, José|||0000-0001-9746-7632
[EN] In the last 20 years the Turing test has been left further behind by new developments in artificial intelligence. At the same time, however, these developments have revived some key elements of the Turing test: imitation and adversarialness. On the one hand, many generative models, such as generative adversarial networks (GAN), build imitators under an adversarial setting that strongly resembles the Turing test (with the judge being a learnt discriminative model). The term "Turing learning" has been used for this kind of setting. On the other hand, AI benchmarks are suffering an adversarial situation too, with a 'challenge-solve-and-replace' evaluation dynamics whenever human performance is 'imitated'. The particular AI community rushes to replace the old benchmark by a more challenging benchmark, one for which human performance would still be beyond AI. These two phenomena related to the Turing test are sufficiently distinctive, important and general for a detailed analysis. This is the main goal of this paper. After recognising the abyss that appears beyond superhuman performance, we build on Turing learning to identify two different evaluation schemas: Turing testing and adversarial testing. We revisit some of the key questions surrounding the Turing test, such as 'understanding', commonsense reasoning and extracting meaning from the world, and explore how the new testing paradigms should work to unmask the limitations of current and future AI. Finally, we discuss how behavioural similarity metrics could be used to create taxonomies for artificial and natural intelligence. Both testing schemas should complete a transition in which humans should give way to machines-not only as references to be imitated but also as judges-when pursuing and measuring machine intelligence., I appreciate the reviewers' comments, leading to new Sect. 5, among other modifications and insights in the final version. This work was funded by the Future of Life Institute, FLI, under grant RFP2-152, and also supported by the EU (FEDER) and Spanish MINECO under RTI2018-094403B-C32, and Generalitat Valenciana under PROMETEO/2019/098. Figure 1 was kindly generated on purpose by Fernando Martinez-Plumed.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Learning alternative ways of performing a task

  • Nieves, D.
  • Ramírez Quintana, María José|||0000-0002-0559-3568
  • C. Monserrat|||0000-0003-1790-8085
  • Ferri Ramírez, César|||0000-0002-8975-1120
  • Hernández-Orallo, José|||0000-0001-9746-7632
[EN] A common way of learning to perform a task is to observe how it is carried out by experts. However, it is well known that for most tasks there is no unique way to perform them. This is especially noticeable the more complex the task is because factors such as the skill or the know-how of the expert may well affect the way she solves the task. In addition, learning from experts also suffers of having a small set of training examples generally coming from several experts (since experts are usually a limited and ex- pensive resource), being all of them positive examples (i.e. examples that represent successful executions of the task). Traditional machine learning techniques are not useful in such scenarios, as they require extensive training data. Starting from very few executions of the task presented as activity sequences, we introduce a novel inductive approach for learning multiple models, with each one representing an alter- native strategy of performing a task. By an iterative process based on generalisation and specialisation, we learn the underlying patterns that capture the different styles of performing a task exhibited by the examples. We illustrate our approach on two common activity recognition tasks: a surgical skills training task and a cooking domain. We evaluate the inferred models with respect to two metrics that measure how well the models represent the examples and capture the different forms of executing a task showed by the examples. We compare our results with the traditional process mining approach and show that a small set of meaningful examples is enough to obtain patterns that capture the different strategies that are followed to solve the tasks., This work has been partially supported by the EU (FEDER) and the Spanish MINECO under grants TIN2014-61716-EXP (SUPERVASION) and RTI2018-094403-B-C32, and by Generalitat Valenciana under grant PROMETEO/2019/098. David Nieves is also supported by the Spanish MINECO under FPI grant (BES-2016-078863).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Context-sensitive Rewriting

  • Lucas Alba, Salvador|||0000-0001-9923-2108
[EN] The appropriate selection of the arguments of functions that can be evaluated in function calls is often useful to improve efficiency, speed, termination behavior, and so on. This is essential, e.g., in the conditional if - then - else operator. We can specify this by associating a set mu( f) of indices of evaluable arguments to each function symbol f. With mu(if-then-else) = {1}, only the Boolean argument b in calls if b then e else e' is evaluated. In the realm of term rewriting, this is called context-sensitive rewriting. It has been proven useful to improve the termination behavior of rewriting computations while it is still able to compute (or approximate) canonical forms like head-normal forms, (infinite) values, and (infinite) normal forms by requiring a few reasonable conditions. This article provides an overview of basic results to use context-sensitive rewriting in practice., Supported by the EU (FEDER) and projects RTI2018-094403-B-C32, PROMETEO/2019/098, and SP20180225.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Abstract Contract Synthesis and Verification in the Symbolic K Framework

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Villanueva, Alicia|||0000-0003-1090-5009
  • Pardo, Daniel
[EN] In this article, we propose a symbolic technique that can be used for automatically inferring software contracts from programs that are written in a non-trivial fragment of C, called KERNELC, that supports pointer-based structures and heap manipulation. Starting from the semantic definition of KERNELC in the K semantic framework, we enrich the symbolic execution facilities recently provided by K with novel capabilities for contract synthesis that are based on abstract subsumption. Roughly speaking, we define an abstract symbolic technique that axiomatically explains the execution of any (modifier) C function by using other (observer) routines in the same program. We implemented our technique in the automated tool KINDSPEC 2.1, which generates logical axioms that express pre- and post-condition assertions which define the precise input/output behavior of the C routines. Thanks to the integrated support for symbolic execution and deductive verification provided by K, some synthesized axioms that cannot be guaranteed to be correct by construction due to abstraction can finally be verified in our setting with little effort., This work has been partially supported by the EC H2020-EU grant agreement No. 952215 (TAILOR), the EU (FEDER) and the Spanish MCIU under grant RTI2018-094403-B-C32, by Generalitat Valenciana under grant PROMETEO/2019/098.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

The teaching size: computable teachers and learners for universal languages

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

AUTOMAT[R]IX: learning simple matrix pipelines

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

Efficient Safety Enforcement for Maude Programs via Program Specialization in the ÁTAME system

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Sapiña-Sanchis, Julia|||0000-0003-2994-6986
  • Ballis, D.
[EN] Program specialization is mainly recognized as a powerful technique for optimizing software systems. Nonetheless, it can also be productively employed in other application areas. This paper presents an assertion-guided program specialization methodology for efficiently imposing safety properties on software systems. The program specializer takes as input a set A of logical assertions that specifies the expected system behavior plus a software system that is modeled as a Maude program R that may violate some of the assertions in A. The outcome is a safe refinement R of R in which every system computation is a good run of R, i.e., it satisfies the assertions in A. The specialization technique has been fully automated in the ATAME system and ensures that no good run of R is removed from R, while the number of bad runs is reduced to zero. The efficiency and scalability of our technique is empirically demonstrated by means of a thorough experimental evaluation of the ATAME system, which shows fast specialization times and good performance of the computed specializations, even for large assertion sets., This work has been partially supported by the EU (FEDER) and the Spanish Ministry of Science, Innovation and Universities under grant RTI2018-094403-B-C32, and by Generalitat Valenciana ref. PROMETEO/2019/098 and ref. APOSTD/2019/127.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Training Data Scientists Through Project-Based Learning

  • Martínez-Plumed, Fernando|||0000-0003-2902-6477
  • Hernández-Orallo, José|||0000-0001-9746-7632
[EN] The concepts of innovation, creativity, problem solving, effective communication, autonomy and critical thinking are at the core of becoming a good data scientist. Adapting to new technological resources and tools is also an important skill, which also builds on the curious and inquisitive nature associated with data science, and is fuelled by rapidly changing data science ecosystems in industry. In this regard, Project-based learning (PBL) has clear benefits for engaging students in data science courses. However, the exploratory character of data science projects, which do not start with a clear specification of what to do, but some data to analyse, pose some challenges to the application of PBL. Our aim is to improve students' data science learning experiences and outcomes through the use of PBL. In this paper, we share our experiences with PBL and present an assessment rubric that focuses on value, innovation and narrative, which can be used as a scaffolding structure for data science courses. Our analysis of a PBL data science course at MSc level, together with data from student surveys, shows how the methodology and rubric align well with the exploratory nature of data science and the proactive, curious, and inquisitive skills required of data scientists., Thiswork was supported in part by valgrAI, the Norwegian Research Council Grant 329745 Machine Teaching for Explainable AI, the Future of LifeInstitute (FLI), under Grant RFP2-152, the EU (FEDER), and Spanish Grant RTI2018-094403-B-C32 through MCIN/AEI/10.13039/501100011033 and in part by CIPROM/2022/6 through Generalitat Valenciana, EU's Horizon 2020 Research and Innovation Programme under Grant 952215 (TAILOR), U.S. DARPA HR00112120007 (RECoG-AI), and Spanish Grant PID2021-122830OB-C42 (SFERA) through MCIN/AEI/10.13039/501100011033 and "ERDF a Way of Making Europe."
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Can language models automate data wrangling?

  • Jaimovitch-López, Gonzalo
  • Ferri Ramírez, César|||0000-0002-8975-1120
  • Hernández-Orallo, José|||0000-0001-9746-7632
  • Martínez-Plumed, Fernando|||0000-0003-2902-6477
  • Ramírez Quintana, María José|||0000-0002-0559-3568
[EN] The automation of data science and other data manipulation processes depend on the integration and formatting of 'messy' data. Data wrangling is an umbrella term for these tedious and time-consuming tasks. Tasks such as transforming dates, units or names expressed in different formats have been challenging for machine learning because (1) users expect to solve them with short cues or few examples, and (2) the problems depend heavily on domain knowledge. Interestingly, large language models today (1) can infer from very few examples or even a short clue in natural language, and (2) can integrate vast amounts of domain knowledge. It is then an important research question to analyse whether language models are a promising approach for data wrangling, especially as their capabilities continue growing. In this paper we apply different variants of the language model Generative Pre-trained Transformer (GPT) to five batteries covering a wide range of data wrangling problems. We compare the effect of prompts and few-shot regimes on their results and how they compare with specialised data wrangling systems and other tools. Our major finding is that they appear as a powerful tool for a wide range of data wrangling tasks. We provide some guidelines about how they can be integrated into data processing pipelines, provided the users can take advantage of their flexibility and the diversity of tasks to be addressed. However, reliability is still an important issue to overcome., Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. This work was funded by the Future of Life Institute, FLI, under grant RFP2-152, the MIT-Spain - INDITEX Sustainability Seed Fund under project COST-OMIZE, the EU (FEDER) and Spanish MINECO under RTI2018-094403-B-C32 and PID2021-122830OB-C42, Generalitat Valenciana under PROMETEO/2019/098 and INNEST/2021/317, EU's Horizon 2020 research and innovation programme under grant agreement No. 952215 (TAILOR) and US DARPA HR00112120007 ReCOG-AI. AcknowledgementsWe thank Lidia Contreras for her help with the Data Wrangling Dataset Repository. We thank the anonymous reviewers from ECMLPKDD Workshop on Automating Data Science (ADS2021) and the anonymous reviewers of this special issue for their comments.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

CRISP-DM Twenty Years Later: From Data Mining Processes to Data Science Trajectories

  • 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
  • Contreras-Ochando, Lidia
  • Kull, Meelis
  • Lachiche, Nicolas
  • Flach, Peter
[EN] CRISP-DM (CRoss-Industry Standard Process for Data Mining) has its origins in the second half of the nineties and is thus about two decades old. According to many surveys and user polls it is still thede factostandard for developing data mining and knowledge discovery projects. However, undoubtedly the field has moved on considerably in twenty years, with data science now the leading term being favoured over data mining. In this paper we investigate whether, and in what contexts, CRISP-DM is still fit for purpose for data science projects. We argue that if the project is goal-directed and process-driven the process model view still largely holds. On the other hand, when data science projects become more exploratory the paths that the project can take become more varied, and a more flexible model is called for. We suggest what the outlines of such a trajectory-based model might look like and how it can be used to categorise data science projects (goal-directed, exploratory or data management). We examine seven real-life exemplars where exploratory activities play an important role and compare them against 51 use cases extracted from the NIST Big Data Public Working Group. We anticipate this categorisation can help project planning in terms of time and cost characteristics., We thank the anonymous reviewers for their comments, which motivated the analysis in Section 5. This material is based upon work supported by the EU (FEDER), and the Spanish MINECO under Grant RTI2018-094403-B-C3, the Generalitat Valenciana PROMETEO/2019/098. F. MartinezPlumed was also supported by INCIBE (Ayudas para la excelencia de los equipos de investigacion avanzada en ciberseguridad), the European Commission (JRC) HUMAINT project (CT-EX2018D335821-101), and UPV (PAID-06-18). J. H-Orallo is also funded by an FLI grant RFP2-152.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

A Partial Evaluation Framework for Order-sorted Equational Programs modulo Axioms

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Escobar Román, Santiago|||0000-0002-3550-4781
  • Cuenca-Ortega, Angel Eduardo
  • Meseguer, José
[EN] Partial evaluation is a powerful and general program optimization technique with many successful applications. Existing PE schemes do not apply to expressive rule-based languages like Maude, CafeOBJ, OBJ, ASF+SDF, and ELAN, which support: 1) rich type structures with sorts, subsorts, and overloading; and 2) equational rewriting modulo various combinations of axioms such as associativity, commutativity, and identity. In this paper, we develop the new foundations needed and illustrate the key concepts by showing how they apply to partial evaluation of expressive programs written in Maude. Our partial evaluation scheme is based on an automatic unfolding algorithm that computes term variants and relies on high-performance order-sorted equational least general generalization and order-sorted equational homeomorphic embedding algorithms for ensuring termination. We show that our partial evaluation technique is sound and complete for convergent rewrite theories that may contain various combinations of associativity, commutativity, and/or identity axioms for different binary operators. We demonstrate the effectiveness of Maude's automatic partial evaluator, Victoria, on several examples where it shows significant speed-ups. (C) 2019 Elsevier Inc. All rights reserved., This work has been partially supported by the EU (FEDER) and the Spanish MCIU under grant RTI2018-094403-B-C32, by Generalitat Valenciana under grant PROMETEO/2019/098, and by NRL under contract number N00173-17-1-G002. Angel Cuenca-Ortega has been supported by the SENESCYT, Ecuador (scholarship program 2013).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Order-sorted Homeomorphic Embedding modulo Combinations of Associativity and/or Commutativity Axioms

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Escobar Román, Santiago|||0000-0002-3550-4781
  • Cuenca-Ortega, Angel
  • Meseguer, José
[EN] The Homeomorphic Embedding relation has been amply used for defining termination criteria of symbolic methods for program analysis, transformation, and verification. However, homeomorphic embedding has never been investigated in the context of order-sorted rewrite theories that support symbolic execution methods modulo equational axioms. This paper generalizes the symbolic homeomorphic embedding relation to order-sorted rewrite theories that may contain various combinations of associativity and/or commutativity axioms for different binary operators. We systematically measure the performance of different, increasingly efficient formulations of the homeomorphic embedding relation modulo axioms that we implement in Maude. Our experimental results show that the most efficient version indeed pays off in practice., M. Alpuente and S. Escobar have been partially supported by the EU (FEDER) and the Spanish MCIU under grant RTI2018-094403-B-C32, by the Spanish Generalitat Valenciana under grant PROMETEO/2019/098, and by the European Union's Horizon 2020 research and innovation programme under grant agreement No. 952215 (TAILOR). J. Meseguer has been supported by NRL under contract number N00173-17-1-G002. A. Cuenca-Ortega has been supported by the SENESCYT, Ecuador (scholarship program 2013).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Derivational Complexity and Context-Sensitive Rewriting

  • Lucas Alba, Salvador|||0000-0001-9923-2108
[EN] Context-sensitive rewriting is a restriction of rewriting where reduction steps are allowed on specific arguments mu(f) subset of {1, ..., k} of k-ary function symbols f only. Terms which cannot be further rewritten in this way are called mu-normal forms. For left-linear term rewriting systems (TRSs), the so-called normalization via mu-normalization procedure provides a systematic way to obtain normal forms by the stepwise computation and combination of intermediate mu-normal forms. In this paper, we show how to obtain bounds on the derivational complexity of computations using this procedure by using bounds on the derivational complexity of context-sensitive rewriting. Two main applications are envisaged: Normalization via mu-normalization can be used with non-terminating TRSs where the procedure still terminates; on the other hand, it can be used to improve on bounds of derivational complexity of terminating TRSs as it discards many rewritings., Partially supported by the EU (FEDER), and projects RTI2018-094403-B-C32 and PROMETEO/2019/098.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Applications and extensions of context-sensitive rewriting

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

Imposing Assertions in Maude via Program Transformation

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

General intelligence disentangled via a generality metric for natural and artificial intelligence

  • Hernández-Orallo, José|||0000-0001-9746-7632
  • Martínez-Plumed, Fernando|||0000-0003-2902-6477
  • Loe, Bao Sheng
  • Cheke, Lucy
  • Heigeartaigh, Sean O.
[EN] Success in all sorts of situations is the most classical interpretation of general intelligence. Under limited resources, however, the capability of an agent must necessarily be limited too, and generality needs to be understood as comprehensive performance up to a level of difficulty. The degree of generality then refers to the way an agent's capability is distributed as a function of task difficulty. This dissects the notion of general intelligence into two non-populational measures, generality and capability, which we apply to individuals and groups of humans, other animals and AI systems, on several cognitive and perceptual tests. Our results indicate that generality and capability can decouple at the individual level: very specialised agents can show high capability and vice versa. The metrics also decouple at the population level, and we rarely see diminishing returns in generality for those groups of high capability. We relate the individual measure of generality to traditional notions of general intelligence and cognitive efficiency in humans, collectives, non-human animals and machines. The choice of the difficulty function now plays a prominent role in this new conception of generality, which brings a quantitative tool for shedding light on long-standing questions about the evolution of general intelligence and the evaluation of progress in Artificial General Intelligence., We are grateful to Jim DiCarlo and his lab (http://dicarlolab.mit.edu/, MIT), Judith Burkart, Laura Damerius and Carel van Schaik (Universitat Zurich), and Katherine Bruce and Mark Galizio (UNC Wilmington), for their data and the very helpful discussions. We thank David Stillwell for suggesting the relation between person-fit metrics and an early version of generality, and Heinrich Peters for pointing out Guttman's model. JHO has been partially supported by the EU (FEDER) and Spanish MINECO grant RTI2018-094403-B-C32 funded by MCIN/AEI/10.13039/501100011033 and by "ERDF A way of making Europe", Generalitat Valenciana under grant PROMETEO/2019/098 and EU's Horizon 2020 research and innovation programme under grant agreement No. 952215 (TAILOR). JHO and SOH are funded by the Future of Life Institute, FLI, under grant RFP2-152. JHO and LC are funded by US DARPA HR00112120007 (RECoG-AI). LC and SOH are funded by the Leverhulme Trust through a grant for the Leverhulme Centre for the Future of Intelligence. FMP is funded by the AI-Watch and HUMAINT projects by DG CONNECT and DG JRC of the European Commission. All authors declare no competing interests. We thank John Burden, Richard Evans and the anonymous reviewers for their insightful comments and corrections. Code and data are available for reproducibility at http://github.com/jorallo/gener ality as explained in G.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

The impact of sociality regimes on heterogeneous cooperative-competitive multi-agent reinforcement learning: a study with the predator-prey game

  • Zhao, Yue
  • Hernández-Orallo, José|||0000-0001-9746-7632
[EN] The performance in multi-agent reinforcement learning (MARL) scenarios has usually been analysed in homogeneous teams with a few choices for the sociality regime (selfish, egalitarian, or altruistic). In this paper we analyse both homogeneous and heterogeneous teams in a variation of sociality regimes in the predator-prey game, using a novel normalisation of the weights so that the sum of all rewards is independent of the sociality regime. We find that the selfish regime is advantageous for both predator and prey teams, and for both homogeneous and heterogeneous teams. In particular, rewards are about 100% higher for the predator team when switching from the egalitarian to selfish regime and more than 400% higher from the altruistic regime. For the prey, the increase is around 40% and 100% respectively. The results are similar for homogeneous and heterogeneous situations. The takeaway message is that any study of homogeneous and heterogeneous cooperative-competitive multi-agent reinforcement learning teams should also take into account the sociality regimes before making conclusions on the preference of any algorithm., This work was funded by the EU (FEDER) and Spanish grant RTI2018-094403-B-C32 funded by MCIN/AEI/10.13039/501100011033 and by 'ERDF A way of making Europe', Generalitat Valenciana under CIPROM/2022/6 (FASSLOW) and IDIFEDER/2021/05 (CLUSTERIA), EU's Horizon 2020 research and innovation programme under grant agreement No. 952215 (TAILOR) and Spanish grant PID2021-122830OB-C42 (SFERA) funded by MCIN/AEI/10.13039/501100011033 and 'ERDF A way of making Europe' and China Scholarship Council (CSC) scholarship (No. 202006290201).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Symbolic Specialization of Rewriting Logic Theories with Presto

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Escobar Román, Santiago|||0000-0002-3550-4781
  • Sapiña-Sanchis, Julia|||0000-0003-2994-6986
  • Ballis, Demis
[EN] This paper introduces Presto, a symbolic partial evaluator for Maude's rewriting logic theories that can improve system analysis and verification. In Presto, the automated optimization of a conditional rewrite theory R (whose rules define the concurrent transitions of a system) is achieved by partially evaluating, with respect to the rules of R, an underlying, companion equational logic theory E that specifies the algebraic structure of the system states of R. This can be particularly useful for specializing an overly general equational theory E whose operators may obey complex combinations of associativity, commutativity, and/or identity axioms, when being plugged into a host rewrite theory R as happens, for instance, in protocol analysis, where sophisticated equational theories for cryptography are used. Presto implements different unfolding operators that are based on folding variant narrowing (the symbolic engine of Maude's equational theories). When combined with an appropriate abstraction algorithm, they allow the specialization to be adapted to the theory termination behavior and bring significant improvement while ensuring strong correctness and termination of the specialization. We demonstrate the effectiveness of Presto in several examples of protocol analysis where it achieves a significant speed-up. Actually, the transformation provided by Presto may cut down an infinite folding variant narrowing space to a finite one, and moreover, some of the costly algebraic axioms and rule conditions may be eliminated as well. As far as we know, this is the first partial evaluator for Maude that respects the semantics of functional, logic, concurrent, and object-oriented computations., This research was partially supported by TAILOR, a project funded by EU Horizon 2020 research and innovation programme under GA No 952215, grant RTI2018-094403-B-C32 funded by MCIN/AEI/10.13039/501100011033 and by "ERDF A way of making Europe", and by Generalitat Valenciana under grant PROMETEO/2019/098. Julia Sapiña has been supported by the Generalitat Valenciana APOSTD/2019/127 grant.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Order-sorted Equational Generalization Algorithm Revisited

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Escobar Román, Santiago|||0000-0002-3550-4781
  • Sapiña-Sanchis, Julia|||0000-0003-2994-6986
  • Meseguer, José
[EN] Generalization, also called anti-unification, is the dual of unification. A generalizer of two terms t and t' is a term t '' of which t and t' are substitution instances. The dual of most general equational unifiers is that of least general equational generalizers, i.e., most specific anti-instances modulo equations. In a previous work, we extended the classical untyped generalization algorithm to: (1) an order-sorted typed setting with sorts, subsorts, and subtype polymorphism; (2) 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 (3) the combination of both, which results in a modular, order-sorted equational generalization algorithm. However, Cerna and Kutsia showed that our algorithm is generally incomplete for the case of identity axioms and a counterexample was given. Furthermore, they proved that, in theories with two identity elements or more, generalization with identity axioms is generally nullary, yet it is finitary for both the linear and one-unital fragments, i.e., either solutions with repeated variables are disregarded or the considered theories are restricted to having just one function symbol with an identity or unit element. In this work, we show how we can easily extend our original inference system to cope with the non-linear fragment and identify a more general class than one-unit theories where generalization with identity axioms is finitary.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Using Well-Founded Relations for Proving Operational Termination

  • Lucas Alba, Salvador|||0000-0001-9923-2108
[EN] In this paper, we study operational termination, a proof theoretical notion for capturing the termination behavior of computational systems. We prove that operational termination can be characterized at different levels by means of well- founded relations on specific formulas which can be obtained from the considered system. We show how to obtain such well-founded relations from logical models which can be automatically generated using existing tools., Partially supported by the EU (FEDER), Projects TIN2015-69175-C4-1-R, and GV PROMETEOII/2015/013.