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

如今，信息被存储在各种人工或物理元素（磁盘、DNA分子等）中，这些元素的特性对用来表示所存储信息的单词的结构施加了一定的限制。我们也可以说，编码信息的可能词（即语言）集合必须满足某些属性。从数据通信的早期开始，以及最近在DNA计算领域，就有研究这些属性/约束的需要。此类属性的示例包括错误检测能力、前缀代码属性、键自由属性和gc-ratio属性。前两个性质在传统的密码理论中是众所周知的，后两个性质在DNA计算相关的密码中是众所周知的。除了满足所需的属性之外，感兴趣的语言通常是常规语言。我们研究中的一些典型问题是：确定给定的正则语言是否满足期望属性，确定给定的正则语言是否在期望属性方面是最大的，研究满足期望属性的语言的结构，研究解决上述类型问题所涉及的复杂性。传统上，上述问题中的每一个都考虑到一个特定的固定属性，并且设计用于解决这些问题的方法是特定于该属性的。然而，最近出现了一些以统一方式处理许多属性的正式方法。本研究的主要目标是：

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: