Pasar al contenido principal

METODOS RIGUROSOS PARA EL DESARROLLO DE SISTEMAS SOFTWARE DE CALIDAD Y FIABILIDAD CERTIFICADAS

PID2019-108528RB-C22

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Convocatoria Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Año convocatoria 2019
Plan Estatal 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSIDAD COMPLUTENSE DE MADRID

Resultados relacionados

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

Docta Complutense
Publicación Artículo científico (JournalArticle)

Complexity analysis and practical resolution of the data classification problem with private characteristics

  • Pantoja, David
  • Rodríguez Laguna, Ismael
  • Rubio Díez, Fernando
  • Segura Díaz, Clara María
In this work we analyze the problem of, given the probability distribution of a population, questioning an unknown individual that is representative of the distribution so that our uncertainty about certain characteristics is significantly reduced—but the uncertainty about others, deemed private or sensitive, is not. Thus, the goal of the problem is extracting information being relevant to a legitimate purpose while preserving the privacy of individuals, which is crucial to enable non-intrusive selection processes in several areas. For instance, it is essential in the design of non-discriminatory personnel selection, promotion, and layoff processes in companies and institutions; in the retrieval of customer information being relevant to the service provided by a company (and no more); in certifications not revealing sensitive industrial information being irrelevant for the certification itself; etc. Interactive questioning processes are constructed for this purpose, which requires generalizing the notion of decision trees to account the amount of desired and undesired information retrieved for each branch of the plan. Our findings about this problem are both theoretical and practical: on the one hand, we prove its NP-completeness by a reduction from the Set Cover problem; and on the other hand, given this intractability, we provide heuristic solutions to find reasonable solutions in affordable time. In particular, a greedy algorithm and two genetic algorithms are presented. Our experiments indicate that the best results are obtained using a genetic algorithm reinforced with a greedy strategy.
Docta Complutense
Publicación Artículo científico (JournalArticle)

A full process algebraic representation of Ant Colony Optimization

  • Rodríguez Laguna, Ismael
  • López Barquilla, Natalia
  • García Moreno, María
We present a process algebra capable of specifying parallelized Ant Colony Optimization algorithms in full detail: PA2CO. After explaining the basis of three different ACO algorithms (Ant System, MAX-MIN Ant System, and Ant Colony System), we formally define PA2CO and use it for representing several types of implementations with different parallel schemes. In particular fine-grained and coarse-grained specifications, each one taking advantage of parallel executions at different levels of system granularity, are formalized.
Docta Complutense
Publicación Contribución de congreso (ConferenceOutput)

Computing Political Power: The Case of the Spanish Parliament

Docta Complutense
Publicación Artículo científico (JournalArticle)

Simulating and model checking membrane systems using strategies in Maude

  • Rubio Cuéllar, Rubén Rafael
  • Martí Oliet, Narciso
  • Pita Andreu, María Isabel
  • Verdejo López, José Alberto
Membrane systems are a biologically-inspired computational model based on the structure of biological cells and the way chemicals interact and traverse their membranes. Although its dynamics is described by rules, encoding membrane systems into rewriting logic is not straightforward due to its complex control mechanisms, and multiple alternatives have been proposed in the literature and implemented in the Maude specification language. The recent release of the Maude strategy language and its associated strategy-aware model checker allow specifying these systems more easily, so that they become executable and verifiable for free. An interactive environment based on a previous prototype by Oana Andrei and Dorel Lucanu is available to operate with the membranes.
Docta Complutense
Publicación Contribución de congreso (ConferenceOutput)

An overview of the Maude strategy language and its applications

  • Rubio Cuéllar, Rubén Rafael
In the Maude specification language, the behavior of systems is modeled by nondeterministic rewrite rules, whose free application may not always be desirable. Hence, a strategy language has been introduced to control the application of rules at a high level, without the intricacies of metaprogramming. In this paper, we give an overview of the Maude strategy language, its applications, related verification tools, and extensions, illustrated with examples.
Docta Complutense
Publicación Contribución de congreso (ConferenceOutput)

Programming Open Distributed Systems in Maude

  • Durán, Francisco
  • Eker, Steven
  • Escobar, Santiago
  • Martí Oliet, Narciso
  • Rubio Cuéllar, Rubén Rafael
  • Talcott, Carolyn
