On the distance between timed automata

DOI10.1007/978-3-030-29662-9_12zbMATH Open1434.68287arXiv1909.10489OpenAlexW2969678322MaRDI QIDQ2176705FDOQ2176705

Publication date: 5 May 2020

Abstract: The problem of inclusion of the language accepted by timed automaton

A

(e.g., the implementation) in the language accepted by

B

(e.g., the specification) is, in general, undecidable in the class of non-deterministic timed automata. In order to tackle this disturbing problem we show how to effectively construct deterministic timed automata

A_{d}

and

B_{d}

that are discretizations (digitizations) of the non-deterministic timed automata

A

and

B

and differ from the original automata by at most

f r a c 16

time units on each occurrence of an event. Language inclusion in the discretized timed automata is decidable and it is also decidable when instead of

m a t h f r a k L (B)

we consider

o v e r l i n e m a t h f r a k L (B)

, the closure of

m a t h f r a k L (B)

in the Euclidean topology: if

m a t h f r a k L (A_{d}) s u b s e t e q m a t h f r a k L (B_{d})

then

m a t h f r a k L (A) s u b s e t e q m a t h f r a k L (B)

and if

m a t h f r a k L (A_{d}) s u b s e t e q m a t h f r a k L (B_{d})

then

m a t h f r a k L (A) s u b s e t e q o v e r l i n e m a t h f r a k L (B)

. Moreover, if

m a t h f r a k L (A_{d}) s u b s e t e q m a t h f r a k L (B_{d})

we would like to know how far away is

m a t h f r a k L (A_{d})

from being included in

m a t h f r a k L (B_{d})

. For that matter we define the distance between the languages of timed automata as the limit on how far away a timed trace of one timed automaton can be from the closest timed trace of the other timed automaton. We then show how one can decide under some restriction whether the distance between two timed automata is finite or infinite.

Full work available at URL: https://arxiv.org/abs/1909.10489

Recommendations

zbMATH Keywords

timed automata language inclusion distance between timed automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cited In (12)

This page was built for publication: On the distance between timed automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2176705)