The Experts below are selected from a list of 1956 Experts worldwide ranked by ideXlab platform

Patricia Bouyer - One of the best experts on this subject based on the ideXlab platform.

  • MFCS - Expressiveness of Updatable Timed Automata
    Lecture Notes in Computer Science, 2020
    Co-Authors: Patricia Bouyer, Catherine Dufourd, Emmanuel Fleury, Antoine Petit
    Abstract:

    Since their introduction by Alur and Dill, Timed automata have been one of the most widely studied models for real-time systems. The syntactic extension of so-called updatable Timed automata allows more powerful updates of clocks than the reset operation proposed in the original model. We prove that any language accepted by an updatable Timed Automaton (from classes where emptiness is decidable) is also accepted by a "classical" Timed Automaton. We propose even more precise results on bisimilarity between updatable and classical Timed automata.

  • Expressiveness of updatable Timed automata
    Lecture Notes in Computer Science, 2020
    Co-Authors: Patricia Bouyer, Catherine Dufourd, Emmanuel Fleury, Antoine Petit
    Abstract:

    Since their introduction by ALUR and DILL, Timed automata have been one of the most widely studied models for real-time systems. The syntactic extension of so-called updatable Timed automata allows more powerful updates of clocks than the reset operation proposed in the original model. We prove that any language accepted by an updatable Timed Automaton (from classes where emptiness is decidable) is also accepted by a classical Timed Automaton. We propose even more precise results on bisimilarity between updatable and classical Timed automata.

  • Efficient Timed Diagnosis Using Automata with Timed Domains
    Runtime Verification, 2018
    Co-Authors: Patricia Bouyer, Samy Jaziri, Nicolas Markey
    Abstract:

    We consider the problems of efficiently diagnosing and predicting what did (or will) happen in a partially-observable one-clock Timed Automaton. We introduce Timed sets as a formalism to keep track of the evolution of the reachable configurations over time, and use our previous work on automata over Timed domains to build a candidate diagnoser for our Timed Automaton. We report on our implementation of this approach compared to the approach of [Tripakis, Fault diagnosis for Timed automata, 2002].

  • Stochastic Timed automata
    Logical Methods in Computer Science, 2014
    Co-Authors: Nathalie Bertrand, Patricia Bouyer, Thomas Brihaye, Quentin Menet, Christel Baier, Marcus Groesser, Marcin Jurdziński
    Abstract:

    A stochastic Timed Automaton is a purely stochastic process defined on a Timed Automaton, in which both delays and discrete choices are made randomly. We study the almost-sure model-checking problem for this model, that is, given a stochastic Timed Automaton A and a property ϕ, we want to decide whether A satisfies ϕ with probability 1. In this paper, we identify several classes of automata and of properties for which this can be decided. The proof relies on the construction of a finite abstraction, called the thick graph, that we interpret as a finite Markov chain, and for which we can decide the almost-sure model-checking problem. Correctness of the abstraction holds when automata are almost-surely fair, which we show, is the case for two large classes of systems, single-clock automata and so-called weak-reactive automata. Techniques employed in this article gather tools from real-time verification and probabilistic verification, as well as topological games played on Timed automata.

  • CONCUR - Timed automata can always be made implementable
    CONCUR 2011 – Concurrency Theory, 2011
    Co-Authors: Patricia Bouyer, Nicolas Markey, Kim Guldstrand Larsen, Ocan Sankur, Claus Thrane
    Abstract:

    Timed automata follow a mathematical semantics, which assumes perfect precision and synchrony of clocks. Since this hypothesis does not hold in digital systems, properties proven formally on a Timed Automaton may be lost at implementation. In order to ensure implementability, several approaches have been considered, corresponding to different hypotheses on the implementation platform. We address two of these: A Timed Automaton is samplable if its semantics is preserved under a discretization of time; it is robust if its semantics is preserved when all timing constraints are relaxed by some small positive parameter. We propose a construction which makes Timed automata implementable in the above sense: From any Timed Automaton A, we build a Timed Automaton A′ that exhibits the same behaviour as A, and moreover A′ is both robust and samplable by construction.

