Pasar al contenido principal

Resultados relacionados

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

Repositorio Digital de la UPF
Publicación Artículo científico (JournalArticle)

High evolutionary turnover of satellite families in Caenorhabditis

  • Subirana, Juan A.
  • Albà Soler, Mar
  • Messeguer, Xavier
Background. The high density of tandem repeat sequences (satellites) in nematode genomes and the availability of genome sequences from several species in the group offer a unique opportunity to better understand the evolutionary dynamics and the functional role of these sequences. We take advantage of the previously developed SATFIND program to study the satellites in four Caenorhabditis species and investigate these questions./nMethods. The identification and comparison of satellites is carried out in three steps. First we find all the satellites present in each species with the SATFIND program. Each satellite is defined by its length, number of repeats, and repeat sequence. Only satellites with at least ten repeats are considered. In the second step we build satellite families with a newly developed alignment program. Satellite families are defined by a consensus sequence and the number of satellites in the family. Finally we compare the consensus sequence of satellite families in different species./nResults. We give a catalog of individual satellites in each species. We have also identified satellite families with a related sequence and compare them in different species. We analyze the turnover of satellites: they increased in size through duplications of fragments of 100-300 bases. It appears that in many cases they have undergone an explosive expansion. In C. elegans we have identified a subset of large satellites that have strong affinity for the centromere protein CENP-A. We have also compared our results with those obtained from other species, including one nematode and three mammals./nConclusions. Most satellite families found in Caenorhabditis are species-specific; in particular those with long repeats. A subset of these satellites may facilitate the formation of kinetochores in mitosis. Other satellite families in C. elegans are either related to Helitron transposons or to meiotic pairing centers., We are thankful to Dr. Lourdes Campos for valuable suggestions. Also to Messrs. W. Blevins and F. Acosta-Reyes for help in the preparation of the manuscript and figures. This work was funded by Ministerio de Economía y Competitividad (TIN2010-21062-C02-01, TIN2013-45732-C4-3-P, BFU2012-36820 and 2009–10380) with additional Feder funds.
Repositorio Digital de la UPF
Publicación Artículo científico (JournalArticle)

Long non-coding RNAs as a source of new peptides

  • Ruiz Orera, Jorge, 1988-
  • Messeguer, Xavier
  • Subirana, Juan A.
  • Albà Soler, Mar
Deep transcriptome sequencing has revealed the existence of many transcripts that lack long or conserved open reading frames (ORFs) and which have been termed long non-coding RNAs (lncRNAs). The vast majority of lncRNAs are lineage-specific and do not yet have a known function. In this study, we test the hypothesis that they may act as a repository for the synthesis of new peptides. We find that a large fraction of the lncRNAs expressed in cells from six different species is associated with ribosomes. The patterns of ribosome protection are consistent with the translation of short peptides. lncRNAs show similar coding potential and sequence constraints than evolutionary young protein coding sequences, indicating that they play an important role in de novo protein evolution, This work was funded by Ministerio de Economía y Competitividad (BFU2012-36820 and TIN2013-45732-C4-3-P) and Fundació ICREA (MMA)
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Abstract Analysis of Universal Properties for tccp

  • Comini, Marco
  • Gallardo Melgarejo, Maria del Mar
  • Titolo, Laura
  • Villanueva, Alicia|||0000-0003-1090-5009
[EN] The Timed Concurrent Constraint Language (tccp) is a time extension of the concurrent constraint paradigm of Saraswat. tccp was defined to model reactive systems, where infinite behaviors arise naturally. In previous works, a semantic framework and abstract diagnosis method for the language has been defined. On the basis of that semantic framework, this paper proposes an abstract semantics that, together with a widening operator, is suitable for the definition of different analyses for tccp programs. The abstract semantics is correct and can be represented as a finite graph where each node represents a hypothetical computational step of the program containing approximated information for the variables. The widening operator allows us to guarantee the convergence of the abstract fixpoint computation., This work has been supported by the Andalusian Excellence Project P11-TIC7659. This work has been partially supported by the EU (FEDER) and the Spanish MINECO under grant TIN 2013-45732-C4-1-P (DAMAS) 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)

Binarised regression tasks: methods and evaluation metrics

  • Hernández-Orallo, José|||0000-0001-9746-7632
  • Ferri Ramírez, César|||0000-0002-8975-1120
  • Ramírez Quintana, María José|||0000-0002-0559-3568
  • Lachiche, Nicolas
  • Martínez Usó, Adolfo
Some supervised tasks are presented with a numerical output but decisions have to be made in a discrete, binarised, way, according to a particular cutoff. This binarised regression task is a very common situation that requires its own analysis, different from regression and classification—and ordinal regression. We first investigate the application cases in terms of the information about the distribution and range of the cutoffs and distinguish six possible scenarios, some of which are more common than others. Next, we study two basic approaches: the retraining approach, which discretises the training set whenever the cutoff is available and learns a new classifier from it, and the reframing approach, which learns a regression model and sets the cutoff when this is available during deployment. In order to assess the binarised regression task, we introduce context plots featuring error against cutoff. Two special cases are of interest, the UCEUCE and OCEOCE curves, showing that the area under the former is the mean absolute error and the latter is a new metric that is in between a ranking measure and a residual-based measure. A comprehensive evaluation of the retraining and reframing approaches is performed using a repository of binarised regression problems created on purpose, concluding that no method is clearly better than the other, except when the size of the training data is small., We thank the anonymous reviewers for their comments, which have helped to improve this paper significantly. We thank Peter Flach and Meelis Kull for their insightful comments and very useful suggestions. This work was supported by the Spanish MINECO under Grant TIN 2013-45732-C4-1-P and by Generalitat Valenciana PROMETEOII2015/013. This research has been developed within 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) and the Agence Nationale pour la Recherche in France (ANR-12-CHRI-0005-03).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Debugging Maude programs via runtime assertion checking and trace slicing

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Sapiña-Sanchis, Julia|||0000-0003-2994-6986
  • Ballis, Demis
  • Frechina, F.
In this paper we propose a dynamic analysis methodology for improving the diagnosis of erroneous Maude programs. The key idea is to combine runtime checking and dynamic trace slicing for automatically catching errors at runtime while reducing the size and complexity of the erroneous traces to be analyzed (i.e., those leading to states failing to satisfy some of the assertions). First, we formalize a technique that is aimed at automatically detecting deviations of the program behavior (symptoms) with respect to two types of user-defined assertions: functional assertions and system assertions. The proposed dynamic checking is provably sound in the sense that all errors flagged are definitely violations of the specifications. Then, upon eventual assertion violations we generate accurate trace slices that help identify the cause of the error. Our methodology is based on (i) a logical notation for specifying assertions that are imposed on execution runs; (ii) a runtime checking technique that dynamically tests the assertions; and (iii) a mechanism based on (equational) least general generalization that automatically derives accurate criteria for slicing from falsified assertions. Finally, we report on an implementation of the proposed technique in the assertion-based, dynamic analyzer ABETS and show how the forward and backward tracking of asserted program properties leads to a thorough trace analysis algorithm that can be used for program diagnosis and debugging. © 2016 Elsevier Inc. All rights reserved., This work has been partially supported by the EU (FEDER) and the Spanish MINECO under grants TIN2015-69175-C4-1-R and TIN2013-45732-C4-1-P, and by Generalitat Valenciana Ref. PROMETEOII/2015/013. F. Frechina was supported by FPU-ME grant AP2010-5681, and J. Sapiña was supported by FPI-UPV grant SP2013-0083 and mobility grant VIIT-3946.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Synthesis of models for order-sorted first-order theories using linear algebra and constraint solving

  • Lucas Alba, Salvador|||0000-0001-9923-2108
