数理解析研究所講究録 1222

代数的半群, 形式言語及び計算理論

京都大学数理解析研究所

2 0 0 1年 7月

まえがき

近年、 代数系の理論と形式言語・計算機科学との様々な係わり合いが注目されてきている。 アルゴリズムや計算機理論の立場から代数系の構造を取り扱う研究が活発化し、 計算代数と呼ばれる新しい分野が生み出されている。 そしてこの分野は数式処理等への応用が期待されている。 -x、計算モデルとの関連から形式言語理論の基礎研究がなされてきたが、 最近その代数的取り扱いが注目されている。
そこで、 言語理論、 計算理論の代数的研究において最も関係の深い代数系の一つである半群やオートマトン理論及びシステムの構成理論等及びその周辺のの研究者を集め、 最新の成果を持ち寄り, この方面の研究の一層の発展を目的として研究集会 「代数的半群, 形式言語及び計算理論」 を開催した.
この講究録は、2001 年 2 月 19 日から 2 月 21 日までの 3 日間数理解析研究所に於いて行われた上記の研究集会の報告集である. 講演件数 28 件のうも, 27件を収録した. 講究録では講演の順番に従いまとめた. また,Calfornia 大学

Davis 校の田村孝行先生は論文による参加で, 当日先生の原稿を庄司邦孝氏が代読した.

今回の研究集会は期間の割に講演数が多く , かなり過密なプログラムになったが, 期間中は活発な議論と質疑応答が展開され、有意義な研究集会となった.
最後に, このような研究集会の機会を与えていただいた数理解析研究所に感謝申し上げます.

2001 午 6 月
今岡輝男(島根大学総合理工学部)

代数的半群, 形式言語及ひ計算理論

Algebraic Smigroups, Fomal Languages and$\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{u}\mathrm{t}\mathrm{a}\dot{\mathrm{u}}\mathrm{o}\mathrm{n}$研究集会報告集

2001 年 2 月 19 日 \sim 2 月 21
研究代表者

輝男 (

今岡

$\mathrm{T}\pi \mathrm{u}\mathrm{o}$$\mathrm{B}$Imaoka)

目次

1. Some remarks on generah.zed inverse$*$-semigroupsI1

島根大・総合理工

今岡

輝男 (Temo Imaoka)

2. ON ORDERED MONOID RINGS——————————————————–5
岡山大・理平野康之 (Yasuyuki Hirano)

3. ALocalization of aSemigroup Ring, If———————————————-ll
茨城大・理松田

4. The ideal transforms of$\mathrm{s}\mathrm{e}\mathrm{m}\mathrm{i}\mathrm{g}_{1}\mathrm{o}\mathrm{u}\mathrm{p}\mathrm{s}------------------------------------------------------- 1\S$

愛知教育大

5. Some$\mathfrak{N}\mathrm{e}$隆輝 (Ry\^uh. Matsuda)

金光

三男 (Mitsuo Kanemitsu)

of commutative artin algebras—————————————————24

山口大. 理菊政 勲 (Isao Kh 皿あ a)”

吉村浩 (Hiroshi Yoshimura)

6. On sffuctures of weak interlaced bilaBices—————————————————-34
島根大・総合理工近藤通朗 (Michiro Kondo)

7. Topics on fmite and countable infmite BCK————————————————-AO
神戸大・名誉教授

8.

9.

$CPN$

井関清志 (Kiyoshi Iseki)

Languages and Codes——————————————————————-A6
京都産業大・理伊藤 正美 (Masmi Ito)
静岡理工科大国持 良行 (Yoshiyuh. Kunimochi)

in equal lengffi for fmite semigroups——————————————-50
P\’al D\"om\"osi
Debreoen Univ.

$\mathrm{I}_{\mathrm{I}}\tau \mathrm{e}\mathrm{d}\mathrm{u}\mathrm{c}\mathrm{i}\mathrm{b}\mathrm{i}1\mathrm{i}\mathrm{t}\mathrm{y}$京都産業大・理伊藤正美 (Masami Ito)

1 0. Characterization of fmite Automata by ffie Images and the Kemels of their Transition$\mathrm{F}\mathrm{u}\mathrm{n}\mathrm{c}\mathrm{t}\mathrm{i}_{\mathrm{o}\mathrm{n}\mathrm{s}-}-------------------------------------------------------------------------------------------------53$

下関水産大・名誉教授

1 1.

斎藤

Weiersffass semigroups of a pair of points whose
神奈川工科大$\mathrm{f}_{1}\mathrm{r}\mathrm{s}\mathrm{t}$米田立彦 (Tatsuhiko Saito)

non-gaps are ffiee—————–5\S二良 ($\mathrm{J}\mathrm{i}_{\mathrm{I}}\mathrm{y}\mathrm{o}$Komeda)

1 2. Subgroup Members 石 Problem and Its Applications to Information Security—————64$\mathrm{p}$通信総合研究所

