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

点击翻译按钮获取中文摘要

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: