Synchronizing Relations on Words
Synchronizing Relations on Words
复制标题
同步单词关系
DOI：
--
复制
发表时间：
2014
影响因子：
0.5
通讯作者：
L. Libkin
中科院分区：
文献类型：
--
作者：
Diego Figueira;L. Libkin
虽然词语语言理论已经非常成熟，但我们对词语关系的认识却相对滞后。然而，这种关系出现在许多新的应用，如验证参数化系统，查询图结构数据，信息提取，例如。在这些应用中通常使用的行为良好的关系类是通过适应一些等价的定义的规律性的话的关系，导致可识别的，定期的，合理的关系的非等价的概念。本文的目标是提出一个系统的方法来定义类的关系的话，其中这三类只是自然的例子，并证明其优势相比，一些标准的技术研究词的关系。其关键思想是一对单词的同步，这是一个扩展字母表上的单词。使用它，我们通过固定字母表上的正则语言类来定义关系类，仅{1，2}用于二元关系。我们通过同步语言的参数的有限性，称为移位，滞后，和shiftlag的一些标准类的关系的话。我们描述了这些条件下的结构图的循环自动机，从而显示其可判定性。我们表明，这些类存在规范同步语言，和每一类的关系可以有效地重新同步使用这些规范的代表。我们还给出了同步语言的充分条件，定义在他们的Parikh图像的内射性和满射性，保证关闭下的交叉和补充类的关系，他们定义。
While the theory of languages of words is very mature, our understanding of relations on words is still lagging behind. And yet such relations appear in many new applications such as verification of parameterized systems, querying graph-structured data, and information extraction, for instance. Classes of well-behaved relations typically used in such applications are obtained by adapting some of the equivalent definitions of regularity of words for relations, leading to non-equivalent notions of recognizable, regular, and rational relations. The goal of this paper is to propose a systematic way of defining classes of relations on words, of which these three classes are just natural examples, and to demonstrate its advantages compared to some of the standard techniques for studying word relations. The key idea is that of a synchronization of a pair of words, which is a word over an extended alphabet. Using it, we define classes of relations via classes of regular languages over a fixed alphabet, just {1,2} for binary relations. We characterize some of the standard classes of relations on words via finiteness of parameters of synchronization languages, called shift, lag, and shiftlag. We describe these conditions in terms of the structure of cycles of graphs underlying automata, thereby showing their decidability. We show that for these classes there exist canonical synchronization languages, and every class of relations can be effectively re-synchronized using those canonical representatives. We also give sufficient conditions on synchronization languages, defined in terms of injectivity and surjectivity of their Parikh images, that guarantee closure under intersection and complement of the classes of relations they define.
DOI：
10.2168/lmcs-9(3:01)2013
发表时间：
2013-04
期刊：
Log. Methods Comput. Sci.
影响因子：
--
作者：
P. Barceló;Diego Figueira;L. Libkin
通讯作者：
P. Barceló;Diego Figueira;L. Libkin