L'analyse prévisionnelle des risques d'un système complexe repose aujourd'hui sur une modélisation de la dynamique du système vis-à-vis des défaillances et réparations de ses composants. L'analyse qualitative d'un tel système consiste à rechercher et à analyser les scénarios conduisant à la panne. En raison de leur nombre, il est courant de ne s'intéresser qu'aux scénarios les plus caractéristiques, les Séquences de Coupe Minimales (SCM). L'absence de formalisation de ces SCM a généré soit des définitions spécifiques à certains outils de modélisation soit des définitions informelles. Les travaux présentés dans cette thèse proposent: i) un cadre et une définition formelle des séquences de coupe minimales, tout deux indépendants de l'outil de modélisation de fiabilité utilisé, ii) une méthode permettant leur calcul, méthode basée sur des propriétés déduites de leur définition, iii) l'extension des premières définitions aux composants multimodes. Ce cadre permet le calcul des SCM pour des installations décrites avec les Boolean logic Driven Markov Processes (BDMP). Sous l'hypothèse que l'ensemble des scénarios représentés implicitement via le modèle de sûreté établi peut être modélisé à l'aide d'un automate fini, ces travaux définissent la notion de cohérence des systèmes dynamiques et réparables, et le moyen d'obtenir une représentation minimale de l'ensemble des scénarios menant à la défaillance du système. / Preventive risk assessment of a complex system rely on a dynamic models which describe the link between the system failure and the scenarios of failure and repair events from its components. The qualitative analyses of a binary dynamic and repairable system is aiming at computing and analyse the scenarios that lead to the system failure. Since such systems describe a large set of those, only the most representative ones, called Minimal Cut Sequences (MCS), are of interest for the safety engineer. The lack of a formal definition for the MCS has generated multiple definitions either specific to a given model (and thus not generic) or informal. This work proposes i) a formal framework and definition for the MCS while staying independent of the reliability model used, ii) the methodology to compute them using property extracted from their formal definition, iii) an extension of the formal framework for multi-states components in order to perform the qualitative analyses of Boolean logic Driven Markov Processes (BDMP) models. Under the hypothesis that the scenarios implicitly described by any reliability model can always be represented by a finite automaton, this work is defining the coherency for dynamic and repairable systems as the way to give a minimal representation of all scenarios that are leading to the system failure.

Quantum computing has generated a lot of interested in the past two decades. Research into powerful models of quantum computation has yielded important and elegant results like an efficient algorithm for factoring and a quadratic speed-up for unordered search. At the same time, given the current difficulty in the physical implementation of these general purpose models, considerable effort has also been made in estimating the power of weaker models of quantum computation: models that have a small quantum component. The first part of this thesis is an investigation into the power of interference in quantum computing. While interference in probability amplitudes is a central feature even in powerful models, it is the only extra resource available to quantum finite automata. Of particular interest is interference in automata that have both classical and quantum states (2QCFA) as proposed by Ambainis and Watrous, since it inquires into the power of a classical deterministic finite automaton when augmented with a quantum component of constant size. Our contributions in this part are as follows: • To abstract out the phenomenon of interference in quantum computing, we propose a model called the 2-way Optical Interference Automata (2OIA). The model consists of a 2DFA augmented with a simple optical arrangement. We show different ways of harnessing the power of interference in the form of algorithms on this model to recognize some non-trivial languages. We then go on to show a language recognizable by a Turing machine using O(n2) space but by no 2OIA. • A natural classical model for comparison with 2QCFA is the weighted automaton, since it has the potential to capture interference in sum of path weights. Using the Cortes-Mohri definition of language recognition, we give an efficient simulation of 2QCFAwith algebraic amplitudes by weighted automata over the complex semi ring. • We introduce quantum non-determinism to the Measure-Once 1-way Quantum Finite Automata of Moore and Crutchfield and Kondacs and Watrous and show that even then, the model can recognize only regular languages with bounded error. • We propose a group theoretic generalization of counter automata that allows a notion of counter reversal complexity. To obtain this generalization, we combine concepts from classical counter automata theory with results in 2QCFA. We examine specific instances of this generalization and compare their ii iii powers. We also show an instance recognizing a language that is not recognized by conventional 2-way counter automata. Finally, we show a strict hierarchy among the 1-way versions of the instances Discussed. The second part of the thesis deals with Quantum Adiabatic Optimization algorithms. A common trick for designing faster quantum adiabatic algorithms is to apply the adiabatic condition locally at every instant. However it is often difficult to determine the instantaneous gap between the lowest two eigen values, which is an essential ingredient in the adiabatic condition. We present a simple linear algebraic technique for obtaining a lower bound on the instantaneous gap even in such a situation. As an illustration, we investigate the adiabatic unordered search of van Dam et al. and Roland and Cerf when the non-zero entries of the diagonal final Hamiltonian are perturbed by a polynomial (in logN, where N is the length of the unordered list) amount. We use our technique to derive a bound on the running time of a local adiabatic schedule in terms of the minimum gap between the lowest two eigenvalues.

