Calendrier d’événements

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)