Global ETD Search

1	Contribution à la théorie des langages de tuiles / Contribution to the theory of tile languages Dubourg, Etienne 12 July 2016 (has links) Les tuiles sont des structures finies, linéaires ou arborescentes, possédantune notion de chevauchement. Elles sont utiles en informatique pourreprésenter des objets musicaux, comme étudié par Janin [2016]. Nous étudieronsles ensembles de tuiles, en particulier comme représentations d’objetsalgébriques, en se basant sur la théorie des semigroupes inversifs.Nos principaux objets d’étude seront les langages de tuiles, et les reconnaisseursappropriés, que l’on peut définir en adaptant aux tuiles des notionsbien connues sur les langages de mots. Nous nous intéresserons à la reconnaissancepar automate, en présentant des automates sur les tuiles linéaires etarborescentes. Nous remarquerons les limites de la puissance de tels automates.Tandis que la notion de reconnaissance par morphisme de monoïdes estinadaptée aux langages de tuiles, nous définirons celle de reconnaissabilité parprémorphisme, ou quasi-reconnaissabilité. Nous étudierons les liens entre quasireconnaissabilitéet reconnaissabilité par automate de tuile.Nous explorerons enfin les propriétés de clôtures de l’ensemble de langagesde tuiles reconnus par automate, et de ceux reconnus par prémorphisme. Ladernière partie sera essentiellement consacrée aux tuiles linéaires, et présenterale monoïde des décompositions restreintes, un outil pour le produit de langagesde tuiles linéaires. / Tiles are finite, linear or tree-like structures, with a notion of overlapping.In computer science, they offer a useful way to represent musical objects,as studied by Janin [2016]. We will study the sets of tiles, especially asrepresentations of algebraic objects, based on the theory of inverse semigroups.Our main focus will be languages of tiles, and the appropriate recognizers,than can be defined by the adaptation to tiles of well-known notions over languagesof words. We will look into the recognition by automata, by presentingautomata over linear and tree-like tiles. We will remark the limits of the powerof such automata.While the notion of recognizability by morphisms is unsuitable to languagesof tiles, we will define recognizability by premorphisms, or quasi-recognizability.We will study the links between quasi-recognizability and recognizability bytile automata.We will finally look into the closure properties of the set of tile languages recognizedby automata, and of the set of quasi-recognizable languages. The lastpart will be dedicated to linear tiles, and will present the monoid of restricteddecompositions, a tool for the product of linear tile languages. Tuiles Arbres à deux racines Langages Monoïdes inversifs Prémorphismes Monoïdes d’Ehresmann Automates de tuiles Tiles Birooted trees Languages Inverse monoids Premorphisms Ehresmann monoids Tile automata
2	On Weak Limits and Unimodular Measures Artemenko, Igor 14 January 2014 (has links) In this thesis, the main objects of study are probability measures on the isomorphism classes of countable, connected rooted graphs. An important class of such measures is formed by unimodular measures, which satisfy a certain equation, sometimes referred to as the intrinsic mass transport principle. The so-called law of a finite graph is an example of a unimodular measure. We say that a measure is sustained by a countable graph if the set of rooted connected components of the graph has full measure. We demonstrate several new results involving sustained unimodular measures, and provide thorough arguments for known ones. In particular, we give a criterion for unimodularity on connected graphs, deduce that connected graphs sustain at most one unimodular measure, and prove that unimodular measures sustained by disconnected graphs are convex combinations. Furthermore, we discuss weak limits of laws of finite graphs, and construct counterexamples to seemingly reasonable conjectures. tree automorphism group ball path connected component rooted birooted graph Cayley converges weakly extreme point mass transport principle involution invariance law neighbourhood orbit rigid subgraph unimodular unimodularity vertex-transitive walk weak limit weak convergence probability measure barred binary tree bi-infinite path first ancestor judicial lawless negligible stabilizer sustained strictly sustained random graph
3	On Weak Limits and Unimodular Measures Artemenko, Igor January 2014 (has links) In this thesis, the main objects of study are probability measures on the isomorphism classes of countable, connected rooted graphs. An important class of such measures is formed by unimodular measures, which satisfy a certain equation, sometimes referred to as the intrinsic mass transport principle. The so-called law of a finite graph is an example of a unimodular measure. We say that a measure is sustained by a countable graph if the set of rooted connected components of the graph has full measure. We demonstrate several new results involving sustained unimodular measures, and provide thorough arguments for known ones. In particular, we give a criterion for unimodularity on connected graphs, deduce that connected graphs sustain at most one unimodular measure, and prove that unimodular measures sustained by disconnected graphs are convex combinations. Furthermore, we discuss weak limits of laws of finite graphs, and construct counterexamples to seemingly reasonable conjectures. tree automorphism group ball path connected component rooted birooted graph Cayley converges weakly extreme point mass transport principle involution invariance law neighbourhood orbit rigid subgraph unimodular unimodularity vertex-transitive walk weak limit weak convergence probability measure barred binary tree bi-infinite path first ancestor judicial lawless negligible stabilizer sustained strictly sustained random graph

1

Page generated in 0.0297 seconds