Subventions et des contributions :

Subvention ou bourse octroyée s'appliquant à plus d'un exercice financier. (2017-2018 à 2022-2023)

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.