Satisfiability Algorithm for Syntactic Read-k-times Branching Programs
Satisfiability Algorithm for Syntactic Read-k-times Branching Programs
复制标题
语法读取k次分支程序的可满足性算法
DOI：
10.1007/s00224-020-09996-3
复制
发表时间：
2020
影响因子：
0.5
通讯作者：
and Junichi Teruyama
中科院分区：
文献类型：
--
作者：
Atsuki Nagao;Kazuhisa Seto;and Junichi Teruyama
给定分支程序的可满足性是确定是否存在从根到1-sink的一致路径。在语法读k次分支程序中，每个变量在从根到汇的任何路径中最多出现k次。在本文的一个初步版本中，我们提供了一个可满足性算法的语法读k次分支程序与n个变量和medges运行的时间。在本文中，我们改进了边界fork= 2。更确切地说，我们证明了语法读两次分支程序的可满足性可以及时解决。我们的算法是基于Borodin，Razborov和Smolensky [计算复杂性，1993]所示的分解技术。
The satisfiability of a given branching program is to determine whether there exists a consistent path from the root to 1-sink. In a syntactic read-k-times branching program, each variable appears at mostktimes in any path from the root to a sink. In a preliminary version of this paper, we provide a satisfiability algorithm for syntactic read-k-times branching programs withnvariables andmedges that runs in time. In this paper, we improve the bounds fork= 2. More precisely, we show that the satisfiability of syntactic read-twice branching programs can be solved in time. Our algorithm is based on the decomposition technique shown by Borodin, Razborov and Smolensky [Computational Complexity, 1993].