Codes, Automata, Formal Languages

代码、自动机、形式语言

• 批准号: RGPIN-2017-06926
• 负责人: Jurgensen, Helmut
• 金额: $ 1.46万
• 依托单位: University of Western Ontario
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=654940
• 关键词: Codes; Automata; Formal; Languages

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.*****

计算机科学的基本问题围绕代码，信息编码和解码，以及信息处理，即使在存在错误的情况下被认为是。在这个一般的上下文中，信息传输系统可以像电线一样简单，也可以像抽象的计算机器一样复杂，甚至是依赖于不可计算的预言机的机器。我在这个非常一般的背景下研究代码、编码和解码对可计算性程度的影响。对于代码本身，我计划追求的主要问题是某些代码对于不寻常但技术上相关的错误模型的错误处理能力，以及代码仅与可能的输出消息的相对化。对于自动机，我研究计算模型的可行性和能力，包括基于化学过程的计算设备。建模之外的一个关键问题是输入编码和输出解码对这种非传统计算模型的影响，以及更普遍的是，它们对任意信息传输系统的计算能力的影响。在形式语言的重写系统中，如文法系统或Lindenmayer系统，信息处理能力隐藏在重写规则中。它们在可以由规则导出的单词的部分之间的信息依赖性中变得明显。我具体的长期和短期目标包括：*（1）使用转换器对某些常见但通常不考虑的错误类型进行建模;*（2）确定各种类型代码对这些错误类型的错误处理能力;*（3）检查相对于可能的输出消息空间的代码能力;* （4）为计算的复杂性制定一个通用框架，该框架考虑到信息的编码和解码，并且不依赖于任何特定的计算模型;* （5）研究重写系统中的信息处理与此类系统的生成能力之间的联系;*（6）确定模块化语法（如millstream系统）对自然语言建模的能力。