Reference number : GC-2017-Q1-03555, amendment number : , agreement type : G, recipient legal name : Jurgensen, Helmut (The University of Western Ontario), recipient country : CA, recipient province : nan, recipient city : Ontario, recipient postal code : nan, program name english : Discovery Grants Program - Individual, program name french : Programme de subventions à la découverte - individuelles, program purpose english : 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., program purpose french : 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., agreement title english : Codes, Automata, Formal Languages, agreement title french : Codes, Automata, Formal Languages, agreement number : RGPIN, agreement value : 100000.0, agreement start date : 2017-05-10, agreement end date : nan, description english : nan, description french : nan, expected results english : nan, expected results french : nan, additional information english : Grant or Award spanning more than one fiscal year. (2017-2018 to 2022-2023), additional information french : Subvention ou bourse octroyée s'appliquant à plus d'un exercice financier. (2017-2018 à 2022-2023), owner organization : nserc-crsng, owner organization title : Natural Sciences and Engineering Research Council of Canada | Conseil de recherches en sciences naturelles et en génie du Canada