Pasar al contenido principal

Resultados relacionados

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

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación 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
Publicación 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
Publicación Contribución de congreso (ConferenceOutput)

Automatically Proving and Disproving Feasibility Conditions

  • Gutiérrez Gil, Raúl|||0000-0002-3984-2868
  • Lucas Alba, Salvador|||0000-0001-9923-2108
[EN] In the realm of term rewriting, given terms s and t, a reachability condition s>>t is called feasible if there is a substitution O such that O(s) rewrites into O(t) in zero or more steps; otherwise, it is called infeasible. Checking infeasibility of (sequences of) reachability conditions is important in the analysis of computational properties of rewrite systems like confluence or (operational) termination. In this paper, we generalize this notion of feasibility to arbitrary n-ary relations on terms defined by first-order theories. In this way, properties of computational systems whose operational semantics can be given as a first-order theory can be investigated. We introduce a framework for proving feasibility/infeasibility, and a new tool, infChecker, which implements it., Supported by EU (FEDER), and projects RTI2018-094403-B-C32, PROMETEO/2019/098, and SP20180225. Also by INCIBE program "Ayudas para la excelencia de los equipos de investigación avanzada en ciberseguridad" (Raul Gutiérrez).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Contribución de congreso (ConferenceOutput)

infChecker. A Tool for Checking Infeasibility

  • Gutiérrez Gil, Raúl|||0000-0002-3984-2868
  • Lucas Alba, Salvador|||0000-0001-9923-2108
[EN] Given a Conditional Term Rewriting System (CTRS) R and terms s and t, we say that the reachability condition s ->* t is *feasible* if there is a substitution \sigma instantiating the variables in s and t such that the *reachability test* \sigma(s)->* \sigma(t) succeeds; otherwise, we call it *infeasible*. Checking infeasibility of such (sequences of) reachability conditions is important in the analysis of computational properties of CTRSs, like confluence or operational termination. Recently, a logic-based approach to prove and disprove infeasibility has been introduced. In this paper we present infChecker, a new tool for checking infeasibility which is based on such an approach., Partially supported by the EU (FEDER), and projects RTI2018-094403-B-C32, PROMETEO/2019/098, and SP20180225. Raul Gutierrez was also supported by INCIBE program Ayudas para la excelencia de los equipos de investigacion avanzada en ciberseguridad.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Contribución de congreso (ConferenceOutput)

MU-TERM: Verify Termination Properties Automatically (System Description)

  • Gutiérrez Gil, Raúl|||0000-0002-3984-2868
  • Lucas Alba, Salvador|||0000-0001-9923-2108
[EN] We report on the new version of mu-term, a tool for proving termination properties of variants of rewrite systems, including conditional, context-sensitive, equational, and order-sorted rewrite systems. We follow a unified logic-based approach to describe rewriting computations. The automatic generation of logical models for suitable first-order theories and formulas provide a common basis to implement the proofs., Supported by EU (FEDER), and projects RTI2018-094403-B-C32,PROMETEO/ 2019/098, and SP20180225. Also by INCIBE program "Ayudas para la excelencia de los equipos de investigación avanzada en ciberseguridad" (Raul Gutiérrez).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación 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.