Representational, Algorithmic and Applied Aspects of Word Relations

词关系的表征、算法和应用方面

• 批准号: RGPIN-2020-05996
• 负责人: Konstantinidis, Stavros
• 金额: $ 1.68万
• 依托单位: Saint Mary's University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=758745
• 关键词: Representational; Algorithmic; Applied; Aspects; Word

Introduction A (word) relation is a set of tuples such that each tuple consists of some fixed number n of words. Thus, we can talk about nD (n-dimensional) word relations. The two most well known kinds of word relations are 1D relations, which are known as (formal) languages and are sets of single words, and 2D relations, which are sets of pairs of words. An example of a 2D word relation is the set of word pairs (u,v) such that the edit distance d(u,v) is at most 2. Theoretical Computer Science provides (1) methods to represent a possibly infinite word relation as a finite object (2) algorithms that operate on these finite objects (3) methods to establish whether algorithmic questions on these objects are hard or even undecidable. Representations of Word Relations Depending on their representation method, we have various types of relations. For example, rational relations are relations representable by regular expressions, or by (finite) automata. Automata for 2D rational relations are called transducers. Regular expressions are convenient for human use; for example 1D regular expressions are ubiquitous in computer programming and are now used even by biologists. However, many algorithms for rational relations operate better on their corresponding automata representations. Some rational word relations are called synchronous; they can be represented by regular expressions of a certain simple format and have certain algorithms that operate faster than those of general rational relations. But there are word relations that are not rational. These are usually represented by automata with accessories like counters and stacks. Motivation, Objectives, Significance Rational relations have applications in various domains, such as reachability in string programs, graph databases, and independence conditions on formal languages. However, according to some authors, "while the theory of languages is very mature, our understanding of nD relations is still lagging behind", and some problems on word relations "seem out of reach in the current state of the theory". Motivated by these considerations, three objectives of the planned work are: (1) Investigate various concepts of synchronous nD relations, in particular for n>2, as well as various rational intersection problems; (2) Investigate algorithmic and decidability questions on word relations and, when possible, implement algorithms that can be applied to questions in biocomputing and abstract language theory; (3) Investigate approximation and randomized algorithms for hard automata problems, such as the NFA universality problem. The long term objective and significance is the establishment of new technical tools on word relations that will enrich our body of knowledge on the topic and will enable researchers to employ these tools in their own research programs. Moreover, the proposed research will provide high quality training of HQP.

一个（词）关系是一组元组，每个元组由一些固定数量的n个词组成。因此，我们可以讨论nD（n维）词的关系。两种最著名的词关系是一维关系，它被称为（形式）语言，是单个词的集合，以及二维关系，它是成对词的集合。2D单词关系的示例是单词对（u，v）的集合，使得编辑距离d（u，v）至多为2。理论计算机科学提供了（1）将可能无限的词关系表示为有限对象的方法（2）对这些有限对象进行操作的算法（3）确定这些对象上的算法问题是否困难甚至不可判定的方法。词语关系的表示取决于它们的表示方法，我们有各种类型的关系。例如，有理关系是可由正则表达式或（有限）自动机表示的关系。二维有理关系的自动机称为转换器。正则表达式便于人类使用;例如，1D正则表达式在计算机编程中无处不在，现在甚至被生物学家使用。然而，许多有理关系的算法在其相应的自动机表示上运行得更好。一些有理词关系被称为同步的;它们可以用某种简单格式的正则表达式表示，并且具有某些比一般有理关系更快的算法。但也有一些词的关系是不合理的。这些通常由带有计数器和堆栈等附件的自动机表示。理性关系在很多领域都有应用，例如字符串程序的可达性，图形数据库，以及形式语言的独立性条件。然而，根据一些作者的说法，“虽然语言理论非常成熟，但我们对nD关系的理解仍然滞后”，并且单词关系的一些问题“在理论的当前状态下似乎遥不可及”。基于这些考虑，计划工作的三个目标是：（1）研究同步nD关系的各种概念，特别是对于n>2，以及各种有理相交问题;（2）研究单词关系的算法和可判定性问题，并在可能的情况下，实现可应用于生物计算和抽象语言理论问题的算法;（3）研究硬自动机问题的近似和随机算法，如NFA普遍性问题。长期目标和意义是建立新的词汇关系技术工具，这将丰富我们对这一主题的知识体系，并使研究人员能够在自己的研究计划中使用这些工具。此外，建议的研究将提供高质量的培训HQP。