Theory and applications of automata and codes

拟议的研究计划解决有关代码属性和自动机（包括传感器）的基本问题，以及它们在数据通信，错误建模，拼写校正和DNA计算等领域的应用。代码属性包括同步、错误检测和纠正，以及由DNA计算中的可靠性问题激发的属性。误差模型是物理通道的抽象表示，在许多情况下，可以方便地用自动机和传感器来描述。自动机的这种具体应用提出了关于自动机结构的新问题，其中一些属于这些对象理论的核心。不同于纠错码的经典理论，这是主要关注的分组码，这项研究的重点是可变长度的代码，很少有人知道他们的行为在传输/存储噪声信道。我的长期目标是分类和识别有意义的代码属性，并找到方法的建设和质量评估的代码相对于一组给定的约束。我的研究建议包括以下几个部分。给出极大实体码的显式构造。这些代码具有非常强的同步特性。 2.研究自动机和形式语言的某些抽象理论概念，这些概念可以作为工具，试图回答在更多应用领域具有特定意义的问题。设计有效的算法来测试正则语言的代码属性并计算此类语言的最大错误检测能力.将理论工具和算法应用于DNA计算，纠错和代码设计领域。此外，实现算法并公开Web接口。

The proposed research program addresses fundamental questions regarding code properties and automata (including transducers), and their applications in areas like reliable coding for data communication,  error modeling, spelling correction, and DNA computing. Code properties include synchronization, error detection and correction, as well as properties motivated by reliability issues in DNA computing. Error models are abstract representations of physical channels and can, in many cases, conveniently be described by automata and transducers. This specific application of automata raises new questions about the structure of automata, some of which belong to the core of the theory of these objects. Unlike the classical theory of error correcting codes, which is mainly concerned with block codes, this research focuses on variable-length codes for which little is known with respect to their behaviour in the transmission/storage over noisy channels. My long term goal is to classify and identify meaningful code properties, and to find methods for the construction and quality evaluation of codes with respect to a given set of constraints. My proposed research consists of the following parts.1. Provide explicit constructions of maximal solid codes. These are codes with remarkably strong synchronization properties.  2. Study certain abstract theoretical concepts of automata and formal languages that can be used as tools in attempting to answer questions with a specific meaning in more applied areas.3. Design efficient algorithms for testing code properties of regular languages and computing maximal error-detecting capabilities of such languages.4. Apply the theoretical tools and algorithms in the areas of  DNA computing, error correction, and code design. Moreover, implement the algorithms and make public web interfaces.