Skip to main content

VALIDACION ASISTIDA DE PROGRAMAS MEDIANTE METODOS PRECISOS Y RIGUROSOS PARA UNA INGENIERIA DEL SOFTWARE ROBUSTA

TIN2013-44742-C4-1-R

•
Funding agency name Ministerio de Economía y Competitividad
Funding agency acronym MINECO
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 2013
State Plan 2013-2016 Plan Estatal de Investigación Científica y Técnica y de Innovación
Management unit Secretaría de Estado de Educación, Formación Profesional y Universidades
Beneficiary centre UNIVERSITAT POLITÈCNICA DE VALÈNCIA

Resultados relacionados

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

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

A Framework for Computing Finite SLD Trees

  • Nishid, Naoki
  • Vidal, Germán|||0000-0002-1857-6951
The search space of SLD resolution, usually represented by means of a so-called SLD tree, is often infinite. However, there are many applications that must deal with possibly infinite SLD trees, like partial evaluation or some static analyses. In this context, being able to construct a finite representation of an infinite SLD tree becomes useful. In this work, we introduce a framework to construct a finite data structure representing the (possibly infinite) SLD derivations for a goal. This data structure, called closed SLD tree, is built using four basic operations: unfolding, flattening, splitting, and subsumption. We prove some basic properties for closed SLD trees, namely that both computed answers and calls are preserved. We present a couple of simple strategies for constructing closed SLD trees with different levels of abstraction, together with some examples of its application. Finally, we illustrate the viability of our approach by introducing a test case generator based on exploring closed SLD trees., This work has been partially supported by the EU (FEDER) and the Spanish Ministerio de Economia y Competitividad (Secretaria de Estado de Investigacion, Desarrollo e Innovacion) under grant TIN2013-44742-C4-1-R and by the Generalitat Valenciana under grant PROMETEO/2011/052.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Contribución de congreso (ConferenceOutput)

A Generalization and Paradigm-Independent Reformulation of Algorithmic Debugging

  • Insa Cabrera, David
  • Silva, Josep|||0000-0001-5096-0008
Algorithmic debugging is a semi-automatic debugging technique that is present in practically all mature programming languages. In this paper we claim that the state of the practice in algorithmic debugging is a step forward compared to the state of the theory. In particular, we argue that novel techniques for algorithmic debugging cannot be supported by the standard internal data structures used in this technique, and a generalization of the standard definitions and algorithms is needed. We identify two specific problems of the standard formulation and implementations of algorithmic debugging, and we propose a reformulation to solve both problems. The reformulation has been done in a paradigm-independent manner to make it useful and reusable in different programming languages., This work has been partially supported by the EU (FEDER) and the Spanish Ministerio de Economía y Competitividad (Secretaría de Estado de Investigación, Desarrollo e Innovación) under Grant TIN2013-44742-C4-1-R and by the Generalitat Valenciana under Grant PROMETEOII/2015/013. David Insa was partially supported by the Spanish Ministerio de Educación under FPU Grant AP2010-4415.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Capítulo o parte de un libro (BookPart)

Corrección Semi-Automática de Programas Java

  • Insa Cabrera, David
  • Silva, Josep|||0000-0001-5096-0008
[ES] La evaluación es una parte fundamental de la enseñanza. Permite tanto a los estudiantes como a los profesores medir el grado de éxito obtenido en el proceso de aprendizaje. De hecho, la evaluación no debería usarse solo para puntuar, sino que debe ser parte integral de la educación, y proporcionar a los alumnos retroalimentación inmediata. Obviamente, la evaluación debe ser objetiva y justa, y tratar a todos los alumnos por igual. Esto ocurre, p.e., en exámenes de respuesta múltiple, pero, desafortunadamente, no está asegurado en la evaluación de código programado por alumnos, puesto que su corrección es todavía un proceso manual y propenso a errores e interpretaciones. En este artículo proponemos un sistema semi-automático de evaluación de código que utiliza técnicas de caja negra (basadas en output-comparison) y técnicas de caja blanca (que observan las propiedades internas del código). El método propuesto incluye nuevas ideas y técnicas que le permiten evaluar incluso código que no compila., Proyecto financiado por EU (FEDER) y el Ministerio de Econom´ıa y Competitividad (TIN2013- 44742-C4-1-R), por la Generalitat Valenciana (PROMETEO-II/2015/013), y por la Universitat Polit`ecnica de Val`encia (PIME B16). Los autores agradecen el respaldo de la acci´on COST IC1405.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Site-Level Web Template Extraction Based on DOM Analysis

  • Alarte-Aleixandre, Julián
  • Silva, Josep|||0000-0001-5096-0008
  • Insa Cabrera, David
  • Tamarit Muñoz, Salvador
One of the main development resources for website engineers are Web templates. Templates allow them to increase productivity by plugin content into already formatted and prepared pagelets. For the final user templates are also useful, because they provide uniformity and a common look and feel for all webpages. However, from the point of view of crawlers and indexers, templates are an important problem, because templates usually contain irrelevant information such as advertisements, menus, and banners. Processing and storing this information leads to a waste of resources (storage space, bandwidth, etc.). It has been measured that templates represent between 40 % and 50 % of data on the Web. Therefore, identifying templates is essential for indexing tasks. In this work we propose a novel method for automatic web template extraction that is based on similarity analysis between the DOM trees of a collection of webpages that are detected using an hyperlink analysis. Our implementation and experiments demonstrate the usefulness of the technique., This work has been partially supported by the EU (FEDER) and the Spanish Ministerio de Econom´ıa y Competitividad (Secretar´ıa de Estado de Investigaci´on, Desarrollo e Innovaci´on) under grant TIN2013-44742-C4-1-R and by the Generalitat Valenciana under grant PROMETEOII/2015/013. David Insa was partially supported by the Spanish Ministerio de Eduaci´on under FPU grant AP2010-4415.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Dynamic slicing of concurrent specification languages

  • Llorens Agost, María Luisa|||0000-0002-2790-0055
  • Oliver Villarroya, Javier|||0000-0002-1169-1260
  • Silva, Josep|||0000-0001-5096-0008
  • Tamarit Muñoz, Salvador
[EN] Dynamic slicing is a technique to extract the part of the program (called slice) that influences or is influenced, in a particular execution, by a given point of interest in the source code (called slicing criterion). Since a single execution is considered, the technique often uses a trace of this execution to analyze data and control dependencies. In this work we present the first formulation and implementation of dynamic slicing in the context of CSP. Most of the ideas presented can be directly applied to other concurrent specification languages such as Promela or CCS, but we center the discussion and the implementation on CSP. We base our technique on a new data structure to represent CSP computations called track. A track is a data structure which represents the sequence of expressions that have been evaluated during the computation, and moreover, it is labeled with the location of these expressions in the specification. The implementation of a dynamic slicer for CSP is useful for debugging, program comprehension, and program specialization, and it is also interesting from a theoretical perspective because CSP introduces difficulties such as heavy concurrency and non-determinism, synchronizations, frequent absence of data dependence, etc. © 2016 Elsevier B.V. All rights reserved, This work has been partially supported by the EU (FEDER) and the Spanish Ministerio de Economia y Competitividad under Grant TIN2013-44742-C4-1-R and by the Generalitat Valenciana under Grant PROMETEOII/2015/013 (SmartLogic). Salvador Tamarit was partially supported by Madrid regional projects N-GREENS Software-CM (S2013/ICE-2731), and by European Union project POLCA (STREP FP7-ICT-20133.4 610686).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Capítulo o parte de un libro (BookPart)

Towards Symbolic Execution in Erlang

  • Vidal, Germán|||0000-0002-1857-6951
The concurrent functional language Erlang [1] has a number of distinguishing features, like dynamic typing, concurrency via asynchronous message passing or hot code loading, that make it especially appropriate for distributed, faulttolerant, soft real-time applications. The success of Erlang is witnessed by the increasing number of its industrial applications. For instance, Erlang has been used to implement Facebook’s chat back-end, the mobile application Whatsapp or Twitterfall—a service to view trends and patterns from Twitter—, to name a few. The success of the language, however, also requires the development of powerful testing and verification techniques. Symbolic execution is at the core of many program analysis and transformation techniques, like partial evaluation, test-case generation or model checking. In this paper, we introduce a symbolic execution technique for Erlang. We discuss how both an overapproximation and an underapproximation of the concrete semantics can be obtained. We illustrate our approach through some examples. To the best of our knowledge, this is the first attempt to formalize symbolic execution in the context of this language, where previous approaches have only considered exploring different schedulings but have not dealt with symbolic data. More details can be found in the companion technical report, This work has been partially supported by the Spanish Ministerio de Economía y Competitividad (Secretaría de Estado de Investigación, Desarrollo e Innovación) under grant TIN2013-44742-C4-1-R and by the Generalitat Valenciana under grant PROMETEO/2011/052.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Capítulo o parte de un libro (BookPart)

