Evènement pour le groupe Séminaire Méthodes Formelles

Date 2019-05-07  11:00-12:00
TitreTopological Sorting under Regular Constraints 
RésuméIn this talk, I will present a joint work with Antoine Amarilli, published at ICALP 18 about what we call the constrained topological sorting problem (CTS): given a regular language K and a directed acyclic graph G with labeled vertices, determine if G has a topological sort that forms a word in K. This natural problem applies to several settings, e.g., scheduling with costs or verifying concurrent programs. I will present a complexity study to solve this problem with respect to some properties of the target regular language.  
OrateurCharles Paperman 
UrlUniversité de Lille 

Aucun document lié à cet événement.

Retour à l'index