Combinatorial filter reduction: Special cases, approximation, and fixed-parameter tractability
作者：
Highlights：
• Combinatorial filters are reduced automatically, such that the reduced filter's behavior is the same as that of input filter.
• Some hardness results for special cases of the general problem are introduced.
• The general problem and its NP-hard special cases are also NP-hard to approximate.
• The optimality of the only heuristic algorithm for this problem is analyzed to find some parameters for bounding the difficulty of the problem.
• Some fixed-parameter tractability and intractability results are presented for the general and special cases of the problem.
摘要
•Combinatorial filters are reduced automatically, such that the reduced filter's behavior is the same as that of input filter.•Some hardness results for special cases of the general problem are introduced.•The general problem and its NP-hard special cases are also NP-hard to approximate.•The optimality of the only heuristic algorithm for this problem is analyzed to find some parameters for bounding the difficulty of the problem.•Some fixed-parameter tractability and intractability results are presented for the general and special cases of the problem.
论文关键词：Combinatorial filters,Reduction,Automata,Approximation,Fixed-parameter
论文评审过程：Received 25 April 2016, Revised 9 November 2016, Accepted 11 November 2016, Available online 22 November 2016, Version of Record 19 December 2016.
论文官网地址：https://doi.org/10.1016/j.jcss.2016.11.007
