论文标题
Watson-Crick无上下文语法的会员问题的实际方面
Practical Aspects of Membership Problem of Watson-Crick Context-free Grammars
论文作者
论文摘要
本文着重于受DNA计算，其模型和算法来决定语言成员资格的沃森 - 克里克语言。它分析了一种名为WK-Cyk的最近引入的算法，并引入了基于常规广度优先搜索的状态空间搜索算法，但使用多种优化和启发式方法在实际使用方面有效，并能够分析更长的输入。关键部分是修剪状态空间的启发式方法（检测死胡同），以及选择最有前途的分支来继续搜索的启发式方法。 这两种算法已经用20种不同的Watson-Crick语法（包括其Chomsky正常形式版本）进行了测试。尽管WK-cyk能够在合理的时间内确定语言会员资格的大约30-50个符号的输入，并且其性能对于各种语法和投入都非常一致，但状态空间搜索通常（89-98％的情况）通常更有效，并且能够进行计算，以便对具有数百张符号甚至数千的输入进行计算。因此，国家空间搜索有可能成为实用的Watson-Crick会员测试的好工具，并且是提高未来算法效率的好基础。
This paper focuses on Watson-Crick languages inspired by DNA computing, their models, and algorithms for deciding the language membership. It analyzes a recently introduced algorithm called WK-CYK and introduces a state space search algorithm that is based on regular Breadth-first search but uses a number of optimizations and heuristics to be efficient in practical use and able to analyze longer inputs. The key parts are the heuristics for pruning the state space (detecting dead ends) and heuristics for choosing the most promising branches to continue the search. These two algorithms have been tested with 20 different Watson-Crick grammars (40 including their Chomsky normal form versions). While WK-CYK is able to decide the language membership in a reasonable time for inputs of the length of roughly 30-50 symbols and its performance is very consistent for all kinds of grammars and inputs, the state space search is usually (89-98 % of cases) more efficient and able to do the computation for inputs with lengths of hundreds or even thousands of symbols. Thus, the state space search has the potential to be a good tool for practical Watson-Crick membership testing and is a good basis for improvement the efficiency of the algorithm in the future.
