A multi-parameter analysis of hard problems on deterministic finite automata

作     者：Fernau, Henning Heggernes, Pinar Villanger, Yngve 

作者机构：Univ Trier Fachbereich 4 Abt Informat Wissensch D-54286 Trier Germany Univ Bergen Dept Informat N-5020 Bergen Norway 

出 版 物：《JOURNAL OF COMPUTER AND SYSTEM SCIENCES》 (计算机与系统科学杂志)

年 卷 期：2015年第81卷第4期

页      面：747-765页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Norwegian German Research Councils 

主　　题：Deterministic finite automata NP-hard decision problems Synchronizing word Consistency problem 

摘      要：We initiate a multi-parameter analysis of two well-known NP-hard problems on deterministic finite automata (DFAs): the problem of finding a short synchronizing word, and that of finding a DFA on few states consistent with a given sample of the intended language and its complement. For both problems, we study natural parameterizations and classify them with the tools provided by Parameterized Complexity. Somewhat surprisingly, in both cases, rather simple FPT algorithms can be shown to be optimal, mostly assuming the (Strong) Exponential Time Hypothesis. (C) 2014 Elsevier Inc. All rights reserved.