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 $\mbox{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]$.
翻译：问题 DFA- 内科- 内科- 无私性 问一个特定数量的确定性自动数据是否接受一个共同的单词 。 一般来说, 这个问题是 PSPACE 完成的 。 这里, 我们调查了这个问题, 用于识别分散语言的交流性自动数据与自动数据亚类。 我们显示, 在两种情况下, DFA- 内科- 无私性都为NP 和 参数化的 $W [1]$( 其中输入自动数据的数量是参数), 当字母固定时 。 此外, 我们为表格非瞬间合并 确定了相同的结果, 这个问题是问数据库中多个表格的组合( 可能包含无值) 是否非空白 。 最后, 我们显示, 以长度约束参数为参数的 Bound NFA- 内无私性无私性, 是 $mbox{ co- w [2, $2, 硬, 其中输入字母为可变式输入式的自动数据, 和不确定性自定义的自动自动数据, 确认有限定的严格约束语言, 产生一个变式, $W[1] $1] 。
相关内容
Alphabet is mostly a collection of companies. This newer Google is a bit slimmed down, with the companies that are pretty far afield of our main internet products contained in Alphabet instead.https://abc.xyz/
微信扫码咨询专知VIP会员