### Abstract

Original language | Undefined |
---|---|

Title of host publication | Proceedings of the 25th International Conference on Computer Aided Verification, CAV 2013 |

Editors | N. Sharygina, H. Veith |

Place of Publication | London |

Publisher | Springer |

Pages | 968-983 |

Number of pages | 18 |

ISBN (Print) | 978-3-642-39798-1 |

DOIs | |

State | Published - 13 Jul 2013 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer Verlag |

### Fingerprint

### Keywords

- FMT-MC: MODEL CHECKING
- METIS-296351
- subsumption
- inclusion abstraction
- Timed Automata
- UPPAAL
- opaal
- Parallel
- LTL
- LTSMIN
- LU abstraction
- liveness
- Model Checking
- Multi-Core
- NDFS
- Büchi emptiness
- IR-84627
- CNDFS
- EWI-23158

### Cite this

*Proceedings of the 25th International Conference on Computer Aided Verification, CAV 2013*(pp. 968-983). (Lecture Notes in Computer Science). London: Springer. DOI: 10.1007/978-3-642-39799-8_69

}

*Proceedings of the 25th International Conference on Computer Aided Verification, CAV 2013.*Lecture Notes in Computer Science, Springer, London, pp. 968-983. DOI: 10.1007/978-3-642-39799-8_69

**Multi-core emptiness checking of timed Büchi automata using inclusion abstraction.** / Laarman, Alfons; Olesen, Mads Chr.; Dalsgaard, Andreas; Larsen, K.G.; van de Pol, Jan Cornelis.

Research output: Scientific - peer-review › Conference contribution

TY - CHAP

T1 - Multi-core emptiness checking of timed Büchi automata using inclusion abstraction

AU - Laarman,Alfons

AU - Olesen,Mads Chr.

AU - Dalsgaard,Andreas

AU - Larsen,K.G.

AU - van de Pol,Jan Cornelis

PY - 2013/7/13

Y1 - 2013/7/13

N2 - This paper contributes to the multi-core model checking of timed automata (TA) with respect to liveness properties, by investigating checking of TA Büchi emptiness under the very coarse inclusion abstraction or zone subsumption, an open problem in this field. We show that in general Büchi emptiness is not preserved under this abstraction. However, we prove that some other structural properties are preserved. Solving the problem partly, we propose a variation of the classic nested depth-first search (NDFS) algorithm that takes advantage of these properties thereby exploiting inclusion abstraction. In addition, we extend the multi-core CNDFS algorithm with subsumption, providing the first parallel LTL model checking algorithm for timed automata. We prove both algorithms correct and show that other, more aggressive variations are incorrect. The algorithms are implemented in LTSmin, and experimental evaluations show the effectiveness and scalability of both contributions: subsumption halves the number of states in the real-world FDDI and CSMA case studies, and the multi-core algorithm yields speedups of up to 40 on a 48 cores.

AB - This paper contributes to the multi-core model checking of timed automata (TA) with respect to liveness properties, by investigating checking of TA Büchi emptiness under the very coarse inclusion abstraction or zone subsumption, an open problem in this field. We show that in general Büchi emptiness is not preserved under this abstraction. However, we prove that some other structural properties are preserved. Solving the problem partly, we propose a variation of the classic nested depth-first search (NDFS) algorithm that takes advantage of these properties thereby exploiting inclusion abstraction. In addition, we extend the multi-core CNDFS algorithm with subsumption, providing the first parallel LTL model checking algorithm for timed automata. We prove both algorithms correct and show that other, more aggressive variations are incorrect. The algorithms are implemented in LTSmin, and experimental evaluations show the effectiveness and scalability of both contributions: subsumption halves the number of states in the real-world FDDI and CSMA case studies, and the multi-core algorithm yields speedups of up to 40 on a 48 cores.

KW - FMT-MC: MODEL CHECKING

KW - METIS-296351

KW - subsumption

KW - inclusion abstraction

KW - Timed Automata

KW - UPPAAL

KW - opaal

KW - Parallel

KW - LTL

KW - LTSMIN

KW - LU abstraction

KW - liveness

KW - Model Checking

KW - Multi-Core

KW - NDFS

KW - Büchi emptiness

KW - IR-84627

KW - CNDFS

KW - EWI-23158

U2 - 10.1007/978-3-642-39799-8_69

DO - 10.1007/978-3-642-39799-8_69

M3 - Conference contribution

SN - 978-3-642-39798-1

T3 - Lecture Notes in Computer Science

SP - 968

EP - 983

BT - Proceedings of the 25th International Conference on Computer Aided Verification, CAV 2013

PB - Springer

ER -