Language Preservation Problems in Parametric Timed Automata - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Logical Methods in Computer Science Année : 2020

Language Preservation Problems in Parametric Timed Automata

Résumé

Parametric timed automata (PTA) are a powerful formalism to model and reason about concurrent systems with some unknown timing delays. In this paper, we address the (untimed) language- and trace-preservation problems: given a reference parameter valuation, does there exist another parameter valuation with the same untimed language, or with the same set of traces? We show that these problems are undecidable both for general PTA and for the restricted class of L/U-PTA, even for integer-valued parameters, or over bounded time. On the other hand, we exhibit decidable subclasses: 1-clock PTA, and 1-parameter deterministic L-PTA and U-PTA. We also consider robust versions of these problems, where we additionally require that the language be preserved for all valuations between the reference valuation and the new valuation.

Dates et versions

hal-02498022 , version 1 (04-03-2020)

Licence

Paternité

Identifiants

Citer

Étienne André, Didier Lime, Nicolas Markey. Language Preservation Problems in Parametric Timed Automata. Logical Methods in Computer Science, 2020, 16 (1), ⟨10.23638/LMCS-16⟩. ⟨hal-02498022⟩
127 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More