[EN] Recent developments in termination analysis for declarative programs emphasize the use of appropriate models for the logical theory representing the program at stake as a generic approach to prove termination of declarative programs. In this setting, Order-Sorted First-Order Logic provides a powerful framework to represent declarative programs. It also provides a target logic to obtain models for other logics via transformations. We investigate the automatic generation of numerical models for order-sorted first-order logics and its use in program analysis, in particular in termination analysis of declarative programs. We use convex domains to give domains to the different sorts of an order-sorted signature; we interpret the ranked symbols of sorted signatures by means of appropriately adapted convex matrix interpretations. Such numerical interpretations permit the use of existing algorithms and tools from linear algebra and arithmetic constraint solving to synthesize the models., Partially supported by the EU (FEDER), Spanish MINECO TIN 2013-45732-C4-1-P and GV PROMETEOII/2015/013
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

A computational analysis of general intelligence tests for evaluating cognitive development

  • 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
[EN] The progression in several cognitive tests for the same subjects at different ages provides valuable information about their cognitive development. One question that has caught recent interest is whether the same approach can be used to assess the cognitive development of artificial systems. In particular, can we assess whether the fluid or crystallised intelligence of an artificial cognitive system is changing during its cognitive development as a result of acquiring more concepts? In this paper, we address several IQ tests problems (odd-one-out problems, Raven s Progressive Matrices and Thurstone s letter series) with a general learning system that is not particularly designed on purpose to solve intelligence tests. The goal is to better understand the role of the basic cognitive perational constructs (such as identity, difference, order, counting, logic, etc.) that are needed to solve these intelligence test problems and serve as a proof-of-concept for evaluation in other developmental problems. From here, we gain some insights into the characteristics and usefulness of these tests and how careful we need to be when applying human test problems to assess the abilities and cognitive development of robots and other artificial cognitive systems., This work has been partially supported by the EU (FEDER) and the Spanish MINECO under grants TIN 2015-69175-C4-1-R and TIN 2013-45732-C4-1-P, and by Generalitat Valenciana under grant PROMETEOII/2015/013.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Evaluation in artificial intelligence: From task-oriented to ability-oriented measurement

  • Hernández-Orallo, José|||0000-0001-9746-7632
The evaluation of artificial intelligence systems and components is crucial for the progress of the discipline. In this paper we describe and critically assess the different ways AI systems are evaluated, and the role of components and techniques in these systems. We first focus on the traditional task-oriented evaluation approach. We identify three kinds of evaluation: human discrimination, problem benchmarks and peer confrontation. We describe some of the limitations of the many evaluation schemes and competitions in these three categories, and follow the progression of some of these tests. We then focus on a less customary (and challenging) ability-oriented evaluation approach, where a system is characterised by its (cognitive) abilities, rather than by the tasks it is designed to solve. We discuss several possibilities: the adaptation of cognitive tests used for humans and animals, the development of tests derived from algorithmic information theory or more integrated approaches under the perspective of universal psychometrics. We analyse some evaluation tests from AI that are better positioned for an ability-oriented evaluation and discuss how their problems and limitations can possibly be addressed with some of the tools and ideas that appear within the paper. Finally, we enumerate a series of lessons learnt and generic guidelines to be used when an AI evaluation scheme is under consideration., I thank the organisers of the AEPIA Summer School On Artificial Intelligence, held in September 2014, for giving me the opportunity to give a lecture on 'AI Evaluation'. This paper was born out of and evolved through that lecture. The information about many benchmarks and competitions discussed in this paper have been contrasted with information from and discussions with many people: M. Bedia, A. Cangelosi, C. Dimitrakakis, I. GarcIa-Varea, Katja Hofmann, W. Langdon, E. Messina, S. Mueller, M. Siebers and C. Soares. Figure 4 is courtesy of F. Martinez-Plumed. Finally, I thank the anonymous reviewers, whose comments have helped to significantly improve the balance and coverage of the paper. This work has been partially supported by the EU (FEDER) and the Spanish MINECO under Grants TIN 2013-45732-C4-1-P, TIN 2015-69175-C4-1-R and by Generalitat Valenciana PROMETEOII2015/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)

