标题： 一种2detLIN语言的Myhill-Nerode类型特征化 显示英文标题

标题： A Myhill-Nerode Type Characterization of 2detLIN Languages

摘要： 线性自动机是具有两个读取头的自动机，从输入的两个端点开始，等价于5' -> 3' Watson-Crick (WK) 有限自动机。 这两个读取头以相反方向读取输入，当读取头相遇时计算结束。 这些自动机接受线性语言类 LIN。 这些模型的确定性对应物一方面表达能力较弱，因为只接受 LIN 的一个真子集，即类 2detLIN；另一方面，它们在所接受语言类的意义上也是等价的。 现在，基于这些自动机模型，我们用类似 Myhill-Nerode 的等价类来表征 2detLIN 语言类。 然而，由于这些自动机可以对输入的前缀和后缀进行计算，我们在等价类中使用前缀-后缀对。 此外，证明了在表征中有限多个等价类与 2detLIN 语言匹配，但我们对使用的前缀-后缀对有一些约束，即表征应具有完备性，并且不能有任何交叉对。 显示英文摘要

摘要： Linear automata are automata with two reading heads starting from the two extremes of the input, are equivalent to 5' -> 3' Watson-Crick (WK) finite automata. The heads read the input in opposite directions and the computation finishes when the heads meet. These automata accept the class LIN of linear languages. The deterministic counterpart of these models, on the one hand, is less expressive, as only a proper subset of LIN, the class 2detLIN is accepted; and on the other hand, they are also equivalent in the sense of the class of the accepted languages. Now, based on these automata models, we characterize the class of 2detLIN languages with a Myhill-Nerode type of equivalence classes. However, as these automata may do the computation of both the prefix and the suffix of the input, we use prefix-suffix pairs in our classes. Additionally, it is proven that finitely many classes in the characterization match with the 2detLIN languages, but we have some constraints on the used prefix-suffix pairs, i.e., the characterization should have the property to be complete and it must not have any crossing pairs.