Name
Abstract | ||
|---|---|---|
We propose a new efficient algorithm for detecting if a cycle in a timed automaton can be iterated infinitely often. Existing methods for this problem have a complexity which is exponential in the number of clocks. Our method is polynomial: it essentially does a logarithmic number of zone canonicalizations. This method can be incorporated in algorithms for verifying B\"uchi properties on timed automata. We report on some experiments that show a significant reduction in search space when our iteratability test is used. |
Year | Venue | Field |
|---|---|---|
2014 | CoRR | Discrete mathematics,Exponential function,Polynomial,Automaton,Algorithm,Timed automaton,Logarithm,Iterated function,Mathematics |
DocType | Volume | Citations |
Journal | abs/1410.4509 | 1 |
PageRank | References | Authors |
0.36 | 2 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aakash Deshpande | 1 | 1 | 0.36 |
| Frédéric Herbreteau | 2 | 64 | 8.47 |
| B. Srivathsan | 3 | 39 | 5.90 |
| Thanh-Tung Tran | 4 | 4 | 1.44 |
| Igor Walukiewicz | 5 | 1239 | 90.24 |