Maude is a high-performance logical framework based on rewriting logic and supporting formal specification, verification and declarative programming of concurrent systems. Since most concurrent open systems are made up of actor-like objects that communicate with each other through message passing, Maude provides special features to support their specification, verification and programming. Since open systems are heterogeneous, involving widely different kinds of objects such as sensors, actuators, devices, databases, graphical user interfaces, and so on, Maude supports declarative message-passing interaction between Maude objects and a wide variety of heterogeneous external objects. In this paper we explain and illustrate a methodology where an open system can first be designed and verified in Maude and then implemented as a distributed system of heterogeneous objects in a way that seamlessly bridges the gap between its formal specification and verification and its distributed implementation.
Docta Complutense
Publicación Contribución de congreso (ConferenceOutput)

Equational Unification and Matching, and Symbolic Reachability Analysis in Maude 3.2 (System Description)

  • Durán, Francisco
  • Eker, Steven
  • Escobar, Santiago
  • Martí Oliet, Narciso
  • Meseguer, José
  • Rubio Cuéllar, Rubén Rafael
  • Talcott, Carolyn
Equational unification and matching are fundamental mechanisms in many automated deduction applications. Supporting them efficiently for as wide as possible a class of equational theories, and in a typed manner supporting type hierarchies, benefits many applications; but this is both challenging and nontrivial. We present Maude 3.2’s efficient support of these features as well as of symbolic reachability analysis of infinite-state concurrent systems based on them.
Docta Complutense
Publicación Contribución de congreso (ConferenceOutput)

Maude as a library: an efficient all-purpose programming interface

  • Rubio Cuéllar, Rubén Rafael
We present a general and efficient programming interface to Maude from Python and other programming languages. All relevant Maude entities and operations are exposed in a documented object-oriented library to facilitate the integration of Maude into external programs and vice versa. This paper describes the design and implementation of the library, explains how to use it, and discusses some mature applications.
Docta Complutense
Publicación Artículo científico (JournalArticle)

Model checking strategy-controlled systems in rewriting logic

  • Rubio Cuéllar, Rubén Rafael
  • Martí Oliet, Narciso
  • Pita Andreu, María Isabel
  • Verdejo López, José Alberto
Rewriting logic and its implementation Maude are an expressive framework for the formal specification and verification of software and other kinds of systems. Concurrency is naturally represented by nondeterministic local transformations produced by the application of rewriting rules over algebraic terms in an equational theory. Some aspects of the global behavior of the systems or additional constraints sometimes require restricting this nondeterminism. Rewriting strategies are used as a higher-level and modular resource to cleanly capture these requirements, which can be easily expressed in Maude with an integrated strategy language. However, strategy-aware specifications cannot be verified with the builtin LTL model checker, making strategies less useful and attractive. In this paper, we discuss model checking for strategy-controlled systems, and present a strategy-aware extension of the Maude LTL model checker. The expressivity of the strategy language is discussed in relation to model checking, the model checker is illustrated with multiple application examples, and its performance is compared.
Docta Complutense
Publicación Artículo científico (JournalArticle)

Efficient Normalization of Linear Temporal Logic

  • Esparza, Javier
  • Rubio Cuéllar, Rubén Rafael
  • Salomon Sickert
In the mid 1980s, Lichtenstein, Pnueli, and Zuck proved a classical theorem stating that every formula of Past LTL (the extension of Linear Temporal Logic (LTL) with past operators) is equivalent to a formula of the form ⋀<sup>n</sup><sub>i=1</sub>GF φ<sub>i</sub> ∨ FG ψ<sub>i</sub> where φ<sub>i</sub> and ψ<sub>i</sub> contain only past operators. Some years later, Chang, Manna, and Pnueli built on this result to derive a similar normal form for LTL. Both normalization procedures have a non-elementary worst-case blow-up, and follow an involved path from formulas to counter-free automata to star-free regular expressions and back to formulas. We improve on both points. We present direct and purely syntactic normalization procedures for LTL, yielding a normal form very similar to the one by Chang, Manna, and Pnueli, that exhibit only a single exponential blow-up. As an application, we derive a simple algorithm to translate LTL into deterministic Rabin automata. The algorithm normalizes the formula, translates it into a special very weak alternating automaton, and applies a simple determinization procedure, valid only for these special automata.
Docta Complutense
Publicación Artículo científico (JournalArticle)

The Maude strategy language

  • Verdejo López, José Alberto
  • Eker, Steven
  • Martí Oliet, Narciso
  • Meseguer, José
  • Rubio Cuéllar, Rubén Rafael