Jianwen Su - One of the best experts on this subject based on the ideXlab platform.

  • augmenting the discrete Timed Automaton with other data structures
    Theoretical Computer Science, 2002
    Co-Authors: Oscar H Ibarra, Jianwen Su
    Abstract:

    We describe a general automata-theoretic approach for analyzing the verification problems of discrete Timed automata (i.e., Timed automata with integer-valued clocks) augmented with various data structures. Formally, let C be a class of nondeterministic machines with reversal-bounded counters and possibly other data structures (e.g., a pushdown stack, a queue, a read-write work-tape, etc.). Let A be a discrete Timed Automaton and M be a machine in b. Denote by A ⊕ M the combined Automaton, i.e., A augmented with M (in some precise sense to be defined). We show that if c has a decidable emptiness problem, then the (binary, forward, backward) reachability, safety, and invariance for A ⊕ M are solvable. We give examples of such c's and exhibit some new properties of discrete Timed automata that can be verified. We also briefly consider reachability in discrete Timed automata operating in parallel.

  • CIAA - Generalizing the Discrete Timed Automaton
    Implementation and Application of Automata, 2001
    Co-Authors: Oscar H Ibarra, Jianwen Su
    Abstract:

    We describe a general automata-theoretic approach for analyzing the verification problems (binary reachability, safety, etc.) of discrete Timed automata augmented with various data structures. We give examples of such data structures and exhibit some new properties of discrete Timed automata that can be verified. We also briefly consider reachability in discrete Timed automata operating in parallel.

  • generalizing the discrete Timed Automaton
    International Conference on Implementation and application of automata, 2000
    Co-Authors: Oscar H Ibarra, Jianwen Su
    Abstract:

    We describe a general automata-theoretic approach for analyzing the verification problems (binary reachability, safety, etc.) of discrete Timed automata augmented with various data structures. We give examples of such data structures and exhibit some new properties of discrete Timed automata that can be verified. We also briefly consider reachability in discrete Timed automata operating in parallel.

Zheng Guoliang - One of the best experts on this subject based on the ideXlab platform.

  • Compatibility between shared variable valuations in Timed Automaton network model-checking
    19th IEEE International Parallel and Distributed Processing Symposium, 2005
    Co-Authors: Zhao Jianhua, Li Xuandong, Zhou Xiuyi, Zheng Guoliang
    Abstract:

    Many real-time systems are modelled as Timed Automaton networks, which are parallel compositions of Timed automata. Those Timed automata interact with each other through shared variables and/or communication channels. In the literate, symbolic states with different shared variable valuations are treated as distinct ones. This paper presents a compatibility relation between shared variable valuations. Using this relation, the reachability analysis algorithm can avoid exploring all the states with different shared variable valuations. An algorithm is presented in this paper to detect compatible shared variable valuations. A compact data structure is also proposed to record the shared variable valuation sets found by this algorithm. Based on these results, an optimized reachability analysis algorithm is presented. Case studies show that our technique improves the space-efficiency of reachability analysis significantly.

  • IPDPS - Compatibility between shared variable valuations in Timed Automaton network model-checking
    19th IEEE International Parallel and Distributed Processing Symposium, 2005
    Co-Authors: Zhao Jianhua, Li Xuandong, Zhou Xiuyi, Zheng Guoliang
    Abstract:

    Many real-time systems are modelled as Timed Automaton networks, which are parallel compositions of Timed automata. Those Timed automata interact with each other through shared variables and/or communication channels. In the literate, symbolic states with different shared variable valuations are treated as distinct ones. This paper presents a compatibility relation between shared variable valuations. Using this relation, the reachability analysis algorithm can avoid exploring all the states with different shared variable valuations. An algorithm is presented in this paper to detect compatible shared variable valuations. A compact data structure is also proposed to record the shared variable valuation sets found by this algorithm. Based on these results, an optimized reachability analysis algorithm is presented. Case studies show that our technique improves the space-efficiency of reachability analysis significantly.

H. Wupper - One of the best experts on this subject based on the ideXlab platform.

  • Timed Automaton models for simple programmable logic controllers
    Proceedings of 11th Euromicro Conference on Real-Time Systems. Euromicro RTS'99, 1999
    Co-Authors: A. Mader, H. Wupper
    Abstract:

    We give Timed Automaton models for a class of Programmable Logic Controller (PLC) applications, that are programmed in a simple fragment of the language Instruction Lists as defined in the standard IEC 1131-3. Two different approaches for modelling timers are suggested, that lead to two different Timed Automaton models. The purpose of this work is to provide a basis for verification and testing of real-time properties of PLC applications. Our work can be seen in broader context: it is a contribution to methodical development of provably correct programs. Even if the present PLC hardware will be substituted by e.g. Personal Computers, with a similar operation mode, the development and verification method will remain useful.

  • ECRTS - Timed Automaton models for simple programmable logic controllers
    Proceedings of 11th Euromicro Conference on Real-Time Systems. Euromicro RTS'99, 1999
    Co-Authors: A. Mader, H. Wupper
    Abstract:

    We give Timed Automaton models for a class of Programmable Logic Controller (PLC) applications, that are programmed in a simple fragment of the language Instruction Lists as defined in the standard IEC 1131-3. Two different approaches for modelling timers are suggested, that lead to two different Timed Automaton models. The purpose of this work is to provide a basis for verification and testing of real-time properties of PLC applications. Our work can be seen in broader context: it is a contribution to methodical development of provably correct programs. Even if the present PLC hardware will be substituted by e.g. Personal Computers, with a similar operation mode, the development and verification method will remain useful.