Concolic Execution and Test Case Generation in Prolog

  • Vidal, Germán|||0000-0002-1857-6951
Symbolic execution extends concrete execution by allowing symbolic input data and then exploring all feasible execution paths. It has been defined and used in the context of many different programming languages and paradigms. A symbolic execution engine is at the heart of many program analysis and transformation techniques, like partial evaluation, test case generation or model checking, to name a few. Despite its relevance, traditional symbolic execution also suffers from several drawbacks. For instance, the search space is usually huge (often infinite) even for the simplest programs. Also, symbolic execution generally computes an overapproximation of the concrete execution space, so that false positives may occur. In this paper, we propose the use of a variant of symbolic execution, called concolic execution, for test case generation in Prolog. Our technique aims at full statement coverage. We argue that this technique computes an underapproximation of the concrete execution space (thus avoiding false positives) and scales up better to medium and large Prolog applications., This work has been partially supported by the EU (FEDER) and the Spanish Ministerio de Economía y Competitividad (Secretaría de Estado de Investigación, Desarrollo e Innovación) under grant TIN2013-44742-C4-1-R and by the Generalitat Valenciana under grant PROMETEO/2011/052.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

A theory of reversibility for Erlang

  • Lanese, Ivan
  • Nishida, Naoki
  • Palacios, Adrián
  • Vidal, Germán|||0000-0002-1857-6951
[EN] In a reversible language, any forward computation can be undone by a finite sequence of backward steps. Reversible computing has been studied in the context of different programming languages and formalisms, where it has been used for testing and verification, among others. In this paper, we consider a subset of Erlang, a functional and concurrent programming language based on the actor model. We present a formal semantics for reversible computation in this language and prove its main properties, including its causal consistency. We also build on top of it a rollback operator that can be used to undo the actions of a process up to a given checkpoint. (C) 2018 Elsevier Inc. All rights reserved., This work has been partially supported by MINECO/AEI/FEDER (EU) under grants TIN2013-44742-C4-1-R and TIN2016-76843-C4-1-R, by the Generalitat Valenciana under grant PROMETEO-II/2015/013 (SmartLogic), by the COST Action IC1405 on Reversible Computation-extending horizons of computing, and by JSPS KAKENHI Grant Number JP17H01722. Adrian Palacios was partially supported by the EU (FEDER) and the Spanish Ayudas para contratos predoctorales para la formacian de doctores and Ayudas a la movilidad predoctoral para la realtzacion de estancias breves en centros de I+D, MINECO (SEIDI), under FPI grants BES-2014-069749 and EEBB-I-16-11469. Ivan Lanese was partially supported by INdAM as a member of GNCS (Gruppo Nazionale per il Calcolo Scientifico). Part of this research was done while the third and fourth authors were visiting Nagoya and Bologna Universities; they gratefully acknowledge their hospitality. Finally, we thank Salvador Tamarit and the anonymous reviewers for their helpful suggestions and comments.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Web template extraction based on hyperlink analysis

  • Alarte-Aleixandre, Julián
  • Silva, Josep|||0000-0001-5096-0008
  • Insa Cabrera, David
  • Tamarit Muñoz, Salvador
[EN] Web templates are one of the main development resources for website engineers. Templates allow them to increase productivity by plugin content into already formatted and prepared pagelets. For the final user templates are also useful, because they provide uniformity and a common look and feel for all webpages. However, from the point of view of crawlers and indexers, templates are an important problem, because templates usually contain irrelevant information such as advertisements, menus, and banners. Processing and storing this information is likely to lead to a waste of resources (storage space, bandwidth, etc.). It has been measured that templates represent between 40% and 50% of data on the Web. Therefore, identifying templates is essential for indexing tasks. In this work we propose a novel method for automatic template extraction that is based on similarity analysis between the DOM trees of a collection of webpages that are detected using menus information. Our implementation and experiments demonstrate the usefulness of the technique., This work has been partially supported by the EU (FEDER) and the Spanish Ministerio de Economia y Competitividad (Secretaria de Estado de Investigacion, Desarrollo e Innovacion) under Grant TIN201344742-C4-1-R and by the Generalitat Valenciana under Grant PROMETEO/2011/052. David Insa was partially supported by the Spanish Ministerio de Educacion under FPU Grant AP2010-4415. Salvador Tamarit was partially supported by research project POLCA, Programming Large Scale Heterogeneous Infrastructures (610686), funded by the European Union, STREP FP7.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Contribución de congreso (ConferenceOutput)

Dynamic Slicing of CSP via Tracking

  • Llorens Agost, María Luisa|||0000-0002-2790-0055
  • Oliver Villarroya, Javier|||0000-0002-1169-1260
  • Silva, Josep|||0000-0001-5096-0008
  • Tamarit Muñoz, Salvador
Dynamic slicing is a technique to extract the part of the program (called slice) that influences or is influenced, in a particular execution, by a given point of interest in the source code (called slicing criterion). Since a single execution is considered, the technique often uses a trace of this execution to analyze data and control dependencies. In this work we present the first formulation and implementation of dynamic slicing in the context of CSP. The implementation of a dynamic slicer for CSP is useful for debugging, program comprehension, and program specialization, and it is also interesting from a theoretical perspective because CSP introduces difficulties such as heavy concurrency and non-determinism, synchronizations, frequent absence of data dependence, etc. We base our technique on a new data structure to represent CSP computations called track., This work has been partially supported by the EU (FEDER) and the Spanish Ministerio de Economía y Competitividad (Secretaría de Estado de Investigación, Desarrollo e Innovación) under grant TIN2013-44742-C4-1-R (CAVI-ROSE) and by the Generalitat Valenciana under grant PROMETEOII/2015/013. Salvador Tamarit was partially supported by EU FP7-ICT-2013.3.4 project 610686 POLCA, Comunidad de Madrid project S2013/ICE-2731 N-Greens Software and MINECO Projects TIN2012-39391-C0-03 and TIN2012-39391-C04-04 (StrongSoft).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

A Survey of Algorithmic Debugging

  • Caballero, Rafael
  • Riesco, Adrián
  • Silva, Josep|||0000-0001-5096-0008
[EN] Algorithmic debugging is a technique proposed in 1982 by E. Y. Shapiro in the context of logic programming. This survey shows how the initial ideas have been developed to become a widespread debugging schema ftting many diferent programming paradigms and with applications out of the program debugging feld. We describe the general framework and the main issues related to the implementations in diferent programming paradigms and discuss several proposed improvements and optimizations. We also review the main algorithmic debugger tools that have been implemented so far and compare their features. From this comparison, we elaborate a summary of desirable characteristics that should be considered when implementing future algorithmic debuggers., This work has been partially supported by the EU (FEDER) and the Spanish Ministerio de Economia y Competitividad under grant TIN2013-44742-C4-1-R, TIN2016-76843-C4-1-R, StrongSoft (TIN2012-39391-C04-04), and TRACES (TIN2015-67522-C3-3-R) by the Generalitat Valenciana under grant PROMETEO-II/2015/013 (SmartLogic) and by the Comunidad de Madrid project N-Greens Software-CM (S2013/ICE-2731).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Automatic detection of webpages that share the same web template

  • Alarte-Aleixandre, Julián
  • Silva, Josep|||0000-0001-5096-0008
  • Insa Cabrera, David
  • Tamarit Muñoz, Salvador
[EN] Template extraction is the process of isolating the template of a given webpage. It is widely used in several disciplines, including webpages development, content extraction, block detection, and webpages indexing. One of the main goals of template extraction is identifying a set of webpages with the same template without having to load and analyze too many webpages prior to identifying the template. This work introduces a new technique to automatically discover a reduced set of webpages in a website that implement the template. This set is computed with an hyperlink analysis that computes a very small set with a high level of confidence., This work has been partially supported by the Spanish Ministerio de Econom´ıa y Competitividad (Secretar´ıa de Estado de Investigacion, Desarrollo e Innovaci ´ on) ´ under grant TIN2013-44742-C4-1-R and by the Generalitat Valenciana under grant PROMETEO/2011/052. David Insa was partially supported by the Spanish Ministerio de Eduacion under FPU grant AP2010-4415. Salvador Tamarit was partially supported by research project POLCA, Programming Large Scale Heterogeneous Infrastructures (610686), funded by the European Union, STREP FP7.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Concolic Testing in Logic programming

  • Mesnard, Fred
  • Payet, Etienne
  • Vidal, Germán|||0000-0002-1857-6951
