License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.115
URN: urn:nbn:de:0030-drops-91193
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9119/
Go to the corresponding LIPIcs Volume Portal

Amarilli, Antoine ; Paperman, Charles

Topological Sorting with Regular Constraints

pdf-format:
LIPIcs-ICALP-2018-115.pdf (0.4 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{amarilli_et_al:LIPIcs:2018:9119,
  author =	{Antoine Amarilli and Charles Paperman},
  title =	{{Topological Sorting with Regular Constraints}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{115:1--115:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9119},
  URN =		{urn:nbn:de:0030-drops-91193},
  doi =		{10.4230/LIPIcs.ICALP.2018.115},
  annote =	{Keywords: Topological sorting, shuffle problem, regular language}
}

Keywords: Topological sorting, shuffle problem, regular language
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI