Titre :

Topological Sorting with Regular Constraints

Auteur(s) :

Amarilli, Antoine [Auteur]
Département Informatique et Réseaux [INFRES]
Data, Intelligence and Graphs [DIG]
Paperman, Charles [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Linking Dynamic Data [LINKS]

Titre de la manifestation scientifique :

ICALP 2018 - 45th International Colloquium on Automata, Languages, and Programming

Ville :

Prague

Pays :

République tchèque

Date de début de la manifestation scientifique :

2018-07-09

Titre de la revue :

45th International Colloquium on Automata, Languages, and Programming, ICALP 2018

Date de publication :

2018-07-13

Mot(s)-clé(s) en anglais :

Topological sort
shuffle problem
regular language

Discipline(s) HAL :

Informatique [cs]/Algorithme et structure de données [cs.DS]
Informatique [cs]/Complexité [cs.CC]
Informatique [cs]/Mathématique discrète [cs.DM]

Résumé en anglais : [en]

We introduce 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 ...
Lire la suite >We introduce 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. We consider the problem CTS[K] where the target language K is fixed, and study its complexity depending on K. We show that CTS[K] is tractable when K falls in several language families, e.g., unions of monomials, which can be used for pattern matching. However, we show that CTS[K] is NP-hard for K = (ab) * and introduce a shuffle reduction technique to show hardness for more languages. We also study the special case of the constrained shuffle problem (CSh), where the input graph is a disjoint union of strings, and show that CSh[K] is additionally tractable when K is a group language or a union of district group monomials. We conjecture that a dichotomy should hold on the complexity of CTS[K] or CSh[K] depending on K, and substantiate this by proving a coarser dichotomy under a different problem phrasing which ensures that tractable languages are closed under common operators.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL