Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Western Ontario

$20,000.00

Codes, Automata, Formal Languages

EF 2017-18

Résumé
Fundamental problems of computer science centering around codes, information encoding and decoding, and information processing even in the presence of errors are considered. In this general context, an information transmission system can be as simple as a wire and also as complicated as an abstract computing machine, even a machine which relies on uncomputable oracles. I investigate the influence of codes, encodings and decodings on the degree of computability in this very general context. For codes themselves, the main issues I plan to pursue are the error-handling capabilities of certain codes for unusual, but technically relevant error models and the relativization of codes to only the likely output messages. For automata, I study the feasability and power of computing models, including computing devices based on chemical processes. One key issue beyond modelling is the influence of input encoding and output decoding on the power of such unconventional models of computation and, far more generally, their influence on the computational power of arbitrary information transmission systems. In rewriting systems, like grammars or Lindenmayer systems, for formal languages, the information processing capabalities are hidden in the re-writing rules. They become apparent in the informational dependency between parts of the words which can be derived by the rules. My concrete long-term and short-term goals include: (1) model certain kinds of common, but not usually considered, types of errors using transducers; (2) determine the error-handling capabilities of various types of codes with respect to these error types; (3) examine the capabilities of codes under relativization to probable output message spaces; (4) develop a general framework for the complexity of computations which takes into account the encoding and decoding of information and which does not depend on any specific model of computation; (5) investigate the connection between information processing in rewriting systems and the generative capability of such systems; (6) determine the power of modularized grammars, like millstream systems, to model natural languages.
Programme
Discovery Grants Program - Individual
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2017-06926
Name nom
Jurgensen, Helmut
Department département
Computer Science - Computer Science
Organization id
36
Institution établissement
University of Western Ontario
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2017
Competition year année de concours
2017
Award amount
20000
Program id
RGPIN
Program name 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
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
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
2714
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Mathematics of computing
Research subject fr
Mathématiques de l'informatique
Partie
1
Nb partie
5
Application title
Codes, Automata, Formal Languages
Keyword
NSERC
Application summary
Fundamental problems of computer science centering around codes, information encoding and decoding, and information processing even in the presence of errors are considered. In this general context, an information transmission system can be as simple as a wire and also as complicated as an abstract computing machine, even a machine which relies on uncomputable oracles. I investigate the influence of codes, encodings and decodings on the degree of computability in this very general context. For codes themselves, the main issues I plan to pursue are the error-handling capabilities of certain codes for unusual, but technically relevant error models and the relativization of codes to only the likely output messages. For automata, I study the feasability and power of computing models, including computing devices based on chemical processes. One key issue beyond modelling is the influence of input encoding and output decoding on the power of such unconventional models of computation and, far more generally, their influence on the computational power of arbitrary information transmission systems. In rewriting systems, like grammars or Lindenmayer systems, for formal languages, the information processing capabalities are hidden in the re-writing rules. They become apparent in the informational dependency between parts of the words which can be derived by the rules. My concrete long-term and short-term goals include: (1) model certain kinds of common, but not usually considered, types of errors using transducers; (2) determine the error-handling capabilities of various types of codes with respect to these error types; (3) examine the capabilities of codes under relativization to probable output message spaces; (4) develop a general framework for the complexity of computations which takes into account the encoding and decoding of information and which does not depend on any specific model of computation; (5) investigate the connection between information processing in rewriting systems and the generative capability of such systems; (6) determine the power of modularized grammars, like millstream systems, to model natural languages.