论文标题
可以有效最小化的一般组合过滤器类
A general class of combinatorial filters that can be minimized efficiently
论文作者
论文摘要
组合过滤器的最小化是一个基本问题，例如在建造便宜，资源有效的机器人中。但是，已知确切的最小化是NP-HARD。本文比到目前为止对这种硬度进行了更细微的分析，并发现了有助于这种复杂性的两个因素。我们表明，每个因素都是问题硬度的独特来源，因此能够阐明（1）图表的（1）编码兼容性关系的结构的作用，以及（2）确定性 - 实现约束。就像先前的一系列工作试图引入其他假设并确定导致实际状态减少的子类一样，我们接下来使用这种新的，更加敏锐的理解来探索特殊案例，以便为哪些确切的最小化是有效的。我们引入了一种用于约束修复的新算法，该算法适用于大型子类过滤器，其中包含了三种不同的特殊情况，以前已知多项式时间最小化最小化的可能性。尽管这三种情况中每种情况的效率似乎都源于看似不同的特性，而当通过本工作的镜头看到时，它们的共同点现在变得很明显。我们还提供了有效降低的全新过滤器家庭。
State minimization of combinatorial filters is a fundamental problem that arises, for example, in building cheap, resource-efficient robots. But exact minimization is known to be NP-hard. This paper conducts a more nuanced analysis of this hardness than up till now, and uncovers two factors which contribute to this complexity. We show each factor is a distinct source of the problem's hardness and are able, thereby, to shed some light on the role played by (1) structure of the graph that encodes compatibility relationships, and (2) determinism-enforcing constraints. Just as a line of prior work has sought to introduce additional assumptions and identify sub-classes that lead to practical state reduction, we next use this new, sharper understanding to explore special cases for which exact minimization is efficient. We introduce a new algorithm for constraint repair that applies to a large sub-class of filters, subsuming three distinct special cases for which the possibility of optimal minimization in polynomial time was known earlier. While the efficiency in each of these three cases previously appeared to stem from seemingly dissimilar properties, when seen through the lens of the present work, their commonality now becomes clear. We also provide entirely new families of filters that are efficiently reducible.
