Tesis sobre el tema "Théorie algébgrique des automates"
Crea una cita precisa en los estilos APA, MLA, Chicago, Harvard y otros
Consulte los 50 mejores tesis para su investigación sobre el tema "Théorie algébgrique des automates".
Junto a cada fuente en la lista de referencias hay un botón "Agregar a la bibliografía". Pulsa este botón, y generaremos automáticamente la referencia bibliográfica para la obra elegida en el estilo de cita que necesites: APA, MLA, Harvard, Vancouver, Chicago, etc.
También puede descargar el texto completo de la publicación académica en formato pdf y leer en línea su resumen siempre que esté disponible en los metadatos.
Explore tesis sobre una amplia variedad de disciplinas y organice su bibliografía correctamente.
Soyez-Martin, Claire. "From semigroup theory to vectorization : recognizing regular languages". Electronic Thesis or Diss., Université de Lille (2022-....), 2023. http://www.theses.fr/2023ULILB052.
Texto completoThe pursuit of optimizing regular expression validation has been a long-standing challenge,spanning several decades. Over time, substantial progress has been made through a vast range of approaches, spanning from ingenious new algorithms to intricate low-level optimizations.Cutting-edge tools have harnessed these optimization techniques to continually push the boundaries of efficient execution. One notable advancement is the integration of vectorization, a method that leverage low-level parallelism to process data in batches, resulting in significant performance enhancements. While there has been extensive research on designing handmade tailored algorithms for particular languages, these solutions often lack generalizability, as the underlying methodology cannot be applied indiscriminately to any regular expression, which makes it difficult to integrate to existing tools.This thesis provides a theoretical framework in which it is possible to generate vectorized programs for regular expressions corresponding to rational expressions in a given class. To do so, we rely on the algebraic theory of automata, which provides tools to process letters in parallel. These tools also allow for a deeper understanding of the underlying regular language, which gives access to some properties that are useful when producing vectorized algorithms. The contribution of this thesis is twofold. First, it provides implementations and preliminary benchmarks to study the potential efficiency of algorithms using algebra and vectorization. Second, it gives algorithms that construct vectorized programs for languages in specific classes of rational expressions, namely the first order logic and its subset restricted to two variables
Hélouët, Loïc. "Automates d'ordres : théorie et applications". Habilitation à diriger des recherches, Université Rennes 1, 2013. http://tel.archives-ouvertes.fr/tel-00926742.
Texto completoBroglio, Annie. "Prédiction par automates". Aix-Marseille 1, 1991. http://www.theses.fr/1991AIX11385.
Texto completoPodelski, Andreas. "Monoïdes d'arbres et automates d'arbres". Paris 7, 1989. http://www.theses.fr/1989PA077247.
Texto completoMosconi, Jean. "La constitution de la théorie des automates". Paris 1, 1989. http://www.theses.fr/1989PA010611.
Texto completoIn the years 1965, the process of the constitution of the "theory of automata", a logico-algebraical study of the computing devices which can be used as mathematical models for information processing machines, was completed. In spite of its theoretical connection with the Turing machine, the enterprise did, however, not take the form of an explicit topic until 1948, when Von Neumann proposed to handle within the framework of a general "logical" theory a whole set of questions stemming from various domains, spreading from biology to computers. The study of finite automata, in the decade 1950-1960, was then the first to impose an organisation on these disconnected achievements in the form of a coherent abstract theory, endowed with manageable algebraical and logical tools. As a counterpart, Turing's approach of calculability gave rise to a theory of infinite machines (whose architectonics was brought gradually closer to that of actual machines), which was to be quickly extended by a computational complexity theory. Finally, in the sixties, joining the combinatorial-algorithmic tradition of post and Markov, the syntactical analysis of natural and programming languages gave the decisive impulse, through the theory of formal grammars, to the study of "bounded-infinite" automata, in particular pushdown and linear bounded automata
Dartois, Luc. "Méthodes algébriques pour la théorie des automates". Paris 7, 2014. http://www.theses.fr/2014PA077236.
Texto completoIn this thesis, we extend the links between the different models of representation of rational languages that are automata, logic and monoids through two extensions of these theories. The first contribution concerns the two-way transducers, an extension of automata defining transformations of words. We first propound the construction of the transitions monoid of two-way machines. This allows us to define the notion of aperiodic two-way transducers. We finally prove that this class is stable by composition. The second contribution concerns logic on finite words. The definability problem of a fragment of logic consists in deciding whether a given regular language can be defined by a formula of the said fragment. We study the decidability of this question when the signature of a fragment is enriched, in our case by predicates handling the modular information of the positions. Thanks to algebraic methods, we were able to gather transfer results to enriched fragments, unifying known results as well as obtaining new ones
Samuelides, Mathias. "Automates d'arbres à jetons". Phd thesis, Université Paris-Diderot - Paris VII, 2007. http://tel.archives-ouvertes.fr/tel-00255024.
Texto completoUne première contribution a été de prouver que les variantes déterministes des deux modèles d'automates d'arbres à jetons sont fermées par complément. Nous donnons alors une nouvelle présentation de la preuve de la caractérisation du modèle fort des automates d'arbres à jetons qui a été établie par Engelfriet et Hoogeboom.
Une autre contribution a été de montrer que les deux modèles d'automates à jetons sont équivalents, que le pouvoir d'expression des automates d'arbres à jetons augmente avec le nombre de jetons et qu'il n'est pas toujours possible de déterminiser un automate d'arbres cheminant même si on s'autorise à ajouter un nombre fixé de jetons.
Une dernière contribution a été de prouver que les problèmes du vide et de l'inclusion sont n-EXPTIME complets pour les classes d'automates à n jetons avec n supérieur à 1.
Oaurdi, Faissal. "Expressions rationnelles et automates réduits". Rouen, 2007. http://www.theses.fr/2007ROUES006.
Texto completoThe general topic of this thesis lies within the scope of the automata theory and turns on the design of efficient algorithms for the problem of conversion of weighted and boolean regular expressions into finite automata having small sizes. We study various types of reduced automata defined from regular expressions : the position automaton, the follow automaton, the c-continuation automaton and the common follows automaton. On the one hand, we give a comparison between the follow automaton and the equation automaton. On the other hand, we describe a new efficient algorithm based on the minimization of an acyclic automaton, for the construction of the equation automaton. We were also interested in the generalization of these automata and their constructions for the weighted regular expressions. We generalize the notion of ZPC structure for the weighted case. We develop two new quadratic algorithms for the problem of the conversion of weighted regular expressions. The first algorithm is based on the extended ZPC structure, allows the construction of the position automaton with multiplicities. The second one, based on the c-continuations, computes the equation automaton with multiplicities. We finally define an extension to the weighted case of the common follows set automaton introduced by Hromckovic et al. We show that this automaton can be obtained in O(nlog2(n)) time where n is the size of the weighted regular expressions
Loraud, Nathalie. "Numérations généralisées, langages et automates". Aix-Marseille 1, 1996. http://www.theses.fr/1996AIX11019.
Texto completoVerma, Kumar Neeraj. "Automates d'arbres bidirectionnels modulo théories équationnelles". Cachan, Ecole normale supérieure, 2003. http://www.theses.fr/2003DENS0027.
Texto completoChemlal, Rezki. "Valeurs propres des automates cellulaires". Phd thesis, Université Paris-Est, 2012. http://tel.archives-ouvertes.fr/tel-00794398.
Texto completoProvillard, Julien. "Automates cellulaires non-uniformes". Nice, 2012. http://www.theses.fr/2012NICE4082.
Texto completoCellular automata (CA) are discrete dynamical systems widely used in many scientific domains. Their main characteristic is to act locally, synchronously and uniformly on a regular set of elementary components called cells. These systems have a huge variety of dynamical behaviours and have been extensively studied in literature. Several variants have been proposed. In this work we are interested in non-uniform cellular automata (nu-CA). They are, essentially, CA in which the uniformity constraint has been relaxed. In the first part, we study a family of nu6CZA which allows to easily representing perturbations of the structure of a CA. The idea is to study the impact of the dynamics of failure or of an error in the physical implementation of a CA by electronic components. Indeed, we will prove that several dynamical properties are not structurally stable (except for the equicontinuity property). However, we will show how to link properties of a CA and its “perturbed” versions. In the second part, we try to infer the global properties of a nu-CA from the local behaviours we can observe. Given a set of local rules which can appear in a given nu-CA, we study the way of mowing them to obtain given global behaviours. Moreover, we associate global properties with peculiar formal languages and we completely characterize these formal languages. In this way we obtain a natural notion of complexity for properties on nu-CA. A property is a complex as the class of languages from which it is characterizes
Roux, Bernard. "Une approche relationnelle des automates et de l'ordonnancement". Lyon 1, 2000. http://www.theses.fr/2000LYO10255.
Texto completoCarayol, Arnaud. "Automates infinis, logique et langages". Rennes 1, 2006. https://tel.archives-ouvertes.fr/tel-00628513.
Texto completoReimen, Nicolas. "Contribution à l'étude des automates cellulaires". Paris 7, 1993. http://www.theses.fr/1993PA077335.
Texto completoRoka, Zsuzsanna. "Automates cellulaires sur graphes de Cayley". Lyon 1, 1994. http://www.theses.fr/1994LYO10180.
Texto completoLombardy, Sylvain. "Approche structurelle de quelques problèmes de la théorie des automates". Phd thesis, Ecole nationale supérieure des telecommunications - ENST, 2001. http://tel.archives-ouvertes.fr/tel-00737830.
Texto completoCaron, Pascal. "Langages rationnels et automates : de la théorie à la programmation". Rouen, 1997. http://www.theses.fr/1997ROUES079.
Texto completoDahmoune, Mohamed. "Quelques contributions en logique mathématique et en théorie des automates". Thesis, Paris Est, 2014. http://www.theses.fr/2014PEST1013/document.
Texto completoThis work deals mainly with automata theory, mathematical logic and their applications. In the first part, we use finite automata to prove the automaticity of several logical structures over finite words written in a countable infinite alphabet. These structures involve predicates like $pred$, $clone$ and $diff$, where $x pred y$ holds if $x$ is a strict prefix of $y$, $clone(x)$ holds when the two last letters of $x$ are equal, and $diff(x)$ holds when all letters of $x$ are pairwise distinct. The automaticity results allow to deduce the decidability of logical theories associated with these structures. Other related decidability/undecidability results are obtained by logical interpretation. In the second part, we generalize the concept of Common Follow Sets of a regular expression to homogeneous finite automata. Based on this concept and a particular class of binary trees, we devise an efficient algorithm to reduce/minimize the number of transitions of triangular automata. On the one hand, we prove that the produced reduced automaton is asymptotically minimal, in the sense that for an automaton with $n$ states, the number of transitions in the reduced automaton is equivalent to $n(log_2 n)^2$ , which corresponds at the same time to the upper and the lower known bounds. On the other hand, experiments reveal that for small values of $n$, all minimal automata are exactly those obtained by our reduction, which lead us to conjecture that our construction is not only a reduction but a minimization. In the last part, we present an experimental study on the use of special automata on partial words for the approximate pattern matching problem in dictionaries. Despite exponential theoretical time and space upper bounds, our experiments show that, in many practical cases, these automata have a linear size and allow a linear search time
Carayol, Arnaud. "Automates infinis, logiques et langages". Phd thesis, Université Rennes 1, 2006. http://tel.archives-ouvertes.fr/tel-00628513.
Texto completoCristau, Julien. "Jeux et automates sur les ordres". Phd thesis, Université Paris-Diderot - Paris VII, 2010. http://tel.archives-ouvertes.fr/tel-00554026.
Texto completoDaviaud, Laure. "Comportements asymptotiques des automates Max-plus et Min-plus". Paris 7, 2014. http://www.theses.fr/2014PA077238.
Texto completoThis thesis focuses on the study of issues that lie at the boundary between decidability of boundedness and undecidability of the comparison. For that, this paper gives a detailed description of functions computed by min-plus and max-plus automata. More precisely, given a function f computed by a min-plus (resp. Max-plus) automaton, the main contribution of the thesis consists in the description of the function g that associates an integer n to the maximum of the values f(w) for words w of length less than n (respectively the minimum of the values f(w) for words w of length greater than n). The theorem for approximating the function-length ratio gives an approximation of the upper bound of ratios g(n)/n in the case of a min-plus automaton, and an approximation of the lower bound of ratios g(n)/n in the case of a max-plus automaton. The asymptotic equivalence theorem describes the asymptotic behavior of the function g in the case of max-plus automata and more precisely, it states that this function is asymptotically equivalent to a rational function. The theorem for approximating the function-length ratio has an application to the approximate comparison of min-plus automata. This approximate comparison highly refines previously known results about comparison, and appears to be the most accurate comparison between two functions computed by min-plus automata, that remains decidable. The asymptotic equivalence theorem exhibits an algorithm that calculates an asymptotic equivalent of the length of the longest run in a size-change abstraction instance
Gonzalez, Patrick. "Croissance d'automates et théorie des nombres". Aix-Marseille 2, 1992. http://www.theses.fr/1992AIX22028.
Texto completoHadj, Kacem Hatem. "Contributions à la théorie et aux applications des automates à multiplicités". Rouen, 2005. http://www.theses.fr/2005ROUES008.
Texto completoThis thesis is a work based on publications in Theoretical Computer Science. It consists of two contributions of the theory of automata with multiplicities. This structure has many applications to connected sciences (Computer Sciences, Mathematics, Physics, …). A particular type of automata with multiplicities is the automaton with ε-transitions denoted by k-ε-automaton. In the first part, we give an algebraic method for removing the ε-transitions of the k-ε-automaton in order to obtain an equivalent k-automaton with the same behaviour. We discuss two aspects of the star problem (by infinite sums and by equations). The theory of minimization allows to minimize a k-automaton in the sense of reducing to the smallest among the number of states. It can be used with some modification to solve other problems such as the splitting of modules. We have used the algorithm of decomposition to split a Boolean function which constitute the non linear element of the cryptographic algorithm and to split a ц-module where ц is the Hecke algebra as q=0
Bernardi, Vincent. "Lois de conservation sur automates cellulaires". Aix-Marseille 1, 2007. http://www.theses.fr/2007AIX11055.
Texto completoBarat, Guy. "Echelles de numération et fonctions arithmétiques associées". Aix-Marseille 1, 1995. http://www.theses.fr/1995AIX11057.
Texto completoRamangalahy, Solofo. "Test de conformité pour des spécifications à base d'automates : une approche par la théorie des jeux". Orléans, 1999. http://www.theses.fr/1999ORLE2073.
Texto completoConformance testing aims at applying test cases to a system in order to study its correction with respect to its specification. The automaton model underlies the semantics of the usual formal specification languages. Its use in the specification phase allow the study of the conformance testing problem with the so-called "formal methods" framework. The thesis study this problem in this framework
Sebti, Nadia. "Noyaux rationnels et automates d'arbres". Rouen, 2015. http://www.theses.fr/2015ROUES007.
Texto completoIn the case of words, a general scheme for computing rational kernels has been proposed. It is based on a general algorithm for composition of weighted transducers and a general algorithm computing smallest distance. Our goal is to generalize this computation scheme to the case of trees using tree automata. To do this we have established the following two main objectives : On the one hand,define tree automata for computing subtree kernel, subsettree kernel and tree factor kernel. On the other hand, from a regular tree expression, build a tree automaton to compute the various rational tree kernels described by regular tree expressions using the following scheme over two tree languages L1 and L2 : KE(L1;L2) = (AL1 \ AE \ AL1). We explored and proposed efficient algorithms for the conversion of a regular tree expression into tree automata. The first algorithm computes the Follow sets for a regular tree expression E of a size jEj and alphabetic width jjEjj in O(jjEjj jEj) time complexity. The second algorithm computes the equation tree automaton via the k-C-Continuations which is based on the acyclic minimization of Revuz. The algorithm is performed in an O(jQj jEj) time and space complexity, where jQj is the number of states of the produced automaton. Then we developed algorithms for the computation of subtree kernel, subsettree kernel and tree factor kernel. Our approach is based on the representation of all trees of the set S = fs1; : : : ; sng (resp. T = ft1; : : : ; tmg) by a particular weighted tree automaton called Root Weighted Tree Automaton the RWTA AS (resp. AT ) (equivalent to the prefix automaton in the case of words) such that jASj #Pn i=1 jsij = jSj (resp. JAT #Pm j=1 jtj j = jTj) ; then we compute the kernels between the two sets S and T. This amounts to compute the weight of the intersection automaton AS \ AT. We show that the computation of the kernel K(S; T) can be done in O(jASj jAT j) time and space complexity. Keywords: Finite Tree Automata, Rationnal Tree Languages, Regular Tree Expressions, Conversion of Regular Tree Expressions, Rational Kernels, Trees, Rational Tree Kernels
Genet, Thomas. "Contraintes d'ordre et automates d'arbres pour les preuves de terminaison". Nancy 1, 1998. http://docnum.univ-lorraine.fr/public/SCD_T_1998_0245_GENET.pdf.
Texto completoCécé, Gérard. "Vérification, analyse et approximations symboliques des automates communicants". Cachan, Ecole normale supérieure, 1998. http://www.theses.fr/1998DENS0008.
Texto completoRenkin, Florian. "Transformations d’ω-automates pour la synthèse de systèmes réactifs". Electronic Thesis or Diss., Sorbonne université, 2022. http://www.theses.fr/2022SORUS227.
Texto completoSynthesis aims to produce a correct system from specifications. One approach to solve this problem is to translate the specification into a parity game whose winning strategy encodes the system. In this thesis we will show two methods to produce parity automata. The first is based on improving and combining new or existing procedures. The second is an algorithm from Casares et al. providing a guarantee of optimal results. In a second step, we will show how we reduce the obtained system. Two types of reductions will be discussed. The first allows to obtain an optimal result but not the second which privileges the processing time. The third part will describe optimizations that can be used for certain classes of specifications
Gauwin, Olivier. "Flux XML, Requêtes XPath et Automates". Phd thesis, Université des Sciences et Technologie de Lille - Lille I, 2009. http://tel.archives-ouvertes.fr/tel-00421911.
Texto completoDans cette thèse, nous étudions des algorithmes d'évaluation de requêtes sur des flux XML. Notre objectif est de gérer efficacement la mémoire, afin de pouvoir évaluer des requêtes sur des données volumineuses, tout en utilisant peu de mémoire. Cette tâche s'avère complexe, et nécessite des restrictions importantes sur les langages de requêtes. Nous étudions donc les requêtes définies par des automates déterministes ou par des fragments du standard W3C XPath, plutôt que par des langages plus puissants comme les standards W3C XQuery et XSLT.
Nous définissons tout d'abord les Streaming Tree Automata (STAs), qui opèrent sur les arbres d'arité non bornée dans l'ordre du document. Nous prouvons qu'ils sont équivalents aux Nested Word Automata et aux Pushdown Forest Automata. Nous élaborons ensuite un algorithme d'évaluation au plus tôt, pour les requêtes définies par des STAs déterministes. Bien qu'il ne stocke que les candidats nécessaires, cet algorithme est en temps polynomial à chaque événement du flux, et pour chaque candidat. Par conséquent, nous obtenons des résultats positifs pour l'évaluation en flux des requêtes définies par des STAs déterministes. Nous mesurons une telle adéquation d'un langage de requêtes à une évaluation en flux via un nouveau modèle de machines, appelées Streaming Random Access Machines (SRAMs), et via une mesure du nombre de candidats simultanément vivants, appelé concurrence. Nous montrons également qu'il peut être décidé en temps polynomial si la concurrence d'une requête définie par un STA déterministe est bornée. Notre preuve est basée sur une réduction au problème de la valuation bornée des relations reconnaissables d'arbres.
Concernant le standard W3C XPath, nous montrons que même de petits fragments syntaxiques ne sont pas adaptés à une évaluation en flux, sauf si P=NP. Les difficultés proviennent du non-déterminisme de ce langage, ainsi que du nombre de conjonctions et de disjonctions. Nous définissons des fragments de Forward XPath qui évitent ces problèmes, et prouvons, par compilation vers les STAs déterministes en temps polynomial, qu'ils sont adaptés à une évaluation en flux.
Mansard, Alexandre. "Automates infinis et traces de Mazurkiewicz". Thesis, La Réunion, 2020. https://elgebar.univ-reunion.fr/login?url=http://thesesenligne.univ.run/20_22_A_Mansard.pdf.
Texto completoWe introduce the notion of level-regularity for Mazurkiewicz trace languages and we consider recognizable trace rewriting systems with level-regular contexts (RTLsystem). We prove that an automaton for which the underlying graph is the rewriting graph of a RTL system and for which the sets of initial vertices and final vertices are level-regular (RTL automaton), is word-automatic. In particular, the first-order theory of a RTL automaton is decidable. Then, we prove that, enriched with thereachability relation, an automaton for which the underlying graph is the concurrent unfolding of a finite concurrent graph, and for which the sets of initial vertices and final vertices are level-regular, is RTL. In particular, the first-order theory with the reachability predicate of such an automaton is decidable. Besides, it is known that this property also holds for ground term rewriting graphs (GTR graph). We highlight various concurrent unfoldings of finite concurrent graphs that are not GTRgraphs. The infinite quarter grid tree is such an unfolding. The class of concurrent unfoldings of finite concurrent graphs is therefore a class of word-automatic graphs for which the first-order theory with the reachability predicate is decidable and that contains some non GTR graphs. We define the operations of level-length synchronization and level-length superposition of trace automata (automata for which vertices are Mazurkiewicz traces) and we prove that if a family F of trace automata is closed under these operations, then for any deterministic trace automaton H 2 F, the languages accepted by the deterministic trace automata belonging to F and that are length-reducible to H, form a Boolean algebra; the length of a trace being the length of its Foata normal form, a trace automaton G is length-reducible to a trace automaton H if there exists a length-preserving morphism from G to H. Then, we show that the family of trace suffix automata with level regular contexts, the extension of word suffix automata to Mazurkiewicz traces, satisfies these closure properties. We define a generalized Petri net as a trace suffix automaton over a dependence alphabet for which the dependence is reduced to the equality and we show that the subfamily of generalized Petri nets also satisfies the closure properties above. In particular, this yields various Boolean algebras of word languages accepted by deterministic generalized Petri nets
Zeitoun, Marc. "Opérations implicites et variétés de semi-groupes finis". Paris 7, 1993. http://www.theses.fr/1993PA077221.
Texto completoHéam, Pierre-Cyrille. "Contribution à l'algorithmique des automates : compléxité et aspects topologiques". Paris 7, 2001. http://www.theses.fr/2001PA077085.
Texto completoManiatakos, Vasileios Foivos A. "Graphes et Automates pour le Contrôle de l'Interaction en Improvisation Musicale Assistée par Ordinateur". Paris 6, 2012. http://www.theses.fr/2012PA066249.
Texto completoThis thesis studies three party interaction in the music improvisation context. We use this term to refer to the ensemble of interactions arising from the onstage coexistence of three constituents participants: the human instrument player, the computer and the computer operator/performer. The purpose of this study is to investigate the requirements arising out of such interaction as well as establish the framework that will allow the computer fulfil the double mission of operating both as player and an instrument. In this framework we first present Multi Factor Graph (MFG), a new memory model for musical sequences. MFG is a deterministic automaton that indexes played sequences, with the intention of dealing with pattern recognition and sequence generation. Inspired by the Factor Oracle (FO) automaton, MFG deals with two FO-related issues. First, it corrects FO’s false positives during string recognition. Second, as far as the computer improvisation domain is concerned, it corrects the errors in the estimation of continuation probabilities arising from the misinterpretation of the FO’s Suffix Link Tree (SLT) as an indicator for maximal suffix repeats. Secondly, we study with the help of graphs by examining the complexity of adding simple to more sophisticated and complex constraints to generation. We propose reduced, graph-based computational frameworks that are able to efficiently deal with each of the problems discussed earlier. Finally, by drawing together all elements developed throughout the first two parts, we employ MFG as a universal framework for managing problems of machine musicianship, namely music listening, constrained sequence generation and interaction
De, Souza Rodrigo. "Etude structurelle des transducteurs de norme bornée". Paris, ENST, 2008. http://www.theses.fr/2008ENST0023.
Texto completoTransducers - automata with output - and rational relations are fundamental concepts in the field of automata theory. In particular, the rational functions are an important and well known family of relations due to the remarkable properties they possess. The bounded valued relations are a generalisation of the rational functions introduced by Schützenberger in 1976, where every image has a bounded number of elements. Even though some properties of the rational functions have been shown to hold in this more general setting, the use of techniques of distinct nature and the difficulty of some proofs indicate the need for a deeper understanding of these relations. This thesis brings a uniform presentation of some properties of the bounded valued rational relations, based on the representation by transducers and the manipulation of their structure with the use of produts and coverings of automata. Under this structural approach, it is tackled the decomposition of a bounded valued rational relation into a sum of rational functions and a generalisation, the decidability of the bounded valuedness and of the equivalence for the bounded valued transducers. The constructions developed in this thesis allow in particular clear algorithms with gains of complexity with respect to the known results
Devolder-Muchembled, Jeanne. "Codes, mots infinis et bi-infinis". Lille 1, 1993. http://www.theses.fr/1993LIL10075.
Texto completoRispal, Chloé. "Automates sur les ordres linéaires : Complémentation". Phd thesis, Université de Marne la Vallée, 2004. http://tel.archives-ouvertes.fr/tel-00720658.
Texto completoSablik, Mathieu. "Etude de l'action conjointe d'un automate cellulaire et du décalage : une approche topologique et ergodique". Aix-Marseille 2, 2006. http://www.theses.fr/2006AIX22019.
Texto completoGuillon, Pierre. "Automates cellulaires : dynamiques, simulations, traces". Phd thesis, Université Paris-Est, 2008. http://tel.archives-ouvertes.fr/tel-00432058.
Texto completoFrilley, François. "Differenciation d'ensembles structures : applications aux cas du monoïde libre et de la foret des arbres finis et étiquetés". Paris 7, 1989. http://www.theses.fr/1989PA077189.
Texto completoFrisch, Alain. "Théorie, conception et réalisation d'un langage de programmation adapté à XML". Paris 7, 2004. http://www.theses.fr/2004PA077074.
Texto completoDando, Louis-Marie. "Expressivité des automates pondérés circulaires et boustrophédons". Thesis, Bordeaux, 2019. http://www.theses.fr/2019BORD0130/document.
Texto completoThis thesis deals with some extensions of weighted automata,and studies the series they can realisedepending on the nature of their weigths.These extensions are characterised by howthe input head of the automaton is allowed to move:rotating automata can go back at the beginning of the word,and two-way automata can change the reading direction.In the general setting, weigthed rotating automata are morepowerful than classical one-way automata, and less powerfulthan two-way ones.Moreover, we introduce Hadamard expressions,which are an extension of rational expressions and can denotethe behaviour of rotating automata.The algorithms for this conversion are studied when the weights belong toa rationally additive semiring.Then, rotating automata are shown as expressive as two-way automatain the case of rational, real or complex numbers.It is also proved that two-way and one-way automataare equivalent when weighted on a locally finite bimonoid
Luque, Jean-Gabriel. "Monoïdes et automates admettant un produit de mélange". Rouen, 1999. http://www.theses.fr/1999ROUES094.
Texto completoVELOSO, PEIXOTO MARCOS. "Automates a contraintes arithmetiques et procedures d'evaluation ascendante de programmes logiques". Paris 7, 1994. http://www.theses.fr/1994PA077194.
Texto completoMaubert, Bastien. "Fondations logiques des jeux à information imparfaite : stratégies uniformes". Phd thesis, Université Rennes 1, 2014. http://tel.archives-ouvertes.fr/tel-00980490.
Texto completoGuingne, Franck. "Contribution à l’algorithmique des automates pondérés à une, deux ou plusieurs bandes". Rouen, 2005. http://www.theses.fr/2005ROUES009.
Texto completoThis PhD thesis deals with the automata theory. A general study of similarity relations and the notion a cover automata are presented. We define merging relations and the notion of cover transducers. A reduction algorithm is exposed and tested. Weighted multi-tape automata are a generalisation of automata and transducers. We define the join and auto-intersection operations and we present the corresponding algorithms. As a consequence of the Post's Correspondence Problem there does not exist a general algorithm of auto-intersection. We define a class of weighted multi-tape automata in which it is possible to compute the auto-intersection. After a State of the Art of finite state machine compilers, we present XEROX's compilers, WFSC and XFST, through their specificities. We present the '?' symbol and extended-alphabet machines, then the notion of virtual networks in XFST. Several characteristics of the generic and modular design of WFSC are exposed. We study the worst-case complexity for the printing of all paths of an acyclic automaton. We describe the structure that maximizes the complexity, then we compute this complexity for a given number of states
Saidane, Faouzi. "Graphes et langages : une approche métrique". Lyon 1, 1991. http://www.theses.fr/1991LYO10206.
Texto completoViêt, Triêm Tông Valérie. "Automates d'arbres et réécriture pour l'étude de problèmes d'accessibilité". Rennes 1, 2003. http://www.theses.fr/2003REN10162.
Texto completo