山村

-

1

-

明弘 (Akihiro Ymmura)13. Van Kampen Diagrams and -unitag Coextensions———————————————74$\mathrm{E}$山村

通信総合研究所

明弘 (Akihiro Ymmura)

14. Finite regular semigroups which are amalgamation bases for finite SemigIOuPS————-\S 3
庄司

島根大・総合理工邦孝 (Kunitaka Shoji)

15. Finitely Generated Idempotent-free Semilattice-Indecomposable Semigroups
with Relations I————————————————————————————86Tamura)
田村 孝行 (Univ. of
16. On Some Trices—————————————————————————————90$\mathrm{T}\mathrm{a}\mathrm{k}\mathfrak{B}’\mathrm{u}\mathrm{k}\mathrm{i}$$\mathrm{C}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{f}\mathrm{o}\mathrm{m}\mathrm{i}*\mathrm{D}\mathrm{a}\mathrm{v}\mathrm{i}\mathrm{s}$甲南大・理堀内

清光 (Kiyomitsu Horiuchi)

Undecidabiliy
17. Linear MaIkov Properties and Undecidabiliy————————————————-98$\mathfrak{l}\mathrm{a}\mathrm{I}\mathrm{k}\mathrm{o}\mathrm{V}$東邦大・理小林ゆう治 (Yuji Kobayashi)

京都産業大・理勝良

昌司 (Masashi Katsura)

18. ParaUel Computation and Synchronized Term Rewriting Systems-Extmded Absrac’ ————————————————-105
憲悦 (Ken-Etsu Fujita)

島根大・総合理工

藤田筑波大・電子・情報工学系

Aart Middeldorp

19. The measure of an omega$\mathrm{r}\mathrm{e}\mathrm{g}\mathrm{u}\mathrm{l}\pi$language is rariona1———————————114
竹内京大・情報学

泉$(\mathrm{h}_{1}\mathrm{m}\mathrm{i} \mathrm{T}*\mathrm{e}\mathrm{u}\dot{0})$20. An Automaton for Deciding Wheffiera Given Set of Words is aCode—————123
辻佳代子 (Kayoko Tsuji)

天理大・教養21.

pgwv

Computmg in silu—
Models for
Jim-Qin Liu
国際電気通信基礎技術研究所
Il
下原 勝憲 (Ka 自 unori S 石 moh と a)$\mathrm{M}\mathrm{o}1\mathrm{o}\mathrm{e}\mathrm{u}1\pi$$\mathrm{p}_{\theta \mathrm{f}\mathrm{f}\mathrm{i}_{\mathrm{W}}\mathrm{G}\mathrm{r}}v\Phi^{\mathrm{h}\mathrm{M}\mathrm{o}\mathrm{d}\mathrm{e}1\mathrm{s}\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{M}\mathrm{o}1\mathrm{o}\mathrm{e}\mathrm{u}1\pi\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{u}\mathrm{t}\dot{\mathrm{m}}\mathrm{g}insilu------------------------- 128}$$\mathrm{G}\mathrm{r}\Phi^{\mathrm{h}}$22. Abracket representation of the monoid of links————————————–138
東邦大・理片海直樹 (Naoki Katmuni)Il

稲田勇 (Ismu 石 ata)

11

小林ゆう治

$\sigma \mathrm{u}\mathrm{j}\mathrm{i}$Kobayashi)

23. ALGORITHMS VERIFYING LOCAL THRESHOLD AND PIECEWISE
AND SOLVING ALMEIDA PROBLEM————-145
TESTABILITY OF
A. N. Trahbnan
Bm-Ilan Univ.
152
24. No trade theorem in an SA logic$\mathrm{s}\mathrm{B}\mathrm{M}\mathrm{I}\mathrm{G}\mathrm{R}\mathrm{O}\mathfrak{M}$平瀬慶應大・経済学

和基 (Kazuh. Hirase)

25. AWARENESS, BELIEF AND COMCATION REACHING CONSENSUS——–160
東工大・社会理工学福田恵美子 (Emiko Fukuda)

茨城高専

松久隆 (Takashi Matsuhisa)

笹沼寿人 (Hisato Sasmuma)

Il

170

26. CONSENSUS ON -BELIEF COMMUNICATI$P$

一橋大・経済学石川竜一郎 (Ryuichiro Ishikawa)

茨城高専

松久隆 (Takas 石 M 出抽 isa)

茨城大・理赤川-2-洋介 ($\mathrm{Y}\mathrm{o}\mathrm{h}$-suke Akagawa)7.

($\mathrm{n}$Linear Arrangement Plroblems on Multidimensional Torus Graphs—————178
岡山大・エ神保秀司 (Shuji Jimbo)

osaburo Hffiiguc 石)武藤 仁之\Phi 而 s 石曲)

”

橋口”

攻三郎

$\mathrm{C}$$\mathrm{M}$-3-