Resynchronizing Classes of Word Relations
Resynchronizing Classes of Word Relations
复制标题
重新同步词关系类
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Gabriele Puppis
中科院分区：
文献类型：
--
作者：
M. E. Descotte;Diego Figueira;Gabriele Puppis
在有限字母A上定义二元词关系的一种自然方法是通过两带有限状态自动机，它可以看作是正则语言L / {1,2}xA，其中（i， A）被解释为从磁带i读取字母A。因此，语言L中的单词w表示A^* *中的（u_1,u_2）对，其中u_i是w在i标记字母上的投影。虽然这种形式定义了被充分研究过的Rational关系类（又名非确定性有限状态传感器），但是对从磁带读取的机制施加限制，我们称之为同步，产生了关系的各种子类。这种同步限制是通过对语言在{1,2}上的投影的规则属性施加的。这样，对于每一个正则语言C子集q{1,2}^*，我们得到一个类Rel(C)的关系，如正则类，可识别类，或保长类，以及（无限）许多其他类。
A natural approach to defining binary word relations over a finite alphabet A is through two-tape finite state automata, which can be seen as regular language L over {1,2}xA, where (i,a) is interpreted as reading letter a from tape i. Thus, a word w of the language L denotes the pair (u_1,u_2) in A^* imes A^* in which u_i is the projection of w onto i-labelled letters. While this formalism defines the well-studied class of Rational relations (a.k.a. non-deterministic finite state transducers), enforcing restrictions on the reading regime from the tapes, that we call synchronization, yields various sub-classes of relations. Such synchronization restrictions are imposed through regular properties on the projection of the language onto {1,2}. In this way, for each regular language C subseteq {1,2}^*, one obtains a class Rel(C) of relations, such as the classes of Regular, Recognizable, or length-preserving relations, as well as (infinitely) many other classes.
We study the problem of containment for synchronized classes of relations: given C,D subseteq {1,2}^*, is Rel(C) subseteq Rel(D)? We show a characterization in terms of C and D which gives a decidability procedure to test for class inclusion. This also yields a procedure to re-synchronize languages from {1,2}xA preserving the denoted relation whenever the inclusion holds.