Stochastic Timed Automata
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 $\Phi$, we want to decid...
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2014-12-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/1092/pdf |
| _version_ | 1827322902041591808 |
|---|---|
| author | Nathalie Bertrand Patricia Bouyer Thomas Brihaye Quentin Menet Christel Baier Marcus Groesser Marcin Jurdzinski |
| author_facet | Nathalie Bertrand Patricia Bouyer Thomas Brihaye Quentin Menet Christel Baier Marcus Groesser Marcin Jurdzinski |
| author_sort | Nathalie Bertrand |
| collection | DOAJ |
| description | 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 $\Phi$, we want to decide whether
A satisfies $\Phi$ 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. |
| first_indexed | 2024-04-25T01:36:10Z |
| format | Article |
| id | doaj.art-f92695f2a20e4670973631558ddb9c08 |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:36:10Z |
| publishDate | 2014-12-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-f92695f2a20e4670973631558ddb9c082024-03-08T09:37:58ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742014-12-01Volume 10, Issue 410.2168/LMCS-10(4:6)20141092Stochastic Timed AutomataNathalie Bertrandhttps://orcid.org/0000-0002-9957-5394Patricia BouyerThomas BrihayeQuentin MenetChristel Baierhttps://orcid.org/0000-0002-5321-9343Marcus GroesserMarcin JurdzinskiA 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 $\Phi$, we want to decide whether A satisfies $\Phi$ 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.https://lmcs.episciences.org/1092/pdfcomputer science - logic in computer science |
| spellingShingle | Nathalie Bertrand Patricia Bouyer Thomas Brihaye Quentin Menet Christel Baier Marcus Groesser Marcin Jurdzinski Stochastic Timed Automata Logical Methods in Computer Science computer science - logic in computer science |
| title | Stochastic Timed Automata |
| title_full | Stochastic Timed Automata |
| title_fullStr | Stochastic Timed Automata |
| title_full_unstemmed | Stochastic Timed Automata |
| title_short | Stochastic Timed Automata |
| title_sort | stochastic timed automata |
| topic | computer science - logic in computer science |
| url | https://lmcs.episciences.org/1092/pdf |
| work_keys_str_mv | AT nathaliebertrand stochastictimedautomata AT patriciabouyer stochastictimedautomata AT thomasbrihaye stochastictimedautomata AT quentinmenet stochastictimedautomata AT christelbaier stochastictimedautomata AT marcusgroesser stochastictimedautomata AT marcinjurdzinski stochastictimedautomata |