"Independent formal languages: structure, algorithms, complexity, implementation"

“独立的形式语言：结构、算法、复杂性、实现”

• 批准号: 217247-2012
• 负责人: Konstantinidis, Stavros
• 金额: $ 2.03万
• 依托单位: Saint Mary's University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2016
• 资助国家: 加拿大
• 起止时间: 2016-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=593961
• 关键词: Independent; formal; languages; structure; algorithms

Nowadays, information is stored in various artificial or physical elements (disks, DNA molecules, etc.) whose characteristics impose certain constraints on the structure of the words that can be used to represent the stored information. We can also say that the set of possible words (the language, that is) in which information is encoded must satisfy certain properties. The need for investigating such properties/constraints has been present since the early days of data communications as well as more recently in the domain of DNA computing. Examples of such properties are error-detecting capability, the prefix code property, the bond-freeness property, and the gc-ratio property. The former two properties are well-known in traditional theories of codes, and the latter two in DNA computing related codes. In addition to satisfying the desired properties, the languages of interest are normally regular languages. Some typical questions of interest in our research are the following: decide whether a given regular language satisfies a desired property, decide whether a given regular language is maximal with respect to a desired property, investigate the structure of languages satisfying a desired property, investigate the complexity involved in solving the above types of problems. Traditionally, each of the above problems is considered with a certain fixed property in mind, and the approaches designed to address these problems are specific to that property. Recently, however, there have been a few formal approaches for addressing many properties in a uniform way. The major objectives of this research are:

如今，信息存储在各种人工或物理元件（磁盘，DNA分子等）中。其特征对可用于表示所存储信息的字的结构施加了某些约束。我们也可以说，编码信息的可能单词（即语言）的集合必须满足某些性质。调查这样的属性/约束的需要已经存在，因为早期的数据通信，以及最近在DNA计算领域。这些属性的示例是错误检测能力、前缀码属性、无键属性和gc比率属性。前两个性质在传统的代码理论中是众所周知的，后两个性质在DNA计算相关的代码中是众所周知的。除了满足所需的属性外，感兴趣的语言通常是正则语言。在我们的研究中感兴趣的一些典型的问题如下：决定一个给定的正则语言是否满足一个期望的属性，决定一个给定的正则语言是否是最大的关于一个期望的属性，调查满足一个期望的属性的语言的结构，调查在解决上述类型的问题所涉及的复杂性。传统上，上述问题中的每一个都是在考虑某个固定属性的情况下考虑的，并且设计用于解决这些问题的方法特定于该属性。然而，最近有一些正式的方法，以统一的方式解决许多属性。这项研究的主要目标是：