HomeNewsCase StudiesPeoplePublications
[Bas15] N. Basset. Timed Symbolic Dynamics. In Sankaranarayanan, Sriram and Vicario, Enrico (editors), 13th International Conference on Formal Modeling and Analysis of Timed Systems (FORMATS'15), volume 9268 of LNCS, pages 44-59, Springer International Publishing. 2015. [pdf] [bib]
Downloads:  pdf pdf (428 KB)  bib bib
Notes: The original publication is available at link.springer.com.
Abstract. We introduce a theory of timed symbolic dynamics unifying results from timed automata theory and symbolic dynamics. The timed sofic shift spaces we define are a way of seeing timed regular languages as shift spaces on general alphabets (in classical symbolic dynamics, sofic shift spaces correspond to regular languages). We show that morphisms of shift spaces on general alphabets can be approximated by sliding block codes resulting in a generalised version of the so-called Curtis-Hedlund-Lyndon Theorem. We provide a new measure for timed languages by characterising the Gromov-Lindenstrauss-Weiss metric mean dimension for timed shift spaces and illustrate it on several examples. We revisit recent results on volumetry of timed languages in terms of timed symbolic dynamics. In particular we explain the discretisation of timed shift spaces and their entropy.