Iterative Bounded Synthesis for Efficient Cycle Detection in Parametric Timed Automata

Étienne André (1, 2) , Jaime Arias (3) , Laure Petrucci (3) , Jaco van De Pol (4)

1 MOSEL - Proof-oriented development of computer-based systems
2 VERIDIS - Modeling and Verification of Distributed Algorithms and Systems
3 LIPN - Laboratoire d'Informatique de Paris-Nord
4 Aarhus University [Aarhus]

We study semi-algorithms to synthesise the constraints under which a Parametric Timed Automaton satisfies some liveness requirement. The algorithms traverse a possibly infinite parametric zone graph, searching for accepting cycles. We provide new search and pruning algorithms, leading to successful termination for many examples. We demonstrate the success and efficiency of these algorithms on a benchmark. We also illustrate parameter synthesis for the classical Bounded Retransmission Protocol. Finally, we introduce a new notion of completeness in the limit, to investigate if an algorithm enumerates all solutions.

Mots clés: Parameter Synthesis; Liveness Properties; IMITATOR

Domaines: Logique en informatique [cs.LO]

Étienne André, Jaime Arias, Laure Petrucci, Jaco van De Pol. Iterative Bounded Synthesis for Efficient Cycle Detection in Parametric Timed Automata. TACAS 2021 - 27th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, Jan Friso Groote; Kim G. Larsen, Mar 2021, virtual, Luxembourg. pp.311-329, ⟨10.1007/978-3-030-72016-2_17⟩. ⟨hal-03340887⟩