Institut de Mathématiques de Marseille, UMR 7373




Rechercher


Accueil > Séminaires > Séminaires et Groupes de travail hebdomadaires > Dynamique, Arithmétique, Combinatoire (Ernest)

Séminaire Dynamique, Arithmétique, Combinatoire (Ernest)

par Drappeau Sary, Guillon Pierre, Lozingot Eric, Merlet Glenn - publié le , mis à jour le

Agenda

Séminaire

  • Mardi 24 janvier 11:00-12:00 - Andrew RYZHIKOV - Université Grenoble Alpes

    Synchronization Problems in Automata Without Non-trivial Cycles

    Résumé : The concept of synchronization in automata theory is a formalization of the idea of returning control over an automaton in a situation where its current state in unknown. If the current state is known to be in some particular subset of states, checking whether the control can be returned (the subset synchronization problem) is known to be a PSPACE-complete problem. I will speak about the restriction of this problem to the class of weakly acyclic automata, which are the automata containing no cycles other than self-loops in their underlying digraph. Such automata form a proper subclass of well-studied aperiodic automata. In the class of weakly acyclic automata many synchronization problems remain surprisingly hard. In particular, the subset synchronization problem is NP-complete, and its generalization, the problem of computing the rank of a subset of states, is hard to approximate within a polynomial factor. The results remain true even in the case where the alphabet of the automaton is binary. I will show the connection of the mentioned problems with the problem of finding the chromatic number of a graph and provide some other problems that are hard in the class of weakly acyclic automata.

    JPEG - 11.3 ko
    Andrew RYZHIKOV

    Lieu : Salle des séminaires 304-306 (3ème étage) - Institut de Mathématiques de Marseille (UMR 7373)
    Site Sud
    Campus de Luminy, Case 907
    13288 MARSEILLE Cedex 9

    Exporter cet événement

groupe de travail

Manifestation scientifique

Descriptif
Nature Séminaire
Intitulé Dynamique, Arithmétique, Combinatoire (Ernest)
Responsables Sary Drappeau & Pierre Guillon
Équipe de rattachement Géométrie, Dynamique, Arithmétique, Combinatoire
et leurs interactions (GDAC)
Fréquence Hebdomadaire
Jour-Horaire Mardi. 
11h05-12h
Lieu Luminy, salle des séminaires 304-306 (accès)
Lien -