2021/08/11 by Henning Fernau, Stefan Hoffmann, Fernau, Henning +3
Computer Science · #68Q45 (Primary) 68Q19 (Secondary) #Computational Complexity (cs.CC) #Databases (cs.DB) #F.1.3 #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #Machine Learning and Algorithms #acm:68Q19 #acm:68Q45 #cs.CC #cs.DB #cs.FL #msc:68Q19 #msc:68Q45 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2108.05244
arxiv created 2021/08/11 · openalex publication_date 2021/08/11 · arxiv updated 2021/08/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The problem DFA-Intersection-Nonemptiness asks if a given number of deterministic automata accept a common word. In general, this problem is PSPACE-complete. Here, we investigate this problem for the subclasses of commutative automata and automata recognizing sparse languages. We show that in both cases DFA-Intersection-Nonemptiness is complete for NP and for the parameterized class W[1], where the number of input automata is the parameter, when the alphabet is fixed. Additionally, we establish the same result for Tables Non-Empty Join, a problem that asks if the join of several tables (possibly containing null values) in a database is non-empty. Lastly, we show that Bounded NFA-Intersection-Nonemptiness, parameterized by the length bound, is co-W[2]-hard with a variable input alphabet and for nondeterministic automata recognizing finite strictly bounded languages, yielding a variant leaving the realm of W[1].