Semigroups, Formal Languages and Computation

半群、形式语言和计算

• 批准号: 09440017
• 负责人: IMAOKA Teruo
• 金额: $ 3.78万
• 依托单位: Shimane University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (B)
• 财政年份: 1997
• 资助国家: 日本
• 起止时间: 1997 至 1999
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-09440017/
• 关键词: semigroup; representation; amalgamation; formal language; rewriting system; free monoid; automata; computation; semigroup; representation; amalgamation; formal language; rewriting system; free monoid; automata; computation

The main results of this project are as follows :(1)The class of generalized inverse [*-]semigroups has the strong amalgamation property.(2)The transitive representations of a generalized inverse *-semigroup is characterized by using right ω-cosets.(3)We obtained the necessary and sufficient conditions for that a completely 0-simple semigroup is a special amalgamation base.(4)The decision problem whether or not a finite semigroup has representation extension property is decidable.(5)Several properties and a characterization of the shuffle residual of a language are obtained. For example, conditions for the existence of maximal languages whose shuffle residual equals a given language are obtained.(6) We obtained concrete descriptions of the free algebras in several varieties given by language structures equipped with the operations of reversal, concatenation, shuffle and others.

本课题的主要成果如下：(1)广义逆[*-]半群类具有强并合性。(2)广义逆*-半群的传递表示用右ω-陪集来表征。(3)得到了完全0-简单半群是特殊并合基的充要条件。(4)有限或非有限的决策问题 半群具有可判定的表示扩展性质。(5)得到了语言洗牌残差的几个性质和表征。例如，获得了洗牌残差等于给定语言的最大语言的存在条件。(6)我们获得了由具有反转、串联、洗牌等操作的语言结构给出的几种自由代数的具体描述。

项目成果

M. Ito: "On some special classes of regular languages"Jewels and Forever, edited by J. Karhumaki et al, Springer, New York. 25-34 (1999)

M. Ito：“关于常规语言的某些特殊类别”Jewels and Forever，由 J. Karhumaki 等人编辑，Springer，纽约。

M. Ito (編著): "Words, Languages and Combinatorics III"World Scientific, Singapore (to appear).

M. Ito（编辑）：《Words、Languages and Combinatorics III》《世界科学》，新加坡（待发表）。

I.Inata and T.Imaoka: "Note on transitive representations of generalized inverse ^*-semigroups" 数理解析研究所講究録「言語、代数および計算システム」. (to appear).

I.Inata 和 T.Imaoka：“关于广义逆 ^*-半群的传递表示的注释”数学科学研究所 Kokyuroku“语言、代数和计算系统”（待发表）。

M.Ito, L.Kari & G.Thierrin: "Shuffle and scattered deletion closure of languages" Theoretical Computer Science. (発表予定).

M.Ito、L.Kari 和 G.Thierrin：“语言的随机播放和分散删除闭包”理论计算机科学（待提交）。

Y. Kobayashi: "Homotopy reduction systems for monoid presentations asphericity and low-dimensional homology"J. Pure and Applied Algebra. 130. 159-195 (1998)

Y. Kobayashi：“用于幺半群表示非球面性和低维同调性的同伦约简系统”J。