Software testing is one of the most popular validation techniques in the software industry. Surprisingly, we can only find a few approaches to testing in the context of logic programming. In this paper, we introduce a systematic approach for dynamic testing that combines both concrete and symbolic execution. Our approach is fully automatic and guarantees full path coverage when it terminates. We prove some basic properties of our technique and illustrate its practical usefulness through a prototype implementation., This work has been partially supported by the EU (FEDER) and the Spanish Ministerio de Economia y Competitividad under grant TIN2013-44742-C4-1-R and by the Generalitat Valenciana under grant PROMETEOII/2015/013. Part of this research was done while the third author was visiting the University of Reunion; G. Vidal gratefully acknowledges their hospitality.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Capítulo o parte de un libro (BookPart)

Reducing relative termination to dependency pair problems

  • Iborra, José
  • Nishida, Naoki
  • Yamada, Akihisa
  • Vidal, Germán|||0000-0002-1857-6951
Relative termination, a generalized notion of termination, has been used in a number of different contexts like proving the confluence of rewrite systems or analyzing the termination of narrowing. In this paper, we introduce a new technique to prove relative termination by reducing it to dependency pair problems. To the best of our knowledge, this is the first significant contribution to Problem #106 of the RTA List of Open Problems. The practical significance of our method is illustrated by means of an experimental evaluation., Germán Vidal is partially supported by the EU (FEDER) and the Spanish Ministerio de Economía y Competitividad under grant TIN2013-44742-C4-R and by the Generalitat Valenciana under grant PROMETEOII201/013. Akihisa Yamadais supported by the Austrian Science Fund (FWF): Y757
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Algorithmic debugging generalized

  • Insa Cabrera, David
  • Silva, Josep|||0000-0001-5096-0008
[EN] Algorithmic debugging is a semi-automatic debugging technique that abstracts the operational details of computations, allowing the programmers to debug their code from an abstract point of view. However, its use in practice is still marginal, and one of the reasons is the lack of precision of this technique when reporting errors (current algorithmic debuggers do not point an expression or line as buggy, but they point a whole procedure/function/method as containing the bug). In this paper, we make a step forward to overcome this problem. We identify two specific causes of that problem in the standard formulation and implementations of algorithmic debugging, and we present a reformulation to solve both problems. We show that the novel ideas included in the reformulation proposed cannot be supported by the standard internal data structures (such as the Execution Tree) used in this technique and, hence, a generalisation of the standard definitions and algorithms is needed. The reformulation has been done in a language independent manner to make it useful and reusable in different programming languages. (C) 2018 Elsevier Inc. All rights reserved., This work has been partially supported by the EU (FEDER) and the Spanish Ministerio de Economia y Competitividad under grants TIN2013-44742-C4-1-R and TIN2016-76843-C4-1-12, and by the Generalitat Valenciana under grant PROMETEO-II/2015/013 (SmartLogic).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Contribución de congreso (ConferenceOutput)

Semi-automatic assessment of unrestrained Java code: a Library, a DSL, and a workbench to assess exams and exercises

  • Insa Cabrera, David
  • Silva, Josep|||0000-0001-5096-0008
Automated marking of multiple-choice exams is of great interest in university courses with a large number of students. For this reason, it has been systematically implanted in almost all universities. Automatic assessment of source code is however less extended. There are several reasons for that. One reason is that almost all existing systems are based on output comparison with a gold standard. If the output is the expected, the code is correct. Otherwise, it is reported as wrong, even if there is only one typo in the code. Moreover, why it is wrong remains a mystery. In general, assessment tools treat the code as a black box, and they only assess the externally observable behavior. In this work we introduce a new code assessment method that also verifies properties of the code, thus allowing to mark the code even if it is only partially correct. We also report about the use of this system in a real university context, showing that the system automatically assesses around 50% of the work., This work has been partially supported by the EU (FEDER) and the Spanish Ministerio de Economíay Competitividad (Secretaría de Estado de Investigación, Desarrollo e Innovación) under grant TIN2013-44742-C4-1-R and by the Generalitat Valenciana under grant PROMETEOII2015/013. David Insa was partially supported by the Spanish Ministerio de Educación under FPU grant AP2010-4415.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Contribución de congreso (ConferenceOutput)

