In this thesis examples of spectral triples, which represent fractal sets, are examined and new insights into their noncommutative geometries are obtained. Firstly, starting with Connes' spectral triple for a non-empty compact totally disconnected subset E of {R} with no isolated points, we develop a noncommutative coarse multifractal formalism. Specifically, we show how multifractal properties of a measure supported on E can be expressed in terms of a spectral triple and the Dixmier trace of certain operators. If E satisfies a given porosity condition, then we prove that the coarse multifractal box-counting dimension can be recovered. We show that for a self-similar measure μ, given by an iterated function system S defined on a compact subset of {R} satisfying the strong separation condition, our noncommutative coarse multifractal formalism gives rise to a noncommutative integral which recovers the self-similar multifractal measure ν associated to μ, and we establish a relationship between the noncommutative volume of such a noncommutative integral and the measure theoretical entropy of ν with respect to S. Secondly, motivated by the results of Antonescu-Ivan and Christensen, we construct a family of (1, +)-summable spectral triples for a one-sided topologically exact subshift of finite type (∑{{A}} {{N}}, σ). These spectral triples are constructed using equilibrium measures obtained from the Perron-Frobenius-Ruelle operator, whose potential function is non-arithemetic and Hölder continuous. We show that the Connes' pseudo-metric, given by any one of these spectral triples, is a metric and that the metric topology agrees with the weak*-topology on the state space {S}(C(∑{{A}} {{N}}); {C}). For each equilibrium measure ν[subscript(φ)] we show that the noncommuative volume of the associated spectral triple is equal to the reciprocal of the measure theoretical entropy of ν[subscript(φ)] with respect to the left shift σ (where it is assumed, without loss of generality, that the pressure of the potential function is equal to zero). We also show that the measure ν[subscript(φ)] can be fully recovered from the noncommutative integration theory.

This paper outlines and implements a systematic approach to the establishment, investigation, and testing of distances and topologies on language spaces. The collection of all languages over a given number of symbols forms a semiring, appropriately termed a language space. Families of languages are defined by interrelations among words. The traditional classification begins with the syntax rules or grammar of the language, that is, the word-transformations by which the entire language can be produced from a single axiom, or starting word. The study of distances between languages as objects and of the topologies induced by language distances upon spaces of languages has been of a limited character. Known language distances introduce topologically awkward features into a language space, such as total disconnectedness. This dissertation examines the topologies induced by three language distances, the effect that each one has upon the notion of a random language, and discusses continuity and word-distribution of structure-preserving language transformations, i.e., morphisms. This approach starts from metric-like requirements, but adduces an additional condition intuitively appropriate to gauging language distance. At the same time, strict, i.e. non-metric pseudometrics are admitted as possible language distance functions, and these are investigated by the use of metric quotient spaces. The study of the notion of randomness implied by the topology induced by such a pseudo-metric on a language space offers insight into the structure of language spaces and verifies the viability of the pseudo-metric. Three language pseudo-metrics are studied in this dissertation: a version of the most commonlyused (Cantor) word metric; an upper-density (Besicovitch) pseudo-metric borrowed from the study of cellular automata; and an adaptation and normalization of topological entropy, each evaluated on the symmetric set-difference between languages. It is shown that each of these distances induces a distinct topology on the space of languages. The topology induced by Cantor distance is compact and totally disconnected, the topologies induced by the other two are non-compact, with entropic distance resulting in a topology that is the strict refinement of the Besicovitch topology, enhancing the picture of the smaller languages in the Besicovitch topology. It is also shown that none of the three topologies gives quantitative expression to the distinction between regular and linear languages, although, using Martin-Lof randomness tests, it is shown that each pseudo-metric is associated with a new notion of a random language. A classification of language mappings is introduced, with the aim of identifying those which best preserve the structure of languages under specific topologies. There are results regarding continuity of mappings, the matrix representation of the pre-image of certain morphisms, and the formal expressions of the probability distribution of the image of certain morphism. The continuity of an injective morphism on its image is demonstrated under limited conditions. Finally, the questions which this approach leaves open are detailed. While basic facts about a permutation-invariant version of symmetric set difference are shown, this has yet to be fully elaborated. The outline is presented for a metric which distinguishes between regular and linear languages by brute force. Syntactic and as algebraic topological continuations of this approach await investigation. A variation of the Cantor distance is introduced, and this induces a non-Cantor topology on a language space. In summary, this dissertation demonstrates that it is possible to systematically topologize the formal language space, and, having done so, to determine the major effects this has upon the notion of random languages and upon language morphisms.

