オ-トマトン,形式言語およびコ-ドの代数的研究

自动机、形式语言和代码的代数研究

基本信息

批准号：
03640107
负责人：
伊藤正美
金额：
$ 0.77万
依托单位：
Kyoto Sangyo University
依托单位国家：
日本
项目类别：
Grant-in-Aid for General Scientific Research (C)
财政年份：
1991
资助国家：
日本
起止时间：
1991 至无数据
项目状态：
已结题

项目摘要

平成3年度の研究の重点はコ-ドの代数的研究におかれた。この分野は形式言語理論のなかでも通信理論への応用が期待されることもあり,計算機科学の基礎理論として重要な位置を占めている。平成3年度は文脈自由言語および稠密な言語とコ-ドの関連性に関して重点的に研究を行なった。まず,平成3年度中に刊行された論文では,外挿コ-ドおよび内挿コ-ドと形式言語との関連が論じられた。また,稠密な正規言語および文脈自由言語の構造が決定された。さらに,一記号上の分離型言語はすべて強分離型になることが証明された。半群の左稠密被覆の定義とその構造の決定の仕事も平成3年度中に刊行された。平成3年度中になされ平成4年以降に刊行される論文では,形式言語と原始語の集合の関係,準同形の一般化としての擬準同形の定義とその構造および言語との関係,任意のn個の要素がコ-ドになるような言語の研究等がある。準備中の仕事としては,右稠密言語およびその特別の場合としての右に稠密言語の構造の決定とコ-ドとの関係の研究がある。以上の個人的な研究のほかに平成3年度中になされた仕事としては,国際会議「語,言語および組合せ論」の会議録の作成があり,さらに平成5年4月には上記の国際会議での形式言語理論関係の論文選集がヨ-ロッパ情報科学連合の機関誌Theoretical Computer Scienceの特別号としてElsevier社(Amsterdam)より刊行される。

1991年的研究重点是代码的代数研究。该领域作为计算机科学的基础理论占有重要地位，有望应用于形式语言理论中的通信理论。 1991年，我们将研究重点放在上下文无关语言以及密集语言和代码之间的关系上。首先，1991 年发表的一篇论文讨论了外推法和内插法代码与形式语言之间的关系。此外，还确定了密集正则语言和上下文无关语言的结构。进一步证明，所有在一个符号上可分的语言都是强可分的。 1991 年还发表了关于半群左稠密覆盖的定义及其结构确定的著作。 1991 年撰写并于 1992 年之后发表的论文讨论了形式语言与一组原始单词之间的关系、准同态的定义（作为同态的推广）、其结构及其与语言的关系，以及任意同态之间的关系研究由 n 个元素组成代码的语言。准备工作包括研究右密集语言的结构与其特例之间的关系、右密集语言结构和代码的确定。除上述个人研究外，1991年期间进行的工作还包括准备国际会议“单词、语言学和组合学”的会议纪要，以及1993年4月上述国际会议相关论文的选集形式语言理论的研究将由爱思唯尔（阿姆斯特丹）作为欧洲信息科学联盟期刊《理论计算机科学》的特刊出版。