TeMex: The Web Template Extractor

  • Alarte-Aleixandre, Julián
  • Silva, Josep|||0000-0001-5096-0008
  • Insa Cabrera, David
  • Tamarit Muñoz, Salvador
This paper presents and describes TeMex, a site-level web template extractor. TeMex is fully automatic, and it can work with online webpages without any preprocessing stage (no information about the template or the associated webpages is needed) and, more importantly, it does not need a prede- fined set of webpages to perform the analysis. TeMex only needs a URL. Contrarily to previous approaches, it includes a mechanism to identify webpage candidates that share the same template. This mechanism increases both recall and precision, and it also reduces the amount of webpages loaded and processed. We describe the tool and its internal architecture, and we present the results of its empirical evaluation., This work has been partially supported by the EU (FEDER) and the Spanish Ministerio de Economía y Competitividad (Secretaría de Estado de Investigación, Desarrollo e Innovación) under Grant TIN2013-44742-C4-1-R and by the Generalitat Valenciana under Grant PROMETEOII/2015/013. David Insa was partially supported by the Spanish Ministerio de Educación under FPU Grant AP2010-4415. Salvador Tamarit was partially supported by research project POLCA, Programming Large Scale Heterogeneous Infrastructures (610686), funded by the European Union, STREP FP7.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Relative Termination via Dependency Pairs

  • Iborra, José
  • Nishida, Naoki
  • Vidal Oriola, Germán
  • Yamada, Akihisa
[EN] A term rewrite system is terminating when no infinite reduction sequences are possible. Relative termination generalizes termination by permitting infinite reductions as long as some distinguished rules are not applied infinitely many times. Relative termination is thus a fundamental notion that has been used in a number of different contexts, like analyzing the confluence of rewrite systems or the termination of narrowing. In this work, we introduce a novel technique to prove relative termination by reducing it to dependency pair problems. To the best of our knowledge, this is the first significant contribution to Problem #106 of the RTA List of Open Problems. We first present a general approach that is then instantiated to provide a concrete technique for proving relative termination. The practical significance of our method is illustrated by means of an experimental evaluation., Open access funding provided by Austrian Science Fund (FWF). We would like to thank Nao Hirokawa, Keiichirou Kusakari, and the anonymous reviewers for their helpful comments and suggestions in early stages of this work.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Reversible computation in term rewriting

  • Nishida, Naoki
  • Palacios, Adrián
  • Vidal, Germán
[EN] Essentially, in a reversible programming language, for each forward computation from state S to state S', there exists a constructive method to go backwards from state S' to state S. Besides its theoretical interest, reversible computation is a fundamental concept which is relevant in many different areas like cellular automata, bidirectional program transformation, or quantum computing, to name a few. In this work, we focus on term rewriting, a computation model that underlies most rule-based programming languages. In general, term rewriting is not reversible, even for injective functions; namely, given a rewrite step t(1) -> t(2), we do not always have a decidable method to get t(1) from t(2). Here, we introduce a conservative extension of term rewriting that becomes reversible. Furthermore, we also define two transformations, injectivization and inversion, to make a rewrite system reversible using standard term rewriting. We illustrate the usefulness of our transformations in the context of bidirectional program transformation. (C) 2017 Elsevier Inc. All rights reserved., This work has been partially supported by the EU (FEDER) and the Spanish Ministerio de Economia y Competitividad (MINECO) under grants TIN2013-44742-C4-1-R and TIN2016-76843-C4-1-R, by the Generalitat Valenciana under grant PROMETE0-II/2015/013 (SmartLogic), and by the COST Action IC1405 on Reversible Computation extending horizons of computing. Adrian Palacios was partially supported by the EU (FEDER) and the Spanish Ayudas para contratos predoctorales para la formacian de doctores and Ayudas a la movilidad predoctoral para la realizacion de estancias breves en centros de I+D, MINECO (SEIDI), under FPI grants BES-2014-069749 and EEBB-I-16-11469. Part of this research was done while the second and third authors were visiting Nagoya University; they gratefully acknowledge their hospitality.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Capítulo o parte de un libro (BookPart)

A Generalized Model for Algorithmic Debugging

  • Insa Cabrera, David
  • Silva, Josep|||0000-0001-5096-0008
Algorithmic debugging is a semi-automatic debugging technique that is present in practically all mature programming languages. In this paper we claim that the state of the practice in algorithmic debugging is a step forward compared to the state of the theory. In particular, we argue that novel techniques for algorithmic debugging cannot be supported by the standard internal data structures used in this technique, and a generalization of the standard definitions and algorithms is needed. We identify two specific problems of the standard formulation and implementations of algorithmic debugging, and we propose a reformulation to solve both problems. The reformulation has been done in a paradigm-independent manner to make it useful and reusable in different programming languages., This work has been partially supported by the EU (FEDER) and the Spanish Ministerio de Economía y Competitividad (Secretaría de Estado de Investigación, Desarrollo e Innovación) under Grant TIN2013-44742-C4-1-R and by the Generalitat Valenciana under Grant PROMETEOII/2015/013. David Insa was partially supported by the Spanish Ministerio de Educación under FPU Grant AP2010-4415.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Automatic transformation of iterative loops into recursive methods

  • Insa Cabrera, David
  • Silva, Josep|||0000-0001-5096-0008
[EN] Context In software engineering, taking a good election between recursion and iteration is essential because their efficiency and maintenance are different. In fact, developers often need to transform iteration into recursion (e.g., in debugging, to decompose the call graph into iterations); thus, it is quite surprising that there does not exist a public transformation from loops to recursion that can be used in industrial projects (i.e., it is automatic, it handles all kinds of loops, it considers exceptions, etc.). Objective This article describes an industrial algorithm implemented as a Java library able to automatically transform iterative loops into equivalent recursive methods. The transformation is described for the programming language Java, but it is general enough as to be adapted to many other languages that allow iteration and recursion. Method We describe the changes needed to transform loops of types while/do/for/foreach into recursion. We provide a transformation schema for each kind of loop. Results Our algorithm is the first public transformation that can be used in industrial projects and faces the whole Java language (i.e., it is fully automatic, it handles all kinds of loops, it considers exceptions, it treats the control statements break and continue, it handles loop labels, it is able to transform any number of nested loops, etc.). This is particularly interesting because some of these features are missing in all previous work, probably, due to the complexity that their mixture introduce in the transformation. Conclusion Developers should use a methodology when transforming code, specifically when transforming loops into recursion. This article provides guidelines and algorithms that allow them to face different problems such as exception handling. The implementation has been made publicly available as open source., This work has been partially supported by the EU (FEDER) and the Spanish Ministerio de Economia y Competitividad (Secretaria de Estado de Investigacion, Desarrollo e Innovacion) under Grant TIN2013-44742-C4-1-R and by the Generalitat Valenciana under Grant PROMETEO/2011/052. David Insa was partially supported by the Spanish Ministerio de Educacion under FPU Grant AP2010-4415.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Symbolic execution as a basis for termination analysis

  • Vidal, Germán|||0000-0002-1857-6951
Program termination is a relevant property that has been extensively studied in the context of many different formalisms and programming languages. Traditional approaches to proving termination are usually based on inspecting the source code. Recently, a new semantics-based approach has emerged, which typically follows a two-stage scheme: first, a finite data structure representing the computation space of the program is built; then, termination is analyzed by inspecting the transitions in this data structure using traditional, syntax-based techniques. Unfortunately, this approach is still specific to a programming language and semantics. In this work, we present instead a general, high-level framework that follows the semanticsbased approach to proving termination. In particular, we focus on the first stage and advocate the use of symbolic execution, together with appropriate subsumption and abstraction operators, for producing a finite representation of the computations of a program. Hopefully, this higher level approach will provide useful insights for designing new semantics-based termination tools for particular programming languages. © 2015 Elsevier B.V. All rights reserved., This work has been partially supported by the EU (FEDER) and the Spanish Ministerio de Economia y Competitividad (Secretaria de Estado de Investigacion, Desarrollo e Innovacion) under grant TIN2013-44742-C4-1-R and by the Generalitat Valenciana under grant PROMETEO/2011/052.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Capítulo o parte de un libro (BookPart)

¿Aprendo más trabajando solo o en pareja? ¿Aprendo más estando cerca o lejos de la pizarra?

  • Insa Cabrera, David
  • Tamarit Muñoz, Salvador
  • Silva, Josep|||0000-0001-5096-0008
