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. |