Ever since Bengt Sigurd laid out the first comprehensive description of Swedish phonotactics in 1965, it has been the main point of reference within the field. This thesis attempts a new approach, by presenting a computational and statistical model of Swedish phonotactics, which can be built by any corpus of IPA phonetic script. The model is a weighted trie, represented as a finite state automaton, where states are phonemes linked by transitions in valid phoneme sequences, which adds the benefits of being probabilistic and expressible by regular languages. It was implemented using the Nordisk Språkteknologi (NST) pronunciation lexicon and was used to test against a couple of rulesets defined in Sigurd relating to initial two consonant clusters of phonemes and phoneme classes. The results largely agree with Sigurd's rules and illustrated the benefits of the model, in that it effectively can be used to pattern match against phonotactic information using regular expression-like syntax. / Ända sedan Bengt Sigurd lade fram den första övergripande beskrivningen av svensk fonotax 1965, så har den varit den främsta referenspunkten inom fältet. Detta examensarbete försöker sig på en ny infallsvinkel genom att presentera en beräkningsbar och statistisk modell av svensk fonotax som kan byggas med en korpus av fonetisk skrift i IPA. Modellen är en viktad trie, representerad som en ändlig automat, vilket har fördelarna av att vara probabilistisk och kunna beskrivas av reguljära språk. Den implementerades med hjälp av uttalslexikonet från Nordisk Språkteknologi (NST) och användes för att testa ett par regelgrupper av initiala två-konsonant kluster av fonem och fonemklasser definierad av Sigurd. Resultaten stämmer till större del överens med Sigurds regler och visar på fördelarna hos modellen, i att den effektivt kan användas för att matcha mönster av fonotaktisk information med hjälp av en liknande syntax för reguljära uttryck.

No description available.

Dans ce travail nous étudions les propriétés arithmétiques et statistiques d'une nouvelle classe de fonctions de comptage des chiffres appelées fonctions digitales restreintes. Nous présentons tout d'abord les principales propriétés des suites engendrées par une substitution ou un $q$-automate ainsi que la suite célèbre de Thue-Morse et ses généralisations, puis nous comparons ces notions avec celle de fonction digitale restreinte.Nous étudions ensuite les sommes d'exponentielles associées à ces fonctions digitales restreintes ainsi que leur application d'une part à l'étude de la répartition modulo 1 des fonctions digitales restreintes et d'autre part à l'étude des propriétés statistiques des suites arithmétiques définies par des fonctions digitales restreintes.Dans la dernière partie de ce travail on étudie la représentation géométrique de ces sommes d'exponentielle à la lumière des travaux antérieurs de Dekking et Mendès-France ce qui nous conduit à énoncer plusieurs problèmes ouverts. / In this work we study the arithmetic and statistic properties of a new class of digital counting functions called restricted digital functions. We first present the main properties of sequences generated by a substitution or a $q$-automate followed by presenting the famous Thue-Morse sequence and its generalizations, then we compare these notions with the one of the restricted digital function.We then study the exponential sums associated with these restricted digital function and their implementation on the one hand to the study of uniform distribution modulo 1 of these restricted digital functions and on the other, to the study of the statistical properties of the arithmetic sequences defined by restricted digital functions.In the last part of this work we study the geometric representation of these exponential sums in the light of previous works of Dekking and Mendès-France which leads us to announce several open problems.

The focus of this thesis is the comparison of languages and the reduction of automata used in network traffic monitoring. In this work, several approaches for approximate (language non-preserving) reduction of automata and comparison of their languages are proposed. The reductions are based on either under-approximating the languages of automata by pruning their states, or over-approximating the language by introducing new self-loops (and pruning redundant states later). The proposed approximate reduction methods and the proposed probabilistic distance utilize information from a network traffic. Formal guarantees with respect to a model of network traffic, represented using a probabilistic automaton are provided. The methods were implemented and evaluated on automata used in network traffic filtering.

Mnoho aplikací přijímá, odesílá a zpracovává data v textové podobě. Správné a bezpečné zpracování těchto dat je typicky zajištěno tzv. ošetřením řetězců (string sanitization). Pomocí metod formální verifikace je možné analyzovat takovéto operace s řetězci a prověřit, zda jsou správně navržené či implementované.  Naším cílem je vytvořit obecný nástroj pro analýzu systémů jejichž konfigurace lze kódovat pomocí slov z vhodné abecedy, a také jeho specializaci pro analýzu programů pracujících s řetězci. Nejprve jsou popsaný konečné automaty a převodníky a poté různé třídy a podtřídy symbolických převodníků, zejména pak jejich omezení. Na základě těchto informací je pak pro použití v analýze programů navržen nový typ symbolických převodníků. Dále je popsán regulární model checking, speciálně pak jeho variantu založenou na abstrakci automatů, tzv. ARMC, u kterého je známo že dokáže velmi úspěšně překonat problém stavové exploze u automatů a umožňuje nám tzv. dosáhnout pevného bodu v analýze. Poté je navržena vlastní analýza programů psaných v imperativním paradigmatu, a to zejména programů manipulujících s řetězci, založená na principech ARMC. Následuje popis vlastní implementace nástroje s důrazem na jeho praktické vlastnosti. Rovněž jsou popsaný důležité části knihovny AutomataDotNet, na které nástroj staví. Práci je uzavřena diskuzí experimentů s nástrojem provedených na příkladech z knihovny LibStranger.

