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

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

• 批准号: 217247-2012
• 负责人: Konstantinidis, Stavros
• 金额: $ 2.03万
• 依托单位: Saint Mary's University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=570126
• 关键词: 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: 1. Develop and investigate formal methods for expressing language properties that would allow some of the algorithmic problems to be addressed in a uniform way, for all expressible properties. 2. Understand the complexity involved in answering some of the desired algorithmic questions. 3. Implement a "Formal Language Server" where a user/client can specify a desired property, and the server will decide whether a language satisfies the property, or construct languages satisfying the property.

如今，信息存储在各种人工或物理元素(磁盘、DNA分子等)中。其特征对可用于表示所存储的信息的词的结构施加了某些约束。我们还可以说，对信息进行编码的可能单词集(即语言)必须满足某些属性。从数据通信的早期开始，以及最近在DNA计算领域，就存在对这种性质/约束进行研究的需要。这些属性的例子有错误检测能力、前缀代码属性、无键性属性和GC比率属性。前两个性质在传统的码论中是众所周知的，后两个性质在DNA计算相关的码中是众所周知的。除了满足期望的性质之外，感兴趣的语言通常是正规语言。我们研究的一些典型问题包括：判定给定的正则语言是否满足期望性质，判定给定的正则语言是否关于期望性质是极大的，研究满足期望性质的语言的结构，研究解决上述类型问题所涉及的复杂性。传统上，上述每个问题都是在考虑某个固定属性的情况下考虑的，而为解决这些问题而设计的方法是特定于该属性的。然而，最近出现了一些以统一方式处理许多属性的正式方法。这项研究的主要目标是： 1.开发和研究用于表示语言属性的形式化方法，这些方法将允许以统一的方式为所有可表达的属性解决一些算法问题。 2.了解回答一些所需的算法问题所涉及的复杂性。 3.实现一个“形式语言服务器”，用户/客户端可以指定所需的属性，服务器将决定一种语言是否满足该属性，或者构造满足该属性的语言。