Oscar H Ibarra - One of the best experts on this subject based on the ideXlab platform.

  • Past pushdown Timed automata
    Lecture Notes in Computer Science, 2020
    Co-Authors: Zhe Dang, Oscar H Ibarra, Tevfik Bultan, Richard A. Kemmerer
    Abstract:

    We consider past pushdown Timed automata that are discrete pushdown Timed automata [15] with past-formulas as enabling conditions. Using past formulas allows a past pushdown Timed Automaton to access the past values of the finite state variables in the Automaton. We prove that the reachability (i.e., the set of reachable configurations from an initial configuration) of a past pushdown Timed Automaton can be accepted by a nondeterministic reversal-bounded multicounter machine augmented with a pushdown stack (i.e., a reversal-bounded NPCM). Using the known fact that the emptiness problem for reversal-bounded NPCMs is decidable, we show that model-checking past pushdown Timed automata against Presburger safety properties on discrete clocks and stack word counts is decidable. An example ASTRAL specification is presented to demonstrate the usefulness of the results.

  • THE EXISTENCE OF ω-CHAINS FOR TRANSITIVE MIXED LINEAR RELATIONS AND ITS APPLICATIONS
    International Journal of Foundations of Computer Science, 2020
    Co-Authors: Zhe Dang, Oscar H Ibarra
    Abstract:

    We show that it is decidable whether a transitive mixed linear relation has an ω-chain. Using this result, we study a number of liveness verification problems for generalized Timed automata within a unified framework. More precisely, we prove that (1) the mixed linear liveness problem for a Timed Automaton with dense clocks, reversal-bounded counters, and a free counter is decidable, and (2) the Presburger liveness problem for a Timed Automaton with discrete clocks, reversal-bounded counters, and a pushdown stack is decidable.

  • augmenting the discrete Timed Automaton with other data structures
    Theoretical Computer Science, 2002
    Co-Authors: Oscar H Ibarra, Jianwen Su
    Abstract:

    We describe a general automata-theoretic approach for analyzing the verification problems of discrete Timed automata (i.e., Timed automata with integer-valued clocks) augmented with various data structures. Formally, let C be a class of nondeterministic machines with reversal-bounded counters and possibly other data structures (e.g., a pushdown stack, a queue, a read-write work-tape, etc.). Let A be a discrete Timed Automaton and M be a machine in b. Denote by A ⊕ M the combined Automaton, i.e., A augmented with M (in some precise sense to be defined). We show that if c has a decidable emptiness problem, then the (binary, forward, backward) reachability, safety, and invariance for A ⊕ M are solvable. We give examples of such c's and exhibit some new properties of discrete Timed automata that can be verified. We also briefly consider reachability in discrete Timed automata operating in parallel.

  • ISAAC - On Removing the Pushdown Stack in Reachability Constructions
    Algorithms and Computation, 2001
    Co-Authors: Oscar H Ibarra, Zhe Dang
    Abstract:

    A discrete pushdown Timed Automaton is a pushdown machine with integer-valued clocks. It has been shown recently that the binary reachability of a discrete pushdown Timed Automaton can be accepted by a 2-tape pushdown acceptor with reversal-bounded counters. We improve this result by showing that the stack can be removed from the acceptor, i.e., the binary reachability can be accepted by a 2-tape finite-state acceptor with reversal-bounded counters.We also obtain similar results for more general machine models. Our characterizations can be used to verify certain properties concerning these machines that were not verifiable before using previous techniques. We are also able to formulate a subset of Presburger LTL that is decidable for satisfiability-checking with respect to these machines.

  • The Existence of $\omega$-Chains for Transitive Mixed Linear Relations and Its Applications
    arXiv: Logic in Computer Science, 2001
    Co-Authors: Zhe Dang, Oscar H Ibarra
    Abstract:

    We show that it is decidable whether a transitive mixed linear relation has an $\omega$-chain. Using this result, we study a number of liveness verification problems for generalized Timed automata within a unified framework. More precisely, we prove that (1) the mixed linear liveness problem for a Timed Automaton with dense clocks, reversal-bounded counters, and a free counter is decidable, and (2) the Presburger liveness problem for a Timed Automaton with discrete clocks, reversal-bounded counters, and a pushdown stack is decidable.