Revised Version 2 of "Dynamic Real-Time CEGAR for Timed Automata Created and Destroyed at Run Time"

This paper makes two contributions to the verification of timed automata by counterexample-guided abstraction refinement (CEGAR) with predicate abstraction. The first is a sound and terminating CEGAR loop for networks of timed automata that are created and destroyed at run time, as in dynamically reconfigurable processors, so that the set of clocks changes along an execution. Abstract counterexamples are checked by an exact backward zone analysis with the new zone operations Add and Del, and we prove that every set it computes is a union of clock regions, which guarantees progress of refinement; incremental re-exploration, sequence interpolation, and breadth-first abstract search preserve these guarantees. The bound on the number of refinements depends only on the clocks of running automata. The second contribution is empirical: with a single implementation, in which every counterexample is replayed by an independent simulator, we identify the class of models on which the abstraction pays off. When independently reset clocks run periodically under equality guards and the property does not depend on their phase difference, the numbers of predicates and abstract states stay constant as the timing constants grow by three orders of magnitude, whereas exact zone exploration grows proportionally and becomes up to 9500 times slower, also on an ARINC 653 partition schedule from the literature, on which TChecker and Theta grow as well. The effect stems from predicate abstraction, not from dynamic creation. Outside this class, exact exploration remains faster, although breadth-first abstract search finds many counterexamples in far fewer iterations.

Authors

Institutions

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-13
DOI
https://doi.org/10.5281/zenodo.24182375
Primary Topic
Formal Methods in Verification
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Revised Version 2 of "Dynamic Real-Time CEGAR for Timed Automata Created and Destroyed at Run Time"

Satoshi Yamane
3 links
Zenodo (CERN European Organization for Nuclear Research)
Formal Methods in Verification
article

Revised Version 2 of "Dynamic Real-Time CEGAR for Timed Automata Created and Destroyed at Run Time"

Satoshi Yamane
article en

Abstract

This paper makes two contributions to the verification of timed automata by counterexample-guided abstraction refinement (CEGAR) with predicate abstraction. The first is a sound and terminating CEGAR loop for networks of timed automata that are created and destroyed at run time, as in dynamically reconfigurable processors, so that the set of clocks changes along an execution. Abstract counterexamples are checked by an exact backward zone analysis with the new zone operations Add and Del, and we prove that every set it computes is a union of clock regions, which guarantees progress of refinement; incremental re-exploration, sequence interpolation, and breadth-first abstract search preserve these guarantees. The bound on the number of refinements depends only on the clocks of running automata. The second contribution is empirical: with a single implementation, in which every counterexample is replayed by an independent simulator, we identify the class of models on which the abstraction pays off. When independently reset clocks run periodically under equality guards and the property does not depend on their phase difference, the numbers of predicates and abstract states stay constant as the timing constants grow by three orders of magnitude, whereas exact zone exploration grows proportionally and becomes up to 9500 times slower, also on an ARINC 653 partition schedule from the literature, on which TChecker and Theta grow as well. The effect stems from predicate abstraction, not from dynamic creation. Outside this class, exact exploration remains faster, although breadth-first abstract search finds many counterexamples in far fewer iterations.

Zenodo (CERN European Organization for Nuclear Research)
Shimonoseki City University (JP)
Formal Methods in Verification
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon