Grant: Discovery Grants Program - Individual
Saint Mary's University
$20,000.00
Theory and applications of automata and codes
FY 2011-12
Summary
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.
Program
Discovery Grants Program - Individual
Recipient
Location
Nova Scotia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
217247-2007
Name nom
Konstantinidis, Stavros
Department département
Mathematics and Computing Science
Organization id
85
Institution établissement
Saint Mary's University
Province en
Nova Scotia
Province fr
Nouvelle-Écosse
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2011
Competition year année de concours
2007
Award amount
20000
Program id
RGPIN
Program nane en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
Research subject code
2712
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Theory of computation
Research subject fr
Théorie de calcul
Partie
5
Nb partie
5
Application title
Theory and applications of automata and codes
Keyword
NSERC
Application summary
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.