Étienne André ; Didier Lime ; Nicolas Markey - Language Preservation Problems in Parametric Timed Automata

lmcs:4700 - Logical Methods in Computer Science, January 22, 2020, Volume 16, Issue 1 - https://doi.org/10.23638/LMCS-16(1:5)2020
Language Preservation Problems in Parametric Timed Automata

Authors: Étienne André ; Didier Lime ; Nicolas Markey

    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.


    Volume: Volume 16, Issue 1
    Published on: January 22, 2020
    Accepted on: January 14, 2020
    Submitted on: July 20, 2018
    Keywords: Computer Science - Logic in Computer Science
    Financement :
      Source : OpenAIRE Graph
    • EQualIS : Enhancing the Quality of Interacting Systems; Funder: European Commission; Code: 308087
    • Collective Adaptive System SynThesIs with Non-zero-sum Games; Funder: European Commission; Code: 601148
    • Parametric Analysis of Concurrent Systems; Funder: French National Research Agency (ANR); Code: ANR-14-CE28-0002

    Linked data

    Source : ScholeXplorer HasVersion DOI 10.48550/arxiv.1807.07091
    • 10.48550/arxiv.1807.07091
    Language Preservation Problems in Parametric Timed Automata
    André, Étienne ; Lime, Didier ; Markey, Nicolas ;

    4 Documents citing this article

    Consultation statistics

    This page has been seen 675 times.
    This article's PDF has been downloaded 294 times.