Constrained narrowing for conditional equational theories modulo axioms

  • Cholewa, Andrew
  • Meseguer, Jose
  • Escobar Román, Santiago|||0000-0002-3550-4781
For an unconditional equational theory (Sigma, E) whose oriented equations (E) over arrow are confluent and terminating, narrowing provides an E-unification algorithm. This has been generalized by various authors in two directions: (i) by considering unconditional equational theories (Sigma, E boolean OR B) where the (E) over arrow are confluent, terminating and coherent modulo axioms B, and (ii) by considering conditional equational theories. Narrowing for a conditional theory (Sigma, E boolean OR B) has also been studied, but much less and with various restrictions. In this paper we extend these prior results by allowing conditional equations with extra variables in their conditions, provided the corresponding rewrite rules (E) over arrow are confluent, strictly coherent, operationally terminating modulo B and satisfy a natural determinism condition allowing incremental computation of matching substitutions for their extra variables. We also generalize the type structure of the types and operations in Sigma to be order-sorted. The narrowing method we propose, called constrained narrowing, treats conditions as constraints whose solution is postponed. This can greatly reduce the search space of narrowing and allows notions such as constrained variant and constrained unifier that can cover symbolically possibly infinite sets of actual variants and unifiers. It also supports a hierarchical method of solving constraints. We give an inference system for hierarchical constrained narrowing modulo B and prove its soundness and completeness. (C) 2015 Elsevier B.V. All rights reserved., We thank the anonymous referees for their constructive criticism and their very detailed and helpful suggestions for improving an earlier version of this work. We also thank Luis Aguirre for kindly giving us additional suggestions to improve the text. This work has been partially supported by NSF Grant CNS 13-19109 and by the EU (FEDER) and the Spanish MINECO under grant 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)

Knowledge acquisition with forgetting: an incremental and developmental setting

  • 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
Identifying the balance between remembering and forgetting is the key to abstraction in the human brain and, therefore, the creation of memories and knowledge. We present an incremental, lifelong view of knowledge acquisition which tries to improve task after task by determining what to keep, consolidate and forget, overcoming the stability-plasticity dilemma. Our framework can combine any rule-based inductive engine (which learns new rules) with a deductive engine (which derives a coverage graph for all rules) and integrates them into a lifelong learner. We rate rules by introducing several metrics through the first adaptation, to our knowledge, of the Minimum Message Length (MML) principle to a coverage graph, a hierarchical assessment structure which handles evidence and rules in a unified way. The metrics are used to forget some of the worst rules and also to consolidate those selected rules that are promoted to the knowledge base. This mechanism is also mirrored by a demotion system. We evaluate the framework with a series of tasks in a chess rule learning domain., This work has been partially supported by the EU (FEDER) and the Spanish MINECO (grant TIN 2013-45732-C4-1-P and FPI-ME grant BES-2011-045099), by Generalitat Valenciana (PROMETEO2011/052) 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 Artículo científico (JournalArticle)

A program analysis framework for tccp based on abstract interpretation

  • Comini, Marco
  • Gallardo, Maria-del-Mar
  • Titolo, Laura
  • Villanueva, Alicia|||0000-0003-1090-5009
[EN] The timed concurrent constraint language (tccp) is a timed extension of the concurrent constraint paradigm. tccp was defined to model reactive systems, where infinite behaviors arise naturally. In previous works, a semantic framework and abstract diagnosis method for the language have been defined. On the basis of that semantic framework, this paper proposes an abstract semantics that, together with a widening operator, is suitable for the definition of different analyses for tccp programs. The abstract semantics is correct and can be represented as a finite graph where each node represents a hypothetical (abstract) computational step of the program. The widening operator allows us to guarantee the convergence of the abstract fixpoint computation., This author has been supported by the Andalusian Excellence Project P11-TIC-7659. This work has been partially supported by the EU (FEDER) and the Spanish MINECO under grants TIN 2015-69175-C4-1-R 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)

