Posts classified under: General

Automata (DFA) are state machines that accept or reject words. The set of words recognized by an automaton is its its language. Regular languages coincide with languages that can be recognized by automata. Here, we’re going to focus on a measure, namely state complexity. For rational languages, this is defined as the size of the … Continue reading Séminaire Algorithmique : « State complexity: Inverting a language reduces the complexity of the root operation », Alexandre Durand (LITIS, Univ. Rouen)

We consider the problem of learning a logical formula from a set of positive and negative examples. The logic we target is Linear Temporal Logic (LTL), a prominent formalism in program verification and analysis, software engineering, and robot motion planning. We’ll discuss on the one hand theoretical results, in particular NP-completeness, and on the other … Continue reading Séminaire Algorithmique : « Learning Linear Temporal Logic », Nathanaël Fijalkow (CNRS, LaBRI, Univ. Bordeaux)

Consider a graph drawn on a surface (for example, the plane minus a finite set of obstacle points), possibly with crossings. We provide a polynomial time algorithm to decide whether such a drawing can be untangled, namely, if one can slide the vertices and edges of the graph on the surface (avoiding the obstacles) to … Continue reading Séminaire Algorithmique : « Untangling Graphs on Surfaces », Loïc Dubois (LIGM, Univ. G.Eiffel)

Je présente l’application pratique du codage et de l’algorithmisation corécursive (extrapolatrice, paresseuse, qui engendre des flots “infinis”) dans le domaine du calcul scientifique : la manipulation des suites illimitées de dérivées “automatiques” du code numérique. Je discute l’usage du langage fonctionnel Haskell dans le traitement des structures comme les séries formelles ou les approximants de Padé. La … Continue reading Séminaire Algorithmique : « Corecursivity and higher-order computational differentiation, and some applications », Jerzy Karczmarczuk (GREYC, Caen)

Le Générateur Sac à dos, proposé en 1985 par Rueppel et Massey est un générateur pseudo aléatoire (PRNG) qui combine un premier PRNG faible, le LFSR, et un problème dur ,le problème de la somme de sous-ensemble, dérivé du problème de sac à dos. Ce générateur a été attaqué avec succès par Knellwolf et Meyer … Continue reading Séminaire Algorithmique : « Discussion autour du Générateur Sac à dos », Florette Martinez (ENS Ulm)

Nowadays, most of our communications over the Internet are encrypted. However, some cryptographic constructions widely deployed today are vulnerable to quantum attacks, and the goal of post-quantum cryptography is to design classical cryptosystems based on computational problems which remain hard even with the help of quantum computers. In this talk, I will give an introduction … Continue reading Séminaire Algorithmique : « Hardness of the Decoding Problem and its Applications in Post-Quantum Cryptography », Maxime Bombar (CWI, Amsterdam, Pays-Pas)

While rotations are bijections that preserve distances and angles in Euclidean space, these geometric properties are not preserved in general when rotations are applied to digital images. In this talk, we particularlly focus on bijection and topology, which are also generally lost. With regard to bijections, we present the set of rotations that give bijective … Continue reading Séminaire Algorithmique : « How to rotate digital images without losing information? », Yukiko Kenmochi (GREYC, Caen)