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.

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