O Dilema do Prisioneiro com n jogadores é um problema que ilustra a dificuldade na formação da cooperação em sociedades de indivíduos racionais. Diversos trabalhos foram feitos no sentido de compreender melhor os fatores que influenciam o surgimento e a evolução da cooperação nessas sociedades, sendo que muitos desses mostraram que a simulação deste tipo de problema carece de escalabilidade, o que impede a realização de experimentos que envolvam uma grande quantidade de agentes ou de parâmetros de teste. Este trabalho tem o intuito de aplicar conceitos de computação paralela para tratar este problema. Para tal, foi desenvolvido um sistema denominado PS2 E2 , evolução de um trabalho anterior, cuja utilização em alguns cenários possibilitou a verificação da influência de alguns parâmetros tais como o tamanho da população e a expressividade do modelo de representação de estratégias na utilidade global de um conjunto de agentes que jogam o Dilema do Prisioneiro com n jogadores. / The n-Player Prisoners Dilemma is a problem that illustrates the difficulty of cooperation formation in societies composed of rational individuals. Several studies were made to better understand the factors that influence the emergence and evolution of cooperation in these societies. Many of these showed that the simulation of this type of problem lacks scalability, which hinders the achievement of experiments involving a large number of agents or test parameters. This work intends to apply parallel computing concepts to treat this problem. To this end, it was developed a system called PS2 E2 , an evolution of a previous work, whose utilization in some scenarios allowed the verification of the influence of some parameters such as the population size and the expressiveness of the strategy representation model in the global utility of a society of agents that play the n-Player Prisoner Dilemma.

O Dilema do Prisioneiro com n jogadores é um problema que ilustra a dificuldade na formação da cooperação em sociedades de indivíduos racionais. Diversos trabalhos foram feitos no sentido de compreender melhor os fatores que influenciam o surgimento e a evolução da cooperação nessas sociedades, sendo que muitos desses mostraram que a simulação deste tipo de problema carece de escalabilidade, o que impede a realização de experimentos que envolvam uma grande quantidade de agentes ou de parâmetros de teste. Este trabalho tem o intuito de aplicar conceitos de computação paralela para tratar este problema. Para tal, foi desenvolvido um sistema denominado PS2 E2 , evolução de um trabalho anterior, cuja utilização em alguns cenários possibilitou a verificação da influência de alguns parâmetros tais como o tamanho da população e a expressividade do modelo de representação de estratégias na utilidade global de um conjunto de agentes que jogam o Dilema do Prisioneiro com n jogadores. / The n-Player Prisoners Dilemma is a problem that illustrates the difficulty of cooperation formation in societies composed of rational individuals. Several studies were made to better understand the factors that influence the emergence and evolution of cooperation in these societies. Many of these showed that the simulation of this type of problem lacks scalability, which hinders the achievement of experiments involving a large number of agents or test parameters. This work intends to apply parallel computing concepts to treat this problem. To this end, it was developed a system called PS2 E2 , an evolution of a previous work, whose utilization in some scenarios allowed the verification of the influence of some parameters such as the population size and the expressiveness of the strategy representation model in the global utility of a society of agents that play the n-Player Prisoner Dilemma.

This thesis studies the properties of finite automata recognizing sets of real vectors encoded in positional notation using an integer base. We consider both general infinite-word automata, and the restricted class of weak deterministic automata, used, in particular, as symbolic data structures for representing the sets of vectors definable in the first order additive theory of real and integer numbers. <br><br> In previous work, it has been established that all sets definable in the additive theory of reals and integers can be handled by weak deterministic automata regardless of the chosen numeration base. In this thesis, we address the reciprocal property, proving that the sets of vectors that are simultaneously recognizable in all bases, by either weak deterministic or Muller automata, are those definable in the additive theory of reals and integers. <br><br> Precisely, for weak deterministic automata, we establish that the sets of real vectors simultaneously recognizable in two multiplicatively independent bases are necessarily definable in the additive theory of reals and integers. For general automata, we show that the multiplicative independence is not sufficient, and we prove that, in this context, the sets of real vectors that are recognizable in two bases that do not share the same set of prime factors are exactly those definable in the additive theory of reals and integers. <br><br> Those results lead to a precise characterization of the sets of real vectors that are recognizable in multiple bases, and provide a theoretical justification to the use of weak automata as symbolic representations of sets. <br><br> As additional contribution, we also obtain valuable insight into the internal structure of automata recognizing sets of vectors definable in the additive theory of reals and integers.