Automatic Inference of Specifications in the K Framework

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Villanueva, Alicia|||0000-0003-1090-5009
  • Pardo Pont, Daniel
[EN] Despite its many unquestionable benefits, formal specifications are not widely used in industrial software development. In order to reduce the time and effort required to write formal specifications, in this paper we propose a technique for automatically discovering specifications from real code. The proposed methodology relies on the symbolic execution capabilities recently provided by the K framework that we exploit to automatically infer formal specifications from programs that are written in a non–trivial fragment of C, called KERNELC. Roughly speaking, our symbolic analysis of KERNELC programs explains the execution of a (modifier) function by using other (observer) routines in the program. We implemented our technique in the automated tool KINDSPEC 2.0, which generates axioms that describe the precise input/output behavior of C routines that handle pointerbased structures (i.e., result values and state change). We describe the implementation of our system and discuss the differences w.r.t. our previous work on inferring specifications from C code., This work has been partially supported by the EU (FEDER) and Spanish MINECO under grants TIN2015-69175-C4-1-R and TIN2013-45732-C4-1-P, and by Generalitat Valenciana ref. PROMETEOII/2015/013.
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)

Dependency pairs for proving termination properties of conditional term rewriting systems

  • Lucas Alba, Salvador|||0000-0001-9923-2108
  • Meseguer, José
[EN] The notion of operational termination provides a logic-based definition of termination of computational systems as the absence of infinite inferences in the computational logic describing the operational semantics of the system. For Conditional Term Rewriting Systems we show that operational termination is characterized as the conjunction of two termination properties. One of them is traditionally called termination and corresponds to the absence of infinite sequences of rewriting steps (a horizontal dimension). The other property, that we call V-termination, concerns the absence of infinitely many attempts to launch the subsidiary processes that are required to perform a single rewriting step (a vertical dimension). We introduce appropriate notions of dependency pairs to characterize termination, V-termination, and operational termination of Conditional Term Rewriting Systems. This can be used to obtain a powerful and more expressive framework for proving termination properties of Conditional Term Rewriting Systems., Partially supported by the EU (FEDER), Spanish MINECO projects TIN 2013-45732-C4-1-P and TIN2015-69175-C4-1-R, GV project PROMETEOII/2015/013, and NSF grant CNS 13-19109. Salvador Lucas' research was partly developed during a sabbatical year at UIUC
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Inferring Specifications in the K Framework

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Villanueva, Alicia|||0000-0003-1090-5009
  • Pardo Pont, Daniel
[EN] Despite its many unquestionable benefits, formal specifications are not widely used in industrial software development. In order to reduce the time and effort required to write formal specifications, in this paper we propose a technique for automatically discovering specifications from real code. The proposed methodology relies on the symbolic execution capabilities recently provided by the K framework that we exploit to automatically infer formal specifications from programs that are written in a non trivial fragment of C, called KERNELC. Roughly speaking, our symbolic analysis of KERNELC programs explains the execution of a (modifier) function by using other (observer) routines in the program. We implemented our technique in the automated tool KINDSPEC 2.0, 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). We describe the implementation of our system and discuss the differences w.r.t. our previous work on inferring specifications from C code., This work has been partially supported by the EU (FEDER) and the Spanish MINECO ref. TIN2013-45732-C4 (DAMAS), and by Generalitat Valenciana ref. PROMETEOII/2015/013. D. Pardo is supported by FPU-ME grant FPU14/01830.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Termination of canonical context-sensitive rewriting and productivity of rewrite systems

  • Lucas Alba, Salvador|||0000-0001-9923-2108
[EN] Termination of programs, i.e., the absence of infinite computations, ensures the existence of normal forms for all initial expressions, thus providing an essential ingredient for the definition of a normalization semantics for functional programs. In lazy functional languages, though, infinite data structures are often delivered as the outcome of computations. For instance, the list of all prime numbers can be returned as a neverending stream of numerical expressions or data structures. If such streams are allowed, requiring termination is hopeless. In this setting, the notion of productivity can be used to provide an account of computations with infinite data structures, as it "captures the idea of computability, of progress of infinite-list programs" (B.A. Sijtsma, On the Productivity of Recursive List Definitions, ACM Transactions on Programming Languages and Systems 11(4):633-649, 1989). However, in the realm of Term Rewriting Systems, which can be seen as (first-order, untyped, unconditional) functional programs, termination of Context-Sensitive Rewriting (CSR) has been showed equivalent to productivity of rewrite systems through appropriate transformations. In this way, tools for proving termination of CSR can be used to prove productivity. In term rewriting, CSR is the restriction of rewriting that arises when reductions are allowed on selected arguments of function symbols only. In this paper we show that well-known results about the computational power of CSR are useful to better understand the existing connections between productivity of rewrite systems and termination of CSR, and also to obtain more powerful techniques to prove productivity of rewrite systems., Partially supported by the EU (FEDER), Spanish MINECO TIN 2013-45732-C4-1-P, and GV PROMETEOII/2015/013.
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 Artículo científico (JournalArticle)

Use of Logical Models for Proving Operational Termination in General Logics

  • Lucas Alba, Salvador|||0000-0001-9923-2108
[EN] A declarative programming language is based on some logic L and its operational semantics is given by a proof calculus which is often presented in a natural deduction style by means of inference rules. Declarative programs are theories S of L and executing a program is proving goals ϕ in the inference system I(S) associated to S as a particulariza-tion of the inference system of the logic. The usual soundness assumption for L implies that every model A of S also satisfies ϕ. In this setting, the operational termination of a declarative program is quite naturally defined as the absence of infinite proof trees in the inference system I(S). Proving operational termination of declarative programs often involves two main ingredients: (i) the generation of logical models A to abstract the program execution (i.e., the provability of specific goals in I(S)), and (ii) the use of well-founded relations to guarantee the absence of infinite branches in proof trees and hence of infinite proof trees, possibly taking into account the information about provability encoded by A. In this paper we show how to deal with (i) and (ii) in a uniform way. The main point is the synthesis of logical models where well-foundedness is a side requirement for some specific predicate symbols., Partially supported by the EU (FEDER), Spanish MINECO TIN 2013-45732-C4-1-P and TIN2015-69175-C4-1-R, and GV PROMETEOII/2015/013.
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Adding laziness in BnB-ADOPT+

  • Lee, Jimmy
  • Meseguer, Pedro
  • Su, Wen
In distributed constraint optimization, agents executing BnB-ADOPT+ react eagerly to cost changes: they send non-redundant COST messages to their parents as soon as they receive new messages. We have observed that a lazier reaction (not sending COST messages until a condition is met) substantially decrements the number of messages sent and causes only a small variation in ENCCCs. This approach combines nicely with soft arc consistency maintenance during search. We provide experimental evidence of the benefits of this approach on several benchmarks., This research has been supported by the following grants: CUHK413808, CUHK413710 and CUHK413713 from the Research Grants Council of Hong Kong SAR, the CSIC / RGC Joint Research Scheme grants S-HK003/12 and 2011HK0017, TIN2013-45732-C4-4-P from Spanish MINECO, and Generalitat de Catalunya SGR- 2014-118, Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

The computability path ordering

  • Blanqui, Frédéric
  • Jouannaud, Jean Pierre
  • Rubio Gimeno, Alberto|||0000-0002-0501-9830
