Project topics and materials
Get Complete Project Material File(s) Now! »
Link between BDTA and TRGs (technical section).
The content of this section will not be used in the rest of the thesis. It just explains how to pass from BDTA to its underlying TRG without changing the entropy. The proof of Proposition 5 is also given here. This section can be skipped by a reader not interested by technical developments.
This section goes as follows: firstly we recall the region-splitting transformation of a BDTA [AD09a]. The region-split form of a BDTA A is a BDTA A′ with the same entropy which admits a region decomposition of the state space. Secondly, we define the underlying TRG of a region-split BDTA and show that entropy of both objects coincide. Thirdly we recall the equations of timed languages and volume functions [AD09a] for region-split BDTAm(which fit also TRGs). Finally we prove that the different notions of entropies associated to a TRG coincide.
Technical challenges
Getting rid of the D-WPC In our recent work [ABD13], we manage to prove the existence of a spectral gap for Ψ without assuming the D-weak progress condition. We think that such a spectral gap suffices to have existence and uniqueness of a maximal entropy SPOR. Nevertheless the functional space of continuous function used in [ABD13] has a dual space which is less intuitive to use (at least for the author) than L2(S), e.g. the meaning of w in this functional space is still to be understood. Computing ρ, v,w The next question is to know how simulation can be realized in practice. Symbolic computations of ρ and v have been proposed in [AD09a] for subclasses of deterministic TA, the algorithm can be adapted to compute w. In the same article, an iterative procedure is also given to estimate the entropy H = log2(ρ). We prove in [ABD13] that this procedure converges exponentially fast due to the presence of the spectral gap mentioned above. We think that approximations of ρ, v and w using an iterative procedure on Ψ and Ψ∗ would give a SPOR with entropy as close to the maximum as we want. However, several challenges remain to be solved. As described above, we must clarify the link between the present work and [ABD13] and understand for instance what would be the iterates of Ψ∗. Another technical hypothesis we want to get rid of is the decomposition of the state space in regions. This decomposition can lead to an exponential blow-up of the size of the model. In works on timed automata, regions are often replaced by zones which are in practice far less numerous. It is a challenging task for us to define Ψ and then the maximal entropy stochastic process Y ∗ on a state space decomposed in zones.
Classical symbolic dynamics
In this section Σ is a finite alphabet which is the simplest case of compact alphabet. The theory of finite alphabet shift spaces is the core of symbolic dynamics. A broad part of this theory can be explained in an elementary manner with characterization of the principal objects (shift space, entropy, conjugacy …) based on finite factors and without referring to topology (see [LM95]). We will lift to the timed case several results of this section.
Table of contents :
R´esum´e introductif en fran¸cais.
1 Introduction
1.1 Contributions, extended outline
1.2 Related work
1.2.1 Classical results lifted to the timed case.
1.2.2 Timed automata related works
1.2.3 Combinatorics
1.3 Past and ongoing publications
2 Preliminaries
2.1 Basics definitions
2.1.1 Timed languages
2.1.2 Bounded Deterministic Timed Automata
2.1.3 Timed region graphs
2.2 Advanced preliminaries
2.2.1 Paths, polytopes and point to point reachability.
2.2.2 Closed version of a timed region graph
2.2.3 SCC decomposition
2.2.4 Volume and entropy of runs
2.3 Link between BDTA and TRGs (technical section).
2.3.1 The region-splitting of [AD09a]
2.3.2 BDTAs and TRGs have the same entropy
2.3.3 Proof of Proposition
2.3.4 Recurrent equations on volume functions [AD09a]
3 Thin and Thick languages
3.1 Preliminaries
3.1.1 Thinness, simplices and examples
3.1.2 Point to point reachability: algebraic characterization
3.1.3 Linear Lyapunov functions and sub-exponential volume.
3.2 Main section
3.2.1 Pumping lemma for long thick paths
3.2.2 Characterizing thick languages
3.2.3 Thin and thick SCC
3.3 Conclusion and perspectives
4 The maximal entropy SPOR.
4.1 Maximal entropy Markov chain on a graph
4.1.1 Markov chain on a graph
4.1.2 Ergodic stochastic processes
4.1.3 Entropies
4.1.4 The asymptotic equipartition property for Markov-chain
4.1.5 The Shannon-Parry Markov chain
4.2 Stochastic processes on timed region graphs
4.2.1 SPOR of a timed region graph
4.2.2 Entropy
4.3 The maximal entropy SPOR
4.3.1 Technical assumptions
4.3.2 Main theorems
4.3.3 Definition and properties of ρ, v and w
4.3.4 Examples
4.3.5 Proof of the maximal entropy theorem (Theorem 14)
4.4 Conclusion and perspectives
4.4.1 Technical challenges
5 Timed symbolic dynamics
5.1 Preliminaries
5.1.1 Words and factors
5.1.2 Topology
5.1.3 Shift spaces
5.1.4 ε-entropies and topological entropy
5.2 Classical symbolic dynamics
5.2.1 Characterization with finite factors
5.2.2 Edge and sofic shifts
5.2.3 The language point of view.
5.3 Compact alphabet shift space
5.3.1 Factor based characterization of shift spaces.
5.3.2 An infinite topological entropy
5.3.3 Entropy of a mesurable shift
5.3.4 Keeping the ε-entropy
5.4 Timed edge shift and timed sofic shift
5.4.1 Definitions
5.4.2 The timed language point of view
5.4.3 Discretization
5.4.4 Metric mean dimension
5.5 Sliding block codes
5.6 Conclusion and perspectives
5.6.1 Open problems
6 Toward a Timed Theory of Channel Coding
6.1 Theory of channel coding for finite alphabet languages
6.1.1 Terminology
6.1.2 Coding: the basic case
6.1.3 Other coding settings
6.2 Timed coding
6.2.1 Timed source, discrete channel, approximate transmission
6.2.2 Timed source, timed channel, exact transmission
6.2.3 A variant: scaling allowed
6.2.4 A speedup and a slowdown lead to a collapse
6.3 Conclusion and perspectives
7 Generating functions of timed languages
7.1 Preliminaries
7.1.1 Clock languages and timed languages
7.1.2 From timed automata to triplet, clock and timed languages
7.1.3 Volume(s) of timed and clock languages
7.2 Generating functions
7.2.1 Definitions
7.2.2 Analytic characterization
7.2.3 Volumes, generating functions and functional analysis
7.2.4 Inductive characterization of generating functions
7.3 Computing generating functions
7.3.1 Generating functions for particular classes of automata
7.4 Conclusion and perspectives
8 Combinatorics using timed languages
8.1 Two problem statements
8.2 A timed and geometric approach
8.2.1 Order sets of a language of signatures (On(L))n≥1
8.2.2 Timed semantics of a language of signatures (L′n)n∈N
8.2.3 Volume preserving transformation between L′n and On(L).
8.2.4 The S-T (timed) language encoding.
8.3 Solving the two problems
8.3.1 Characterization of the VGF of an S-T-automaton.
8.3.2 An algorithm for Problem 2
8.4 Examples
8.4.1 The alternating permutations
8.4.2 The up-up-down-down permutations
8.4.3 Permutations without two consecutive descents
8.5 Conclusion and perspectives
9 Conclusion and perspectives
Bibliography
