An algorithm to find optimum support-reducing decompositions for index generation functions
An algorithm to find optimum support-reducing decompositions for index generation functions
复制标题
一种寻找索引生成函数最佳支持减少分解的算法
DOI：
10.23919/date.2017.7927100
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Y. Iguchi
中科院分区：
文献类型：
--
作者：
Tsutomu Sasao;Kyu Matsuura;Y. Iguchi
索引生成函数对于模式匹配很有用。本文提出了一种寻找索引生成函数支持度降低分解的算法。令 n 为输入变量的数量，令 s 为绑定变量的数量。然后，寻找最佳支持减少分解的详尽搜索需要检查（ns）个组合。我们发现索引生成函数的一个特殊属性可以大大减少搜索空间。利用这一特性，我们开发了一种快速算法。对于给定数量的绑定变量，它会找到具有最少轨道的分解。显示了直至 n = 60 和 s = 33 的实验结果。
Index generation functions are useful for pattern matching. This paper presents an algorithm to find support-reducing decompositions for index generation functions. Let n be the number of the input variables, and let s be the number of bound variables. Then, the exhaustive search for finding an optimum support-reducing decomposition requires to check (ns) combinations. We found a special property of index generation functions that drastically reduces this search space. With this property, we developed a fast algorithm. For a given number of bound variables, it finds a decomposition with the fewest rails. Experimental results up to n = 60 and s = 33 are shown.