论文标题
准确定性5' - > 3'Watson-Crick Automata
Quasi-deterministic 5' -> 3' Watson-Crick Automata
论文作者
论文摘要
Watson-Crick（WK）有限自动机正在使用DNA分子上的Watson-Crick胶带上工作。双链DNA分子包含两个链，每个链具有5'和3'端，这两条链与以下特性形成分子。链具有相同的长度，其5'至3'方向相反，在每个位置，这两个链的核苷酸具有相互补充的核苷酸（通过Watson-Crick互补关系）。因此，WK Automata有两个读数，每个链都有一个。在传统的WK Automata中，两个头部都以相同的物理方向读取整个输入，但是在5' - > 3'wk自动机中，头部从两个极端开始，并以相反的方向读取输入。在传感5' - > 3'wk自动机中，在头部相遇时，输入的过程将完成，并且该模型能够接受无线性上下文语言的类别。确定性变体较弱，命名为2Detlin的类，线性语言的适当子类被它们接受。最近，研究了另一种特定的变体，即状态确定的传感5' - > 3'wk自动机，其中自动机的图具有特殊属性，该特殊属性是图形的每个节点，所有边缘（如果有）（如果有的话）都可以直接通过直接过渡到达每个状态的唯一节点，即最多有一个状态。结果表明，如果传感5' - > 3'wk automata，这个概念与确定论的通常概念有些正交。在本文中，一个新的概念，即准确确定性，即在计算的每种配置中（如果尚未完成），下一个状态是唯一确定的，尽管下一个配置可能没有，以防同一时间启用各种过渡。我们表明，这个新概念是对通常的决定论和状态决策的共同概括，即准确定性传感5' - > 3'wk automata是其他两个类别的超级阶级。 WK自动机（例如无状态或1限值变体）有各种常规限制。我们还证明了由准决 - 确定性传感5' - > 3'WK自动机的各种子类接受的语言类别中的一些层次结构结果，以及其他一些已知的语言类。
Watson-Crick (WK) finite automata are working on a Watson-Crick tape, that is, on a DNA molecule. A double stranded DNA molecule contains two strands, each having a 5' and a 3' end, and these two strands together form the molecule with the following properties. The strands have the same length, their 5' to 3' directions are opposite, and in each position, the two strands have nucleotides that are complement of each other (by the Watson-Crick complementary relation). Consequently, WK automata have two reading heads, one for each strand. In traditional WK automata both heads read the whole input in the same physical direction, but in 5'->3' WK automata the heads start from the two extremes and read the input in opposite direction. In sensing 5'->3' WK automata, the process on the input is finished when the heads meet, and the model is capable to accept the class of linear context-free languages. Deterministic variants are weaker, the class named 2detLIN, a proper subclass of linear languages is accepted by them. Recently, another specific variants, the state-deterministic sensing 5'->3' WK automata are investigated in which the graph of the automaton has the special property that for each node of the graph, all out edges (if any) go to a sole node, i.e., for each state there is (at most) one state that can be reached by a direct transition. It was shown that this concept is somewhat orthogonal to the usual concept of determinism in case of sensing 5'->3' WK automata. In this paper a new concept, the quasi-determinism is investigated, that is in each configuration of a computation (if it is not finished yet), the next state is uniquely determined although the next configuration may not be, in case various transitions are enabled at the same time. We show that this new concept is a common generalisation of the usual determinism and the state-determinism, i.e., the class of quasi-deterministic sensing 5'->3' WK automata is a superclass of both of the mentioned other classes. There are various usual restrictions on WK automata, e.g., stateless or 1-limited variants. We also prove some hierarchy results among language classes accepted by various subclasses of quasi-deterministic sensing 5'->3' WK automata and also some other already known language classes.
