Name
Abstract | ||
|---|---|---|
Concavely-priced probabilistic timed automata, an extension of probabilistic timed automata, are introduced. In this paper we consider expected reachability, discounted, and average price problems for concavely-priced probabilistic timed automata for arbitrary initial states. We prove that these problems are EXPTIME-complete for probabilistic timed automata with two or more clocks and PTIME-complete for automata with one clock. Previous work on expected price problems for probabilistic timed automata was restricted to expected reachability for linearly-priced automata and integer valued initial states. This work uses the boundary region graph introduced by Jurdziński and Trivedi to analyse properties of concavely-priced (non-probabilistic) timed automata. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-04081-8_28 | CONCUR |
Keywords | Field | DocType |
linearly-priced automaton,concavely-priced probabilistic timed automata,expected price problem,initial state,boundary region graph,average price problem,concavely-priced probabilistic,previous work,arbitrary initial state,expected reachability | Discrete mathematics,Quantum finite automata,Automata theory,Mobile automaton,Computer science,Automaton,Reachability,Theoretical computer science,Timed automaton,Probabilistic logic,ω-automaton | Conference |
Volume | ISSN | Citations |
5710 | 0302-9743 | 8 |
PageRank | References | Authors |
0.77 | 19 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marcin Jurdziński | 1 | 329 | 17.40 |
| Marta Z. Kwiatkowska | 2 | 6118 | 322.21 |
| Gethin Norman | 3 | 4163 | 193.68 |
| Ashutosh Trivedi | 4 | 149 | 28.08 |