87 research outputs found
Logical Fragments for Mazurkiewicz Traces: Expressive Power and Algebraic Characterizations
No full textAcknowledgments First and foremost, I would like to thank my supervisor Volker Diekert for his continual motivation and support over all my years in his group. He recommended the topic of this thesis to me and provided valuable guidance and advice. Furthermore I would like to thank Ulrich Hertrampf and Pascal Weil. I also wish to express my gratitude to Holger Austinat, Martin Horsch, Martin Müller and Pascal Tesson for many interesting discussions on topics of this thesis. Last but not least I want to thank all members our department for a very pleasant and likeable ambience
Le problème de décision CSP : homomorphismes et espace logarithmique
No full textCe mémoire porte sur le problème de décision CSP (de l'anglais Constraint Satisfaction Problem, c'est-à-dire problème de satisfaction de contraintes), soit le problème pour lequel nous devons assigner des valeurs à des variables de telle sorte que toutes les conditions portant sur ces variables soient remplies. De surcroît, ce mémoire porte sur les problèmes de détection d'homomorphisme entre structures relationelles qui sont équivalents à CSP. Pour être plus précis, nous nous intéressons à l'algorithme de cohérence d'arc pour les instances de CSP, soit ArcjConsistency. Celui-ci suffit à solutionner un certain sous-ensemble de CSP. Or nous étudions quelques-unes de ses variantes qui sont des algorithmes plus coûteux, mais plus puissants, c'est-à-dire que le sous-ensemble de CSP qu'ils solutionnent est plus grand. La nouveauté de ce mémoire est de décrire et d'étudier une variante de ArcjConsistency, soit NLjCohérence, qui est un algorithme moins puissant mais plus efficace. L'objectif pour nous est de trouver des caractéristiques intéressantes au sujet de ce nouvel algorithme, qui se veut être une version « espace logarithmique » de ArcjConsistency. De plus, nous travaillons sur un sous-ensemble de CSP dit implicatif. Nous démontrons que NL_Cohérence solutionne les instances de ce sous-ensemble en espace logarithmique non-déterministe
Problèmes d'homomorphisme à largeur de chemin bornée
No full textUn homomorphisme est une fonction entre deux structures, par exemple des graphes, qui respecte certaines contraintes. Dans ce mémoire, on étudie la complexité des problèmes d'homomorphisme, c'est-à-dire des problèmes où l'on doit décider s'il existe une telle fonction entre deux structures. On présentera des propriétés sur ces structures qui permettent de déterminer cette complexité. On s'intéressera particulièrement aux problèmes d'homomorphisme qui appartiennent à la classe de complexité NL, une classe contenant des problèmes dont la résolution par un algorithme non déterministe nécéssite peu d'espace mémoire
De la sécurité calculatoire des protocoles cryptographiques devant la menace quantique
No full textOn ne s’en inquiète peut-être pas assez, mais toute communication confidentielle sur Internet, dont on prend désormais la sécurité pour acquise, pourrait du jour au lendemain devenir très facile à espionner. Nous savons en effet qu’un ordinateur quantique, s’il en existe un de suffisante envergure, pourra –ou peut déjà, qui sait ?– rendre obsolète les protocoles cryptographiques qui nous permettent de gérer nos comptes utilisateurs, faire des transactions bancaires et simplement d’avoir des conversations privées. Heureusement, une communauté de chercheurs se penche déjà sur des protocoles alternatifs ; cependant chacune des propositions est isolée dans son propre sous-domaine de recherche et il est difficile de faire la lumière sur laquelle est la plus prometteuse. À travers trois horizons, explorant respectivement pourquoi la cryptographie actuelle est considérée sécuritaire, comment l’arrivée d’un seul ordinateur quantique sur la planète changera toute la cryptographie, et que faire pour communiquer confidentiellement dans un monde où l’informatique quantique est omniprésente, nous développons un cadre uniforme pour analyser lesquels de ces nouveaux protocoles cryptographiques sont assis sur les bases théoriques présageant la plus grande sécurité
Les langages testables par morceaux
No full textTableau d'honneur de la Faculté des études supérieures et postdoctorales, 2011-2012Une des questions incontournables qu'on se pose en théorie des langages est de savoir si une logique est décidable. Autrement dit, pour une logique donnée, on veut savoir s'il existe un algorithme qui détermine si un langage donné est exprimable dans cette logique. Depuis les travaux de Schützenberger, McNaughton et Papert sur la logique de premier ordre sur les mots, on reconnait l'importance de la théorie algébrique des langages pour résoudre ces questions de décidabilité. Un autre exemple historique est la caractérisation de Simon des langages testables par morceaux de mots par les monodes J -triviaux. On dit qu'un langage est testable par morceaux si on peut le définir par une combinaison booléenne d'expressions régulieres de la forme [symbol]. Ces langages sont exactement ceux qui sont définis par la clôture booléenne de [symbol] et le théorème de Simon engendre un algorithme qui en resout la décidabilité. Suite aux succès sur les mots, on a attaque les mêmes questions de décidabilité de logiques sur les langages de forêts, plus spéciquement sur les langages d'arbres. Dernièrement, Bojanczyk, Segoufin et Straubing ont pu démontrer un analogue du théorème de Simon pour les forêts. En effet, ils ont pu caractériser la clôture booléenne de [symbol], c'est-à-dire les langages testables par morceaux, en fonction d'une structure algébrique nommée algèbre de forêts. Ce mémoire est d'abord un état de l'art de la théorie algébrique des langages testables par morceaux. Entre autres, nous présentons le théorème de Simon sur les mots en passant par un résultat de Straubing et Thérien qui utilise la théorie des monodes partiellement ordonnés. Ensuite, nous étudions un pendant de ce résultat pour les algèbres de forêts. Finalement, nous règlons la décidabilité des langages de mots bien emboîtés testables par morceaux, une sous-classe des langages visiblement à pile. En efet, nous proposons un algorithme qui utilise le résultat de Bojanczyk, Segoufin et Straubing sur les langages de forêts
The Complexity of the List Homomorphism Problem for Graphs
No full textWe completely classify the computational complexity of the list \bH-colouring problem for graphs (with possible loops) in combinatorial and algebraic terms: for every graph \bH the problem is either NP-complete, NL-complete, L-complete or is first-order definable; descriptive complexity equivalents are given as well via Datalog and its fragments. Our algebraic characterisations match important conjectures in the study of constraint satisfaction problems
Étude d'un algorithme pour 2-SAT via les opérations de majorité-minorité généralisées
No full textLes problèmes de satisfaction de contraintes sont parmi les problèmes fréquents qu'on trouve dans des domaines variés tels que la recherche opérationnelle et l'intelligence artificielle. Dans un problème de satisfaction de contraintes, on cherche à assigner aux variables des valeurs de telle sorte que toutes les contraintes fournies en entrée soient satisfaites. Chaque contrainte est une paire contenant un tuple de variables et une relation définissant les combinaisons de valeurs autorisées pour ce tuple. Ce problème est NP-complet, donc il est important d'identifier des cas particuliers résolubles en temps polynomial. Dans ce travail, on s'intéresse à une approche dite algébrique pour découvrir des classes de problèmes de satisfaction de contraintes traitables efficacement. On se base sur le résultat prouvé par Dalmau "en 2006" qui donne un algorithme polynomial pour une classe assez vaste de problèmes. On analyse et implémente un cas particulier de cet algorithme qui permet de résoudre des instances de 2-SAT. Cette implementation nous aidera à faire des expérimentations et à en apprendre plus sur la nature de l'algorithme de Dalmau et son comportement en pratique
An algebraic approach to communication complexity /
No full textIn this work, we define the communication complexity of a monoid M as the maximum complexity of any language recognized by M, and show that monoid classes defined by, communication complexity classes form varieties. Then we prove that a group G has constant communication complexity for k players if and only if G is a nilpotent group of class at most ( k - 1), and has linear complexity otherwise. When M is aperiodic, we show that its 2-party communication complexity is constant if M is commutative, logarithmic if M is not commutative but is in the variety DA, and is linear otherwise. Moreover, we show that if M is in DA, there exists a k such that M has constant k-party communication complexity. We conjecture that this condition is also necessary and prove lower bounds in that direction.These results lead us to state a conjecture which would generalize Szegedy's theorem to O(1) players. They also suggest several interesting possibilities to further uncover algebraic characterizations of communication complexity classes. (Abstract shortened by UMI.
Computational complexity questions related to finite monoids and semigroups
No full textIn this thesis, we address a number of issues pertaining to the computational power of monoids and semigroups as machines and to the computational complexity of problems whose difficulty is parametrized by an underlying semigroup or monoid and find that these two axes of research are deeply intertwined.We first consider the "program over monoid" model of D. Barrington and D. Therien [BT88] and set out to answer two fundamental questions: which monoids are rich enough to recognize arbitrary languages via programs of arbitrary length, and which monoids are so weak that any program over them has an equivalent of polynomial length? We find evidence that the two notions are dual and in particular prove that every monoid in DS has exactly one of these two properties. We also prove that for certain "weak" varieties of monoids, programs can only recognize those languages with a "neutral letter" that can be recognized via morphisms over that variety.We then build an algebraic approach to communication complexity, a field which has been of great importance in the study of small complexity classes. We prove that every monoid has communication complexity O(1), &THgr;(log n) or &THgr;(n) in this model. We obtain similar classifications for the communication complexity of finite monoids in the probabilistic, simultaneous, probabilistic simultaneous and MOD p-counting variants of this two-party model and thus characterize the communication complexity (in a worst-case partition sense) of every regular language in these five models. Furthermore, we study the same questions in the Chandra-Furst-Lipton multiparty extension of the classical communication model and describe the variety of monoids which have bounded 3-party communication complexity and bounded k-party communication complexity for some k. We also show how these bounds can be used to establish computational limitations of programs over certain classes of monoids.Finally, we consider the computational complexity of testing if an equation or a system of equations over some fixed finite monoid (or semigroup) has a solution
Garside combinatorics for Thompson's monoid and a hybrid with the braid monoid
No full textOn the model of simple braids, defined to be the left divisors of Garside's elements in the monoid , we investigate simple elements in Thompson's monoid and in a larger monoid that is a hybrid of and : in both cases, we count how many simple elements left divide the right lcm of the first n − 1 atoms, and characterize their normal forms in terms of forbidden factors. In the case of , a generalized Pascal triangle appears
- …