This paper aims at carrying out termination proofs for simply typed higher-order calculi automatically by using ordering comparisons. To this end, we introduce the computability path ordering (CPO), a recursive relation on terms obtained by lifting a precedence on function symbols. A first version, core CPO, is essentially obtained from the higher-order recursive path ordering (HORPO) by eliminating type checks from some recursive calls and by incorporating the treatment of bound variables as in the com-putability closure. The well-foundedness proof shows that core CPO captures the essence of computability arguments ^#224, la Tait and Girard, therefore explaining its name. We further show that no further type check can be eliminated from its recursive calls without loosing well-foundedness, but for one for which we found no counterexample yet. Two extensions of core CPO are then introduced which allow one to consider: the first, higher-order inductive types; the second, a precedence in which some function symbols are smaller than application and abstraction., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

High evolutionary turnover of satellite families in Caenorhabditis

  • Subirana Torrent, Juan A.|||0000-0002-1706-9341
  • Albà, M. Mar
  • Messeguer Peypoch, Xavier|||0000-0001-7430-4857
Background: The high density of tandem repeat sequences (satellites) in nematode genomes and the availability of genome sequences from several species in the group offer a unique opportunity to better understand the evolutionary dynamics and the functional role of these sequences. We take advantage of the previously developed SATFIND program to study the satellites in four Caenorhabditis species and investigate these questions.; Methods: The identification and comparison of satellites is carried out in three steps. First we find all the satellites present in each species with the SATFIND program. Each satellite is defined by its length, number of repeats, and repeat sequence. Only satellites with at least ten repeats are considered. In the second step we build satellite families with a newly developed alignment program. Satellite families are defined by a consensus sequence and the number of satellites in the family. Finally we compare the consensus sequence of satellite families in different species.; Results: We give a catalog of individual satellites in each species. We have also identified satellite families with a related sequence and compare them in different species. We analyze the turnover of satellites: they increased in size through duplications of fragments of 100-300 bases. It appears that in many cases they have undergone an explosive expansion. In C. elegans we have identified a subset of large satellites that have strong affinity for the centromere protein CENP-A. We have also compared our results with those obtained from other species, including one nematode and three mammals.; Conclusions: Most satellite families found in Caenorhabditis are species-specific; in particular those with long repeats. A subset of these satellites may facilitate the formation of kinetochores in mitosis. Other satellite families in C. elegans are either related to Helitron transposons or to meiotic pairing centers., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

High evolutionary turnover of satellite families in Caenorhabditis

  • Subirana, Juan A.
  • Albà Soler, Mar
  • Messeguer, Xavier
Background. The high density of tandem repeat sequences (satellites) in nematode genomes and the availability of genome sequences from several species in the group offer a unique opportunity to better understand the evolutionary dynamics and the functional role of these sequences. We take advantage of the previously developed SATFIND program to study the satellites in four Caenorhabditis species and investigate these questions./nMethods. The identification and comparison of satellites is carried out in three steps. First we find all the satellites present in each species with the SATFIND program. Each satellite is defined by its length, number of repeats, and repeat sequence. Only satellites with at least ten repeats are considered. In the second step we build satellite families with a newly developed alignment program. Satellite families are defined by a consensus sequence and the number of satellites in the family. Finally we compare the consensus sequence of satellite families in different species./nResults. We give a catalog of individual satellites in each species. We have also identified satellite families with a related sequence and compare them in different species. We analyze the turnover of satellites: they increased in size through duplications of fragments of 100-300 bases. It appears that in many cases they have undergone an explosive expansion. In C. elegans we have identified a subset of large satellites that have strong affinity for the centromere protein CENP-A. We have also compared our results with those obtained from other species, including one nematode and three mammals./nConclusions. Most satellite families found in Caenorhabditis are species-specific; in particular those with long repeats. A subset of these satellites may facilitate the formation of kinetochores in mitosis. Other satellite families in C. elegans are either related to Helitron transposons or to meiotic pairing centers., We are thankful to Dr. Lourdes Campos for valuable suggestions. Also to Messrs. W. Blevins and F. Acosta-Reyes for help in the preparation of the manuscript and figures. This work was funded by Ministerio de Economía y Competitividad (TIN2010-21062-C02-01, TIN2013-45732-C4-3-P, BFU2012-36820 and 2009–10380) with additional Feder funds.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

