Theory and applications of automata and codes

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

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.