scientific article; zbMATH DE number 7376042

DOI10.4230/LIPIcs.ICALP.2018.115zbMath1499.68166arXiv1707.04310MaRDI QIDQ5002800

Antoine Amarilli, Charles Paperman

Publication date: 28 July 2021

Full work available at URL: https://arxiv.org/abs/1707.04310

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

regular languagetopological sortingshuffle problem

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

Constrained synchronization and subset synchronization problems for weakly acyclic automata ⋮ Computational complexity of synchronization under sparse regular constraints ⋮ Ideal separation and general theorems for constrained synchronization and their application to small constraint automata ⋮ Constrained synchronization and commutativity ⋮ Computing possible and certain answers over order-incomplete data

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of iterated shuffle
• The method of forced enumeration for nondeterministic automata
• On the computational complexity of a merge recognition problem
• Sur le produit de concatenation non ambigu
• Reconstructing a history of recombinations from a set of sequences
• Polynomial closure of group languages and open sets of the Hall topology
• Polynomial closure and unambiguous product
• Unshuffling a square is NP-hard
• A decomposition theorem for partially ordered sets
• The complexity of temporal constraint satisfaction problems
• Nondeterministic Space is Closed under Complementation
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Scheduling Parallel DAG Jobs Online to Minimize Average Flow Time
• The NP-completeness column: An ongoing guide

This page was built for publication: