Spelling suggestions: "subject:"régulier"" "subject:"régulière""
21 |
Some aspects on sweeping processes / Quelques résultats sur les processus de rafleLatreche, Wissam 10 July 2018 (has links)
Dans cette thèse, on s'intéresse à l'étude d'existence de solutions pour les processus de rafle. Ce problème prend la forme d'une inclusion différentielle contrainte avec des cônes normaux qui apparaissent naturellement dans nombreuses applications telles que le mouvement de foule, l'élastoplasticité, les mécaniques, les circuits électroniques, etc. L'objective de ce travail est de rapprocher deux importantes classes d'inclusions différentielles. D'une part, nous établissons quelques résultats d'existence de tube-solutions pour des processus de rafle à des ensembles uniformément prox-réguliers. D'autre part, nous présentons des résultats d'existence de solutions monotone par rapport à un préordre pour un système mixte d'inclusions différentielles projetées. De plus, nous montrons l'existence d'un point-selle pour notre système et nous fournissons deux exemples d'applications. / In this thesis, we were interested in the study of the existence of solutions for sweeping processes. This problem takes the form of a constrained differential inclusion involving normal cones which appears naturally in many applications such as crowd motion, elastoplasticity, mechanics, electrical circuit, etc.The aim of this work is to bring together two classes of differential inclusions. On one hand, we establish some existence results of solutions-tube for sweeping processes with uniformly prox-regular sets. On the other hand, we present existence results of monotone solutions with respect to a preorder for a mixed system of projected differential inclusions. In addition, we show that our system has a saddle-point and we provide two examples of applications.
|
22 |
Ergodicité et fonctions propres du laplacien sur les grands graphes réguliers / Ergodicity and eigenfunctions of the Laplacian on large regular graphsLe Masson, Etienne 24 September 2013 (has links)
Dans cette thèse, nous étudions les propriétés de concentration des fonctions propres du laplacien discret sur des graphes réguliers de degré fixé dont le nombre de sommets tend vers l'infini. Cette étude s'inspire de la théorie de l'ergodicité quantique sur les variétés. Par analogie avec cette dernière, nous développons un calcul pseudo-différentiel sur les arbres réguliers : nous définissons des classes de symboles et des opérateurs associés, et nous prouvons un certain nombre de propriétés de ces classes de symboles et opérateurs. Nous montrons notamment que les opérateurs sont bornés dans L², et nous donnons des formules de l'adjoint et du produit. Nous nous servons ensuite de cette théorie pour montrer un théorème d'ergodicité quantique pour des suites de graphes réguliers dont le nombre de sommets tend vers l'infini. Il s'agit d'un résultat de délocalisation de la plupart des fonctions propres dans la limite des grands graphes réguliers. Les graphes vérifient une hypothèse d'expansion et ne comportent pas trop de cycles courts, deux hypothèses vérifiées presque sûrement par des suites de graphes réguliers aléatoires. / N this thesis, we study concentration properties of eigenfunctions of the discrete Laplacian on regular graphs of fixed degree, when the number of vertices tend to infinity. This study is made in analogy with the Quantum Ergodicity theory on manifolds. We construct a pseudo-differential calculus on regular trees by defining symbol classes and associated operators and proving some properties of these classes of symbols and operators. In particular we prove that the operators are bounded on L² and give adjoint and product formulas. We then use this theory to prove a Quantum Ergodicity theorem on large regular graphs. This is a property of delocalization of most eigenfunctions in the large scale limit. We consider expander graphs with few short cycles (for instance random large regular graphs). These hypothesis are almost surely satisfied by sequences of random regular graphs.
|
23 |
Émergence et évolution des objets mathématiques en Situation Didactique de Recherche de Problème : le cas des pavages archimédiens du plan / Emergence and evolution of mathematical objects, during a “ Didactical Situation of a Problem Solving ” : the Case of Archimedean tilings of the planeFront, Mathias 27 November 2015 (has links)
Étudier l'émergence de savoirs lors de situations didactiques non finalisées par un savoir préfabriqué et pré-pensé nécessite un bouleversement des points de vue, aussi bien épistémologique que didactique. C'est pourquoi, pour l'étude de situations didactiques pour lesquelles le problème est l'essence, nous développons une nouvelle approche historique et repensons des outils pour les analyses didactiques. Nous proposons alors, pour un problème particulier, l'exploration des pavages archimédiens du plan, une enquête historique centrée sur l'activité du savant cherchant et sur l'influence de la relation aux objets dans la recherche. De ce point de vue, l'étude des travaux de Johannes Kepler à la recherche d'une harmonie du monde est particulièrement instructive. Nous proposons également, pour l'analyse des savoirs émergents en situation didactique, une utilisation d'outils liés à la sémiotique qui permet de mettre en évidence la dynamique de l'évolution des objets mathématiques. Nous pouvons finalement conclure quant à la possibilité de construire et mettre en œuvre des ≪ Situations Didactiques de Recherche de Problème ≫ assurant l'engagement du sujet dans la recherche, l'émergence et le développement d'objets mathématiques, la genèse de savoirs. L'étude nous conforte dans la nécessité d'une approche pragmatique des situations et la pertinence d'un regard différent sur les savoirs à l'école / The study of the emergence of knowledges in teaching situations not finalized by a prefabricated and pre-thought knowledge requires an upheaval of point of view, epistemological as well as didactic. For the study of learning situations in which the problem is the essence, we develop a new historical approach and we rethink the tools for didactic analyzes. We propose, then, for a particular problem, exploration of Archimedean tilings of the plane, a historical inquiry centered on the activity of the scientist in the process of research and on the influence of the relationship with objects. From this perspective, the study of Johannes Kepler’s work in search of a world harmony is particularly instructive. We also propose, for the analysis of the emerging knowledge in teaching situations, to use tools related to semiotics, which allows to highlight the dynamic of evolution of mathematical objects. We can finally conclude on the opportunity to build and implement “Didactic Situations of Problem Solving”, which ensure the commitment of the subject in the research, the emergence and development of mathematical objects, the genesis of knowledges. The study reinforces the necessity of a pragmatic approach of situations and the relevance of a different look at the knowledge at school
|
24 |
Les nombres de Catalan et le groupe modulaire PSL2(Z) / Catalan Numbers and the modular group PSL2(Z)Guichard, Christelle 29 October 2018 (has links)
Dans ce mémoire de thèse, on étudie le morphisme de monoïde $mu$du monoïde libre sur l'alphabet des entiers $nb$,`a valeurs dans le groupe modulaire $PSL_2(zb)$,considéré comme monoïde, défini pour tout entier $a$ par $mu(a)=begin{pmatrix} 0 & -1 1 & a+1 end{pmatrix}.$Les nombres de Catalan apparaissent naturellement dans l'étudede sous-ensembles du noyau de $mu$.Dans un premier temps, on met en évidence deux systèmes de réécriture, l'un sur l'alphabet fini ${0,1}$, l'autresur l'alphabet infini des entiers $nb$ et on montreque ces deux systèmes de réécriture définissent des présentations de monoïde de $PSL_2(zb)$ par générateurs et relations.Par ailleurs, on introduit le morphisme d'indice associé `a l'abélianisé du rev^etement universel de $PSL_2(zb)$,le groupe $B_3$ des tresses `a trois brins. Interprété dans deux contextes différents,le morphisme d'indice est associé au nombre de "demi-tours".Ensuite, dans les quatrième et cinquième parties, on dénombre des sous-ensembles du noyau de $mu_{|{0,1}}$ etdu noyau de $mu$, bigradués par la longueur et l'indice. La suite des nombres de Catalan et d'autres diagonales du triangle de Catalan interviennentsimplement dans les résultats.Enfin, on présente l'origine géométrique de cette étude : on explicite le lien entre l'objectif premier de la thèse qui était l'étudedes polygones convexes entiers d'aire minimale et notre intéret pour le monoïde engendré par ces matrices particulières de $PSL_2(zb)$. / In this thesis, we study a morphism of mono"id $mu$ between the free mono"id on the alphabet of integers $nb$and the modular group $PSL_2(zb)$ considered as a mono"id, defined for all integer $a$by $mu(a)=begin{pmatrix} 0 & -1 1 & a+1 end{pmatrix}.$ The Catalan Numbers arised naturally in the study ofsubsets of the kernel of the morphism $mu$.Firstly, we introduce two rewriting systems, one on the finite alphabet ${0,1}$, and the other on the infinite alphabet of integers $nb$. We proove that bothof these rewriting systems defines a mono"id presentation of $PSL_2(zb)$ by generators and relations.On another note, we introduce the morphism of loop associated to the abelianised of the universal covering group of $PSL_2(zb)$, the group $B_3$ ofbraid group on $3$ strands. In two different contexts, the morphism of loop is associated to the number of "half-turns".Then, in the fourth and the fifth parts, we numerate subsets of the kernel of $mu_{|{0,1}}$ and of the kernel of $mu$,bi-graduated by the morphism of lengthand the morphism of loop. The sequences of Catalan numbers and other diagonals of the Catalan triangle come into the results.Lastly, we present the geometrical origin of this research : we detail the connection between our first aim,which was the study of convex integer polygones ofminimal area, and our interest for the mono"id generated by these particular matrices of $PSL_2(zb)$.
|
25 |
Autour de l'évaluation numérique des fonctions D-finiesMezzarobba, Marc 27 October 2011 (has links) (PDF)
Les fonctions D-finies (ou holonomes) à une variable sont les solutions d'équations différentielles linéaires à coefficients polynomiaux. En calcul formel, il s'est avéré fructueux depuis une vingtaine d'années d'en développer un traitement algorithmique unifié. Cette thèse s'inscrit dans cette optique, et s'intéresse à l'évaluation numérique des fonctions D-finies ainsi qu'à quelques problèmes apparentés. Elle explore trois grandes directions. La première concerne la majoration des coefficients des développements en série de fonctions D-finies. On aboutit à un algorithme de calcul automatique de majorants accompagné d'un résultat de finesse des bornes obtenues. Une seconde direction est la mise en pratique de l'algorithme " bit burst " de Chudnovsky et Chudnovsky pour le prolongement analytique numérique à précision arbitraire des fonctions D-finies. Son implémentation est l'occasion de diverses améliorations techniques. Ici comme pour le calcul de bornes, on s'attache par ailleurs à couvrir le cas des points singuliers réguliers des équations différentielles. Enfin, la dernière partie de la thèse développe une méthode pour calculer une approximation polynomiale de degré imposé d'une fonction D-finie sur un intervalle, via l'étude des développements en série de Tchebycheff de ces fonctions. Toutes les questions sont abordées avec un triple objectif de rigueur (résultats numériques garantis), de généralité (traiter toute la classe des fonctions D-finies) et d'efficacité. Pratiquement tous les algorithmes étudiés s'accompagnent d'implémentations disponibles publiquement.
|
26 |
Algorithmes et applications pour la coloration et les alliances dans les graphes / Graph colorings and alliances : algorithms and applicationsYahiaoui, Said 05 December 2013 (has links)
Dans cette thèse, nous nous intéressons aux aspects algorithmiques et applications de deux problèmes de graphes, à savoir, la coloration et les alliances. La première partie concerne deux variantes de la coloration de graphes, la coloration Grundy et la coloration forte stricte. Nous commençons par l'étude du nombre Grundy des graphes réguliers. Nous donnons une condition fixe k, nous fournissons une condition nécessaire et suffisante pour que le nombre Grundy d'un graphe régulier soit au moins égal k. Nous caractérisons la classe des graphes cubiques (3-réguliers) pour laquelle le nombre Grundy est égal à 4, et nous présentons un algorithme linéaire pour déterminer le nombre Grundy d'un graphe cubique quelconque. Par ailleurs, en se basant sur la coloration forte stricte pour décomposer les arbres en petites composantes, nous présentons un nouvel algorithme pour l'appariement d'arbres étiquetés, non-ordonnés non-enracinés. Nous montrons que la distance calculée entre deux arbres est une pseudo-métrique. Nos expérimentations sur de larges bases synthétiques et des bases de données réelles confirment nos résultats analytiques et montrent que la distance proposée est précise et son algorithme est scalable. La seconde partie de cette thèse est consacrée aux alliances dans les graphes. Nous proposons un algorithme distribué autostabilisant pour la construction d'alliance offensive globale minimale dans un graphe arbitraire. Nous démontrons que cet algorithme converge sous le démon synchrone en temps linéaire. Ensuite, nous donnons le premier algorithme distribué autostabilisant pour le problème de l'alliance forte globale minimale dans un graphe quelconque. Nous prouvons que cet algorithme est polynomial sous le démon inéquitable distribué. Nous montrons par la suite, comment cet algorithme peut être adapté pour des généralisations du problème, comme la k-alliance forte et l'alliance forte pondérée. Enfin, en se basant sur les propriétés structurelles de l'alliance offensive, nous présentons une solution pour décentraliser le protocole de signalisation SIP. Ceci rend possible son déploiement dans un réseau mobile ad hoc / This thesis investigates the algorithmic aspects and applications of two graph problems, namely, colorings and alliances. In the first part, we focus on two variants of the proper vertex coloring, the Grundy coloring and the strict strong coloring. We start by the study of Grundy number for regular graphs. We give a sufficient condition for d-regular graphs with sufficiently large girth to have Grundy number equals d + 1. Then, using graph homomorphism, we obtain a necessary and sufficient condition for d-regular graphs to have Grundy number at least k. Moreover, we characterize cubic graphs (3-regular) for which the Grundy number is d + 1, and present a linear-time algorithm to determine the Grundy number of any arbitrary cubic graph. Subsequently, based on the strict strong coloring, we present an approach for the problem of matching labeled trees. Using this coloring, we propose a new algorithm to deterministically decompose a tree into small components. This leads to an efficient algorithm to measure an accurate distance between unrooted unordered labeled trees. The second part is devoted to the alliances in graphs. We first propose a linear-time self-stabilizing algorithm for the minimal global offensive alliance set problem, under the synchronous distributed scheduler. Then, we give the first self-stabilizing algorithm for the minimal global powerful alliance set problem in arbitrary graphs. Moreover, we show how this algorithm can be adapted to find the minimal global powerful k-alliance and the minimal weighted global powerful alliance sets. We prove that all these algorithms converge in polynomial-time under the unfair distributed scheduler. Finally, based on the structural properties of the offensive alliance, we propose a solution to decentralize the signaling protocol SIP. This enables SIP applications in mobile ad hoc networks
|
27 |
Contribution à la stabilité de Lyapunov non-régulière des inclusions différentielles avec opérateurs monotones maximaux / Contribution to nonsmooth Lyapunov stability of differential inclusions with maximal monotone operatorsNguyen, Bao tran 31 October 2017 (has links)
Dans cette thèse de doctorat, nous apportons quelques contributions à la stabilité de Lyapunov non-régulière des inclusions différentielles de premier ordre avec opérateurs monotones maximaux, dans un cadre Hilbertien de dimension infini. Nous fournissons des caractérisations explicites, primales et/ou duales, des paires de Lyapunov faibles et fortes, dont les fonctions sont semi-continues inférieurement à valeurs réelles étendues, et associées à des inclusions différentielles dont la partie de droite est gouvernée par des perturbations Lipschitziennes des opérateurs dits Cusco F, ou des opérateurs monotones maximaux A, ou les deux à la fois x(t) ∈ F(x(t}} A(x(t}} t ≥ 0, x(0) ∈ domA. De manière équivalente, nous étudions l'invariance faible et forte des ensembles fermés pour ces inclusions différentielles. Comme dans L'approche classique de Lyapunov à la stabilité des équations différentielles, les résultats présentés dans cette thèse n'utilisent que les données du système différentiel; c'est-à-dire, l'opérateur A et la multifonction F, et donc pas besoin de connaître les solutions, ni les semi-groupes générés par les opérateurs monotones en question. Parce que les paires de Lyapunov sont formées par des fonctions qui sont simplement semi-continues inférieurement, et les ensembles invariants ne sont que ensembles fermés, nous faisons usage dans cette thèse à des outils de l'analyse non-lisse, afin de fournir des critères du premier ordre, utilisant des sous-différentiels généraux et des cônes normaux. Nous fournissons une analyse similaire pour les inclusions différentielles gouvernées par le cône normal proximal à des ensembles prox-réguliers. Notre analyse ci-dessus, nous a permis de présenter ces systèmes prox-réguliers d’apparence plus générale, comme des inclusions différentielles avec opérateurs monotones maximaux. Nous utilisons aussi nos résultats pour étudier la géométrie des opérateurs monotones maximaux, et plus précisément, la caractérisation de la frontière des valeurs de ces opérateurs seulement au moyen des valeurs situées à proximité, distinctes du point de référence. Ce résultat a des applications dans la stabilité des problèmes de la programmation semi-infinie. Nous utilisons également nos résultats sur les paires de Lyapunov et les ensembles invariants pour établir une étude systématique des observateurs de type Luenberger pour des inclusions différentielles avec des cônes normaux à des ensembles prox-réguliers. / In this PhD thesis, we make some contributions to nonsmooth Lyapunov stability of first-order differential inclusions with maximal monotone operators, in the setting of infinite-dimensional Hilbert spaces. We provide primal and dual explicit characterizations for parameterized weak and strong Lyapunov pairs of lower semicontinuous extended-real-valued functions, referred to as a-Lyapunov pairs, associated to differential inclusions with right-hand-sides governed by Lipschitz or Cusco perturbationsF of maximal monotone operators A, x(t) ∈ F(x(t}} A(x(t}} t ≥ 0, x(0) ∈ domA. Equivalently, we study the weak and strong invariance of sets with respect to such differential inclusions. As in the classical Lyapunov approach to the stability of differential equations, the presented results make use of only the data of the differential system; that is, the operator A and the multifunction F, and so no need to know about the solutions, nor the semi-groups generated by the monotone operators. Because our Lyapunov pairs and invariant sets candidates are just lower semicontinuous and closed, respectively, we make use of nonsmooth analysis to provide first-order-like criteria using general subdifferentials and normal cones. We provide similar analysis to non-convex differential inclusions governed by proximal normal cones to prox-regular sets. Our analysis above allowed to prove that such apparently more general systems can be easily coined into our convex setting. We also use our results to study the geometry of maximal monotone operators, and specifically, the characterization of the boundary of the values of such operators by means only of the values at nearby points, which are distinct of the reference point. This result has its application in the stability of semi-infinite programming problems. We also use our results on Lyapunov pairs and invariant sets to provide a systematic study of Luenberger-like observers design for differential inclusions with normal cones to prox-regular sets.
|
28 |
Automates à contraintes semilinéaires = Automata with a semilinear constraintCadilhac, Michaël 11 1900 (has links)
Cette thèse présente une étude dans divers domaines de l'informatique
théorique de modèles de calculs combinant automates finis et contraintes
arithmétiques. Nous nous intéressons aux questions de décidabilité,
d'expressivité et de clôture, tout en ouvrant l'étude à la complexité, la
logique, l'algèbre et aux applications. Cette étude est présentée au travers
de quatre articles de recherche.
Le premier article, Affine Parikh Automata, poursuit l'étude de Klaedtke et Ruess
des automates de Parikh et en définit des généralisations et restrictions.
L'automate de Parikh est un point de départ de cette thèse; nous montrons que
ce modèle de calcul est équivalent à l'automate contraint que nous
définissons comme un automate qui n'accepte un mot que si le nombre de fois
que chaque transition est empruntée répond à une contrainte arithmétique.
Ce modèle est naturellement étendu à l'automate de Parikh affine qui
effectue une opération affine sur un ensemble de registres lors du
franchissement d'une transition. Nous étudions aussi l'automate de
Parikh sur lettres: un automate qui n'accepte un mot que si le nombre de
fois que chaque lettre y apparaît répond à une contrainte arithmétique.
Le deuxième article, Bounded Parikh Automata, étudie les langages
bornés des automates de Parikh. Un langage est borné s'il existe des
mots w_1, w_2, ..., w_k tels que chaque mot du langage peut s'écrire
w_1...w_1w_2...w_2...w_k...w_k. Ces langages sont
importants dans des domaines applicatifs et présentent usuellement de bonnes
propriétés théoriques. Nous montrons que dans le contexte des langages
bornés, le déterminisme n'influence pas l'expressivité des automates de
Parikh.
Le troisième article, Unambiguous Constrained Automata, introduit les
automates contraints non ambigus, c'est-à-dire pour lesquels il
n'existe qu'un chemin acceptant par mot reconnu par l'automate. Nous
montrons qu'il s'agit d'un modèle combinant une meilleure expressivité et de
meilleures propriétés de clôture que l'automate contraint déterministe. Le
problème de déterminer si le langage d'un automate contraint non ambigu est
régulier est montré décidable.
Le quatrième article, Algebra and Complexity Meet Contrained Automata,
présente une étude des représentations algébriques qu'admettent les automates
contraints et les automates de Parikh affines. Nous déduisons de ces
caractérisations des résultats d'expressivité et de complexité. Nous
montrons aussi que certaines hypothèses classiques en complexité
computationelle sont reliées à des résultats de séparation et de non clôture
dans les automates de Parikh affines.
La thèse est conclue par une ouverture à un possible approfondissement, au
travers d'un certain nombre de problèmes ouverts. / This thesis presents a study from the theoretical computer science
perspective of computing models combining finite automata and arithmetic
constraints. We focus on decidability questions, expressiveness, and closure
properties, while opening the study to complexity, logic, algebra, and
applications. This thesis is presented through four research articles.
The first article, Affine Parikh Automata, continues the study of Klaedtke
and Ruess on Parikh automata and defines generalizations and restrictions of
this model. The Parikh automaton is one of the starting points of this
thesis. We show that this model of computation is equivalent to the
constrained automaton that we define as an automaton which accepts a word
only if the number of times each transition is taken satisfies a given
arithmetic constraint. This model is naturally extended to affine Parikh
automata, in which an affine transformation is applied to a set of registers
on taking a transition. We also study the Parikh automaton on letters, that
is, an automaton which accepts a word only if the number of times each letter
appears in the word verifies an arithmetic constraint.
The second article, Bounded Parikh Automata, focuses on the
bounded languages of Parikh automata. A language is bounded if there
are words w_1, w_2, ..., w_k such that every word in the language can be
written as w_1...w_1w_2...w_2 ... w_k...w_k. These languages
are important in applications and usually display good theoretical
properties. We show that, over the bounded languages, determinism does not
influence the expressiveness of Parikh automata.
The third article, Unambiguous Constrained Automata, introduces the
concept of unambiguity in constrained automata. An automaton is
unambiguous if there is only one accepting path per word of its language. We
show that the unambiguous constrained automaton is an appealing model of
computation which combines a better expressiveness and better closure
properties than the deterministic constrained automaton. We show that it is
decidable whether the language of an unambiguous constrained automaton is
regular.
The fourth article, Algebra and Complexity Meet Constrained Automata,
presents a study of algebraic representations of constrained automata and
affine Parikh automata. We deduce expressiveness and complexity results from
these characterizations. We also study how classical computational
complexity hypotheses help in showing separations and nonclosure properties
in affine Parikh automata.
The thesis is concluded by a presentation of possible future avenues of
research, through several open problems.
|
29 |
Une approche combinatoire du problème de séparation pour les langages réguliers / A combinatorial approach to the separation problem for regular languagesVan Rooijen, Lorijn 04 December 2014 (has links)
Le problème de séparation pour une classe de langages S est le suivant : étant donnés deux langages L1 et L2, existe-t-il un langage appartenant à S qui contient L1, en étant disjoint de L2 ? Si les langages à séparer sont des langages réguliers, le problème de séparation pour la classe S est plus général que le problème de l'appartenance à cette classe, et nous fournit des informations plus détaillées sur la classe. Ce problème de séparation apparaît dans un contexte algébrique sous la forme des parties ponctuelles, et dans un contexte profini sous la forme d'un problème de séparation topologique. Pour quelques classes de langages spécifiques, ce problème a été étudié en utilisant des méthodes profondes de la théorie des semigroupes profinis.Dans cette thèse, on s'intéresse, dans un premier temps, à la décidabilité de ce problème pour plusieurs sous-classes des langages réguliers. Dans un second temps, on s'intéresse à obtenir un langage séparateur, s'il existe, ainsi qu'à la complexité de ces problèmes.Nous établissons une approche générique pour prouver que le problème de séparation est décidable pour une classe de langages donnée. En utilisant cette approche, nous obtenons la décidabilité du problème de séparation pour les langages testables par morceaux, les langages non-ambigus, les langages localement testables, et les langages localement testables à seuil. Ces classes correspondent à des fragments de la logique du premier ordre, et sont parmi lesclasses de langages réguliers les plus étudiées. De plus, cette approche donne une description d'un langage séparateur, pourvu qu'il existe. / The separation problem, for a class S of languages, is the following: given two input languages, does there exist a language in S that contains the first language and that is disjoint from the second langage ?For regular input languages, the separation problem for a class S subsumes the classical membership problem for this class, and provides more detailed information about the class. This separation problem first emerged in an algebraic context in the form of pointlike sets, and in a profinite context as a topological separation problem. These problems have been studied for specific classes of languages, using involved techniques from the theory of profinite semigroups.In this thesis, we are not only interested in showing the decidability of the separation problem for several subclasses of the regular languages, but also in constructing a separating language, if it exists, and in the complexity of these problems.We provide a generic approach, based on combinatorial arguments, to proving the decidability of this problem for a given class. Using this approach, we prove that the separation problem is decidable for the classes of piecewise testable languages, unambiguous languages, and locally (threshold) testable languages. These classes are defined by different fragments of first-order logic, and are among the most studied classes of regular languages. Furthermore, our approach yields a description of a separating language, in case it exists.
|
30 |
Geoffroi du Loroux et l'architecture religieuse en Aquitaine au XIIème siècleMasson, Juliette 04 July 2012 (has links) (PDF)
Cette étude menée sur les fondations canoniales de Geoffroy du Loroux, archevêque de Bordeaux de 1136 à 1158, a pour objectif de montrer une implication du prélat dans le parti architectural de ses fondations qui présentent a priori une similitude en plan et en élévation. Grand artisan de la réforme grégorienne en Aquitaine, l'action de Geoffroy du Loroux est bien cernée par sa collection de sermons mais ses fondations n'ont jamais fait l'objet d'une étude de synthèse. Chacune des quatre fondations attribuées à l'archevêque, l'Isle et Pleine-Selve (Gironde), Sablonceaux (Charente-Maritime) et Fontaine-le-Comte (Vienne), a été soumise à une analyse architecturale approfondie, complétée d'une étude métrologique, afin d'appréhender chaque édifice dans sa globalité. Les éléments conservés du XIIe siècle ont ensuite été soumis à une étude comparative. En outre, une discussion est menée autour de l'attribution à Geoffroy du Loroux de la reconstruction de la cathédrale de Bordeaux dès le XIIe siècle.Il s'avère que les fondations liées à Geoffroy du Loroux adoptent un parti architectural stéréotypé et d'une esthétique ostensiblement austère. L'archevêque apparaît comme un prélat soucieux de laisser à ses successeurs des modèles pour transmettre le message de la réforme grégorienne, tant au travers de ses sermons qu'au niveau de ses fondations. Ces dernières se devaient d'être représentatives d'une grande humilité et du retour à la rigueur prôné par la réforme, en totale opposition avec le faste clunisien. Ce travail amène à s'interroger sur le rôle des collégiales qui, utilisées tel un outil de diffusion de la réforme, ont pu freiner l'implantation de Cluny dans le Bordelais.
|
Page generated in 0.0837 seconds