Skip to Main content Skip to Navigation
Conference papers

Thin and Thick Timed Regular Languages

Abstract : In previous literature on timed automata, it was noticed that they are in several aspects too precise, which leads sometimes to strange artifacts, mathematical pathologies or unrealistic models. In particular, some timed automata are non-implementable, non-robust, behave badly under discretization, have many Zeno runs etc. In this paper, we propose a unifying approach to most of these issues for deterministic timed automata. We classify these automata either as thin or as thick. In thin automata, all the infinite trajectories are, in some weak sense, Zeno; the discretization of long trajectories is difficult, since it requires very small discretization step. In thick automata, most of trajectories are non-Zeno and behave well under discretization; such automata satisfy a sort of pumping lemma. Formally, the thin-thick alternative is based on the notion of entropy of timed regular languages introduced by E. Asarin and A. Degorre in [3,4]. Thin languages have the entropy = − ∞ while thick have a larger one. An important application of thin-thick alternative is again the entropy theory of timed languages. We show that the entropy can be computed with a desired precision using discretization and thus it is computable, which closes a question left open in [3,4].
Document type :
Conference papers
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00793583
Contributor : Nicolas Basset <>
Submitted on : Thursday, July 24, 2014 - 12:05:30 PM
Last modification on : Friday, March 27, 2020 - 3:06:37 AM
Long-term archiving on: : Monday, November 17, 2014 - 3:46:56 PM

File

FORMATS11.pdf
Files produced by the author(s)

Identifiers

Citation

Nicolas Basset, Eugene Asarin. Thin and Thick Timed Regular Languages. FORMATS, Sep 2011, Netherlands. pp.113-128, ⟨10.1007/978-3-642-24310-3_9⟩. ⟨hal-00793583⟩

Share

Metrics

Record views

498

Files downloads

672