Rewriting logic is a natural and expressive framework for the specification of concurrent systems and logics. The Maude specification language provides an implementation of this formalism that allows executing, verifying, and analyzing the represented systems. These specifications declare their objects by means of terms and equations, and provide rewriting rules to represent potentially non-deterministic local transformations on the state. Sometimes a controlled application of these rules is required to reduce non-determinism, to capture global, goal-oriented or efficiency concerns, or to select specific executions for their analysis. That is what we call a strategy. In order to express them, respecting the separation of concerns principle, a Maude strategy language was proposed and developed. The first implementation of the strategy language was done in Maude itself using its reflective features. After ample experimentation, some more features have been added and, for greater efficiency, the strategy language has been implemented in C++ as an integral part of the Maude system. This paper describes the Maude strategy language along with its semantics, its implementation decisions, and several application examples from various fields.
Docta Complutense
Publicación Artículo científico (JournalArticle)

Strategies, model checking and branching-time properties in Maude

  • Rubio Cuéllar, Rubén Rafael
  • Martí Oliet, Narciso
  • Pita Andreu, María Isabel
  • Verdejo López, José Alberto
Rewriting logic and its implementation Maude are a natural and expressive framework for the specification of concurrent systems and logics. Its nondeterministic local transformations are described by rewriting rules, which can be controlled at a higher level using a builtin strategy language added to Maude 3. This specification resource would not be of much interest without tools to analyze their models, so in a previous work, we extended the Maude LTL model checker to verify strategy-controlled systems. In this paper, CTL* and μ-calculus are added to the repertoire of supported logics, after discussing which adaptations are needed for branching-time properties. The new extension relies on some external model checkers that are exposed the Maude models through general and efficient connections, profitable for future extensions and further applications. The performance of these model checkers is compared.
Docta Complutense
Publicación Artículo científico (JournalArticle)

Maude2Lean: Theorem proving for Maude specifications using Lean

  • Rubio Cuéllar, Rubén Rafael
  • Riesco Rodríguez, Adrián
Maude is a specification language based on rewriting logic whose programs can be executed, model checked, and analyzed with other automated techniques, but not easily theorem proved. On the other hand, Lean is a modern proof assistant based on the calculus of inductive constructions with a wide library of reusable proofs and definitions. This paper presents a translation from the first formalism to the second, and the maude2lean tool that predictably derives a Lean program from a Maude module. Hence, theorems can be proved in Lean about Maude specifications.
Docta Complutense
Publicación Contribución de congreso (ConferenceOutput)

Specifying fairness constraints and model checking with non-intensional strategies

  • Rubio Cuéllar, Rubén Rafael
  • Martí Oliet, Narciso
  • Pita Andreu, María Isabel
  • Verdejo López, José Alberto
Strategies are a natural way of specifying constraints in a rewriting-based model. They are often expressed as executable programs in some strategy language that intensionally filter the possible next rewrites. Hence, they cannot capture restrictions of the model involving unbounded delays, like fairness, which are useful in many verification scenarios. In this paper, we propose a variation to the semantics of the Maude strategy language that allows expressing non-intensional strategies without recursion, in a way amenable for verification. Then we present an LTL model checker for this kind of strategies and discuss the corresponding problem for other logics.
Docta Complutense
Publicación Artículo científico (JournalArticle)

Metalevel transformation of strategies

  • Rubio Cuéllar, Rubén Rafael
  • Martí Oliet, Narciso
  • Pita Andreu, María Isabel
  • Verdejo López, José Alberto
In the reflective Maude specification language, based on rewriting logic, a strategy language has been introduced to control rule rewriting while avoiding complex and verbose metalevel programs. However, just as multiple levels of reflection are required for some metaprogramming tasks, reflective manipulation and generation of strategies are convenient in multiple situations. Some examples of reflective strategy transformations are presented, which implement special forms of evaluation or extend the strategy language while preserving its advantages.
Docta Complutense
Publicación Contribución de congreso (ConferenceOutput)

QMaude: Quantitative Specification and Verification in Rewriting Logic

  • Rubio Cuéllar, Rubén Rafael
  • Martí Oliet, Narciso
  • Pita Andreu, María Isabel
  • Verdejo López, José Alberto
In formal verification, qualitative and quantitative aspects are both relevant, and high-level formalisms are convenient to naturally specify the systems under study and their properties. In this paper, we present a framework for describing probabilistic models on top of nondeterministic specifications in the highly-expressive language Maude, based on rewriting logic. Quantitative properties can be checked and calculated on them using both probabilistic and statistical methods with external tools like PRISM, Storm, MultiVeSta, and custom implementations as backends. At the same time, the underlying nondeterministic system can be verified using the qualitative model-checking and deductive tools already available in Maude.