[ES] Este artculo desarrolla un estudio estadstico a partir de un experimentorealizado en dos escuelas universitarias de la Universitat Politecnica deValencia. El objetivo principal del estudio es cuanticar como la distanciade los alumnos al profesor y la pizarra en el aula afecta a su rendimientoacademico. Un segundo objetivo pretende determinar si trabajar en parejao de manera individual tambien afecta al rendimiento. En el experimentohemos recogido y procesado informacion sobre la posicion exacta de cadaalumno en el aula y en el laboratorio durante dos cursos academicos.Tambien se registro cada cambio de posicion, as como sus notas en diferentesexamenes, cursos y asignaturas tanto de teora como de practicas.Nuestro experimento ha producido gran cantidad de datos que han sidoanalizados usando metodos estadsticos avanzados como ANOVA, el testHSD post-hoc de Tukey, y el test de Mantel basado en el coeciente decorrelacion producto-momento de Pearson., Proyecto financiado por EU (FEDER) y el Ministerio de Econom´ıa y Competitividad (TIN2013- 44742-C4-1-R), por la Generalitat Valenciana (PROMETEO-II/2015/013), y por la Universitat Polit`ecnica de Val`encia (PIME B16). Los autores agradecen el respaldo de la acci´on COST IC1405.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Automatic assessment of Java code

  • Insa Cabrera, David
  • Silva, Josep|||0000-0001-5096-0008
[EN] Assessment is an integral part of education often used to evaluate students, but also to provide them with feedback. It is essential to ensure that assessment is fair, objective, and equally applied to all students. This holds, for instance, in multiple-choice tests, but, unfortunately, it is not ensured in the assessment of source code, which is still a manual and error-prone task. In this paper, we present JavAssess, a Java library with an API composed of around 200 methods to automatically inspect, test, mark, and correct Java code. It can be used to produce both black-box (based on output comparison) and white-box (based on the internal properties of the code) assessment tools. This means that it allows for marking the code even if it is only partially correct. We describe the library, how to use it, and we provide a complete example to automatically mark and correct a student's code. We also report the use of this system in a real university context to compare manual and automatic assessment in university courses. The study reports the average error in the marks produced by teachers when assessing source code manually, and it shows that the system automatically assesses around 50% of the work. (C) 2018 Elsevier Ltd. All rights reserved., This work has been partially supported by MINECO/AEI/FEDER (EU) under grants TIN2013-44742-C4-1-R and TIN2016-76843-C4-1-R, by the Generalitat Valenciana under grant PROMETEO-II/2015/013 (SmartLogic), and by the Universitat Politecnica de Valencia under grant PIME B18 and EICE HEGEA.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Contribución de congreso (ConferenceOutput)

Reversible Term Rewriting

  • Nishida, Naoki
  • Palacios Corella, Adrián
  • Nishida
  • Vidal, Germán|||0000-0002-1857-6951
Essentially, in a reversible programming language, for each forward computation step from state S to state S', there exists a constructive and deterministic method to go backwards from state S' to state S. Besides its theoretical interest, reversible computation is a fundamental concept which is relevant in many different areas like cellular automata, bidirectional program transformation, or quantum computing, to name a few. In this paper, we focus on term rewriting, a computation model that underlies most rule-based programming languages. In general, term rewriting is not reversible, even for injective functions; namely, given a rewrite step t1 -> t2, we do not always have a decidable and deterministic method to get t1 from t2. Here, we introduce a conservative extension of term rewriting that becomes reversible. Furthermore, we also define a transformation to make a rewrite system reversible using standard term rewriting., This work has been partially supported by the EU (FEDER) and the Spanish Ministerio de Economía y Competitividad (MINECO) under grant TIN2013-44742-C4-1-R, by the Generalitat Valenciana under grant PROMETEO-II/2015/013 (SmartLogic) and by the COST Action IC 1405 on Reversible Computation. A. Palacios was partially supported by the the EU (FEDER) and the Spanish Ayudas para contratos predoctorales para la formación de doctores de la Sec. Estado de Investigación, Desarrollo e Innovación del MINECO under FPI grant BES-2014-069749. Part of this research was done while the second and third authors were visiting Nagoya University; they gratefully acknowledge their hospitality.