Name
Abstract | ||
|---|---|---|
Timed automata (TAs) represent a powerful formalism to model and verify systems where concurrency is mixed with hard timing constraints. However, they can seem limited when dealing with uncertain or unknown timing constants. Several parametric extensions were proposed in the literature, and the vast majority of them leads to the undecidability of the EF-emptiness problem: "is the set of valuations for which a given location is reachable empty?" Here, we study an extension of TAs where clocks can be updated to a parameter. While the EF-emptiness problem is undecidable for rational-valued parameters, it becomes PSPACE-complete for integer-valued parameters. In addition, exact synthesis of the parameter valuations set can be achieved. We also extend these two results to the EF-universality ("are all valuations such that a given location is reachable?"), AF-emptiness ("is the set of valuations for which a given location is unavoidable empty?") and AF-universality ("are all valuations such that a given location is unavoidable?") problems. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1109/ACSD.2018.000-2 | 2018 18th International Conference on Application of Concurrency to System Design (ACSD) |
Keywords | Field | DocType |
parametric timed automata,parameter synthesis,reachability emptiness,decidability | Computer science,Concurrency,Automaton,Theoretical computer science,Parametric statistics,Concurrent computing,Formalism (philosophy),Cost accounting,Semantics,Undecidable problem | Conference |
ISSN | ISBN | Citations |
1550-4808 | 978-1-5386-7014-9 | 0 |
PageRank | References | Authors |
0.34 | 14 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Étienne André | 1 | 294 | 35.08 |
| didier lime | 2 | 787 | 46.02 |
| Mathias Ramparison | 3 | 2 | 1.71 |