High evolutionary turnover of satellite families in Caenorhabditis

  • Subirana Torrent, Juan A.
  • Albà, M. Mar
  • Messeguer Peypoch, Xavier
Background: The high density of tandem repeat sequences (satellites) in nematode genomes and the availability of genome sequences from several species in the group offer a unique opportunity to better understand the evolutionary dynamics and the functional role of these sequences. We take advantage of the previously developed SATFIND program to study the satellites in four Caenorhabditis species and investigate these questions.; Methods: The identification and comparison of satellites is carried out in three steps. First we find all the satellites present in each species with the SATFIND program. Each satellite is defined by its length, number of repeats, and repeat sequence. Only satellites with at least ten repeats are considered. In the second step we build satellite families with a newly developed alignment program. Satellite families are defined by a consensus sequence and the number of satellites in the family. Finally we compare the consensus sequence of satellite families in different species.; Results: We give a catalog of individual satellites in each species. We have also identified satellite families with a related sequence and compare them in different species. We analyze the turnover of satellites: they increased in size through duplications of fragments of 100-300 bases. It appears that in many cases they have undergone an explosive expansion. In C. elegans we have identified a subset of large satellites that have strong affinity for the centromere protein CENP-A. We have also compared our results with those obtained from other species, including one nematode and three mammals.; Conclusions: Most satellite families found in Caenorhabditis are species-specific; in particular those with long repeats. A subset of these satellites may facilitate the formation of kinetochores in mitosis. Other satellite families in C. elegans are either related to Helitron transposons or to meiotic pairing centers., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Long non-coding RNAs as a source of new peptides

  • Ruiz Orera, Jorge, 1988-
  • Messeguer, Xavier
  • Subirana, Juan A.
  • Albà Soler, Mar
Deep transcriptome sequencing has revealed the existence of many transcripts that lack long or conserved open reading frames (ORFs) and which have been termed long non-coding RNAs (lncRNAs). The vast majority of lncRNAs are lineage-specific and do not yet have a known function. In this study, we test the hypothesis that they may act as a repository for the synthesis of new peptides. We find that a large fraction of the lncRNAs expressed in cells from six different species is associated with ribosomes. The patterns of ribosome protection are consistent with the translation of short peptides. lncRNAs show similar coding potential and sequence constraints than evolutionary young protein coding sequences, indicating that they play an important role in de novo protein evolution, This work was funded by Ministerio de Economía y Competitividad (BFU2012-36820 and TIN2013-45732-C4-3-P) and Fundació ICREA (MMA)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

The computability path ordering

  • Blanqui, Frédéric
  • Jouannaud, Jean Pierre
  • Rubio Gimeno, Alberto
This paper aims at carrying out termination proofs for simply typed higher-order calculi automatically by using ordering comparisons. To this end, we introduce the computability path ordering (CPO), a recursive relation on terms obtained by lifting a precedence on function symbols. A first version, core CPO, is essentially obtained from the higher-order recursive path ordering (HORPO) by eliminating type checks from some recursive calls and by incorporating the treatment of bound variables as in the com-putability closure. The well-foundedness proof shows that core CPO captures the essence of computability arguments ^#224, la Tait and Girard, therefore explaining its name. We further show that no further type check can be eliminated from its recursive calls without loosing well-foundedness, but for one for which we found no counterexample yet. Two extensions of core CPO are then introduced which allow one to consider: the first, higher-order inductive types; the second, a precedence in which some function symbols are smaller than application and abstraction., Peer Reviewed, Postprint (author's final draft)