All physical systems are affected by some noise that limits the resolution that can be attained in partitioning their state space. For chaotic, locally hyperbolic flows, this resolution depends on the interplay of the local stretching/contraction and the smearing due to noise. My goal is to determine the `finest attainable' partition for a given hyperbolic dynamical system and a given weak additive white noise. That is achieved by computing the local eigenfunctions of the Fokker-Planck evolution operator in linearized neighborhoods of the periodic orbits of the corresponding deterministic system, and using overlaps of their widths as the criterion for an optimal partition. The Fokker-Planck evolution is then represented by a finite transition graph, whose spectral determinant yields time averages of dynamical observables. The method applies in principle to both continuous- and discrete-time dynamical systems. Numerical tests of such optimal partitions on unimodal maps support my hypothesis.

Models based on various types of automata are ubiquitous in modern science. These models allow reasoning about deep theoretical questions and provide a basis for the development of efficient algorithms to solve related computational problems. This work discusses several types of automata used in such models, including cellular automata and mandatory results automata. The first part of this work is dedicated to cellular automata. These automata form an important class of discrete dynamical systems widely used to model physical, biological, and chemical processes. Here we discuss a way to study the dynamics of one-dimensional cellular automata through the theory of two-dimensional picture languages. The connection between cellular automata and picture languages stems from the fact that the set of all space-time diagrams of a cellular automaton defines a picture language. We will discuss a hierarchy of cellular automata based on the complexity of the picture languages that they define. In addition to this, we present a characterization of cellular automata that can be described by finite-state transducers. The second part of this work presents a theory of runtime enforcement based on mech- anism models called Mandatory Results Automata (MRAs). MRAs can monitor and trans- form security-relevant actions and their results. Because previous work could not model general security monitors transforming results, MRAs capture realistic behaviors outside the scope of previous models. MRAs also have a simple but realistic operational seman- tics that makes it straightforward to define concrete MRAs. Moreover, the definitions of policies and enforcement with MRAs are significantly simpler and more expressive than those of previous models. Putting all these features together, we argue that MRAs make good general models of (synchronous) runtime mechanisms, upon which a theory of run- time enforcement can be based. We develop some enforceability theory by characterizing the policies deterministic and nondeterministic MRAs enforce.

Nous étudions dans cette thèse la notion de quasipériodicité,introduite par Apostolico et Ehrenfeucht au début des années 1990,puis étendue aux mots infinis par Solomon Marcus au début des années2000. Un mot (fini ou infini) w est quasipériodique s'il peut êtrecouvert par des occurrences, éventuellement chevauchantes, d'un autremot, fini, appelé sa quasipériode. En 2006, Monteil etMarcus ont introduit la notion plus forte de quasipériodicitémulti-échelles : le fait d'avoir une infinité de quasipériodes.Dans un premier temps, nous étudions la quasipériodicité des motsinfinis bidimensionnels. Nous montrons que, contrairement au casunidimensionnel où la quasipériodicité ne force aucune propriété fortedes mots infinis, il existe des quasipériodes q qui forcent les mots2D q-quasipériodiques à être d'entropie nulle. Nous montrons égalementque la quasipériodicité multi-échelles en deux dimensions forcel'existence de fréquences uniformes pour les facteurs.Dans un deuxième temps, nous donnons des résultats sur les motsinfinis en une dimension. Nous donnons notament une approchepermettant de déterminer les quasipériodes d'un mot infini à partir deses facteurs carrés et de ses facteurs spéciaux. Nous montrons ensuiteque la famille des mots périodiques, ainsi que celle des mots standardsturmiens, peuvent être caractérisées en termes de quasipériodicitémulti-échelles. / We study the notion of quasiperiodicity, introduced by Apostolico and Ehrenfeucht at the beginning of the 1990's, then extended to infinite words by Solomon Marcus at the beginning of the 2000's. A (finite or infinite) word w is quasiperiodic if it can be covered by occurrences, possibly overlapping, of another finite word, call its quasiperiod. In 2006, Monteil and Marcus introduced a stronger notion: multi-scale quasiperiodicity, the property of having infinitely many quasiperiods.First we study quasiperiodicity of two-dimensional infinite words. We show that, by contrast with the one-dimensional case where quasiperiodicity do not force any property on infinite words, there exist quasiperiods q which force 2D q-quasiperiodic words to have zero entropy. We also show that multi-scale quasiperiodicity in two dimension force the existence of uniform frequencies for factors.Then we give results on infinite words in one dimension. Most notably we give a method to determine the quasiperiods of an infinite words from its square and special factors. We show that the family of periodic words and standard Sturmian words are characterizable in terms of multi-scale quasiperiodicity.

In this thesis, we explore the interface between symbolic and dynamical system computation, with particular regard to dynamical system models of neuronal networks. In doing so, we adhere to a definition of computation as the physical realization of a formal system, where we say that a dynamical system performs a computation if a correspondence can be found between its dynamics on a vectorial space and the formal system’s dynamics on a symbolic space. Guided by this definition, we characterize computation in a range of neuronal network models. We first present a constructive mapping between a range of formal systems and Recurrent Neural Networks (RNNs), through the introduction of a Versatile Shift and a modular network architecture supporting its real-time simulation. We then move on to more detailed models of neural dynamics, characterizing the computation performed by networks of delay-pulse-coupled oscillators supporting the emergence of heteroclinic dynamics. We show that a correspondence can be found between these networks and Finite-State Transducers, and use the derived abstraction to investigate how noise affects computation in this class of systems, unveiling a surprising facilitatory effect on information transmission. Finally, we present a new dynamical framework for computation in neuronal networks based on the slow-fast dynamics paradigm, and discuss the consequences of our results for future work, specifically for what concerns the fields of interactive computation and Artificial Intelligence.

This paper studies symbolic dynamical systems {0, 1}G, where G is a countably infinite group, {0, 1}G has the product topology, and G acts on {0, 1}G by shifts. It is proven that for every countably infinite group G the union of the minimal free subflows of {0, 1}G is dense. In fact, a stronger result is obtained which states that if G is a countably infinite group and U is an open subset of {0, 1}G, then there is a collection of size continuum consisting of pairwise disjoint minimal free subflows intersecting U.

Cette thèse étudie la moyennabilité et la propriété de Liouville des groupes pleins-topologiques des systèmes de Cantor, des groupes d'échanges d'intervalles, et des groupes agissants sur les arbres enracinés. Dans le Chapitre 2, nous obtenons les premiers exemples de groupes simples, infinis, de type fini, tels que le bord de Poisson de toute marche aléatoire simple est trivial (la propriété de Liouville). Ces exemples sont des sous-groupes dérivés de groupes pleins topologiques d'une famille de sous-décalages minimaux. Nous montrons que si la complexité d'un sous-décalage (pas nécessairement minimal) est strictement sous-quadratique, toute mesure de probabilité symétrique de support fini sur le groupe plein-topologique est d'entropie asymptotique nulle. Dans le Chapitre 3, nous exhibons une famille de groupes pleins-topologiques de sous-décalages minimaux qui contiennent les groupes de Grigorchuk G_ω comme sous-groupes. Cette construction montre que le groupe plein-topologique d'un sous-décalage minimal peut avoir des sous-groupes de croissance intermédiaire, en répondant à une question de Grigorchuk. Dans le Chapitre 4 (basé sur un travail en commun avec K. Juschenko, N. Monod, M. de la Salle) nous étudions les actions extensivement moyennables, une notion qui est un outil pour montrer la moyennabilité des groupes. Comme application, nous montrons la moyennabilité des groupes d'échanges d'intervalles dont les angles de translations ont rang rationnel au plus 2. Nous obtenons aussi une caractérisation "de type Kesten" de la moyennabilité extensive d'une action, et nous l'utilisons pour donner une preuve courte, purement probabiliste du fait que les actions récurrentes sont extensivement moyennables. Nous étudions aussi la propriété de Liouville pour les groupes d'échanges d'intervalles, et nous montrons qu'il existe des groupes d'échanges d'intervalles tels que toute mesure de support fini non dégénérée a un bord non trivial. Dans le Chapitre 5 (basé sur un travail en commun avec G. Amir, O. Angel, B. Virág) nous montrons que les groupes agissant sur les arbres enracinés par automorphismes bornés ont la propriété de Liouville. En particulier cela inclut les groupes engendrés par des automates d'activité bornée. / This thesis deals with the Liouville property and amenability of topological full groups of Cantor systems, groups of interval exchanges, and groups acting on rooted trees. In Chapter 2, we provide the first examples of finitely generated, infinite simple groups that have trivial Poisson-Furstenberg boundary for simple random walks (the Liouville property). These arise as the derived subgroup of the topological full groups of a family of minimal subshifts. We show that if the complexity of a (non necessarily minimal) subshift grows strictly subquadratically, every symmetric and finitely supported probability measure on the topological full group has vanishing asymptotic entropy. In Chapter 3, we exhibit a family of topological full groups of minimal subshifts that contain Grigorchuk groups G_ω as subgroups. This shows that the topological full group of a minimal subshift can have subgroups of intermediate growth, answering a question of Grigorchuk. In Chapter 4 (based on a joint work with K. Juschenko, N. Monod, M. de la Salle), we study various features of extensively amenable group actions, a notion which is a tool to prove amenability of groups. As an application, we prove amenability of groups of interval exchanges whose angular components have rational rank at most 2. We also obtain a "Kesten-like" characterisation of extensive amenability in terms of the inverted orbit and use it give a short, probabilistic proof of the fact that recurrent actions are extensively amenable. Finally we study the Liouville property for groups of interval exchanges, and show that there are groups of interval exchanges that admit no finitely supported measure with trivial boundary. In Chapter 5 (based on a joint work with G. Amir, O. Angel, B. Virág), we establish the Liouville property for all groups acting on rooted trees by bounded automorphisms. This includes in particular groups generated by bounded automata. This strengthens results by various authors about amenability of these groups, some of which are based on proving the Liouville property in some special cases.

Symbolic dynamics is a current interest in the area of anomaly detection, especially in mechanical systems.  Symbolic dynamics reduces the overall dimensionality of system responses while maintaining a high level of robustness to noise.  Rolling element bearings are particularly common mechanical components where anomaly detection is of high importance.  Harsh operating conditions and manufacturing imperfections increase vibration innately reducing component life and increasing downtime and costly repairs.  This thesis presents a novel way to detect bearing vibrational anomalies through Symbolic Aggregate Approximation (SAX) in the two-dimensional time-frequency domain.  SAX reduces computational requirements by partitioning high-dimensional sensor data into discrete states.  This analysis specifically suits bearing vibration data in the time-frequency domain, as the distribution of data does not greatly change between normal and faulty conditions. Under ground truth synthetically-generated experiments, two-dimensional SAX in conjunction with Markov model feature extraction is successful in detecting anomalies (> 99%) using short time spans (< 0.1 seconds) of data in the time-frequency domain with low false alarms (< 8%).  Analysis of real-world datasets validates the performance over the commonly used one-dimensional symbolic analysis by detecting 100% of experimental anomalous vibration with 0 false alarms in all fault types using less than 1 second of data for the basis of 'normality'. Two-dimensional SAX also demonstrates the ability to detect anomalies in predicative monitoring environments earlier than previous methods, even in low Signal-to-Noise ratios. / Master of Science

We model hyperbolic toral automorphisms by two types of Smale spaces; shifts of finite type and substitution tilings spaces. Smale spaces are dynamical systems with local hyperbolic product structure. In 1970, Bowen showed that an irreducible Smale space is a factor of a shift of finite type by showing that it has Markov partitions. Putnam extended Bowen's theorem by showing that every irreducible Smale space has a factor map that can be split into a s-bijective and u-bijective map; thereby better modelling a Smale space on its characterizing expanding and contracting spaces separately. In this thesis, we define two new constructions of Markov partitions for hyperbolic toral automorphisms inspired by the work of Adler, Weiss, and Praggastis. With one of the constructions, we investigate when a factor map from a shift of finite type to a hyperbolic toral automorphism can be written as a composition of a s-bijective and u-bijective map and we show that if such a splitting exists then the Markov partition must satisfy a Border Continuity condition. The second construction can be thought of as an explicit example of Putnam's theorem for the case of hyperbolic toral automorphisms whose defining matrix is in dimension 2 and has positive entries. We define a full splitting for all such hyperbolic toral automorphisms with one exception; the Arnold Cat map. / Graduate