数理解析研究所講究録 1222

(1)

数理解析研究所講究録 1222

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

京都大学数理解析研究所

2 0 0 1 年 7 ^月

(2)

まえがき

近年、代数系の理論と形式言語・計算機科学との様々な係わり合いが注目されてきている。アルゴリズムや計算機理論の立場から代数系の構造を取り扱う研究が活発化し、計算代数と呼ばれる新しい分野が生み出されている。そして

この分野は数式処理等への応用が期待されている。-x、計算モデルとの関連から形式言語理論の基礎研究がなされてきたが、最近その代数的取り扱いが注

目されている。

そこで、言語理論、計算理論の代数的研究において最も関係の深い代数系の一つである半群やオートマトン理論及びシステムの構成理論等及びその周辺のの研究者を集め、最新の成果を持ち寄り, この方面の研究の一層の発展を目的

として研究集会「代数的半群, 形式言語及び計算理論」を開催した.

この講究録は、

2001

年

2

^月

19

^日から

2

^月

21

^日までの

3

^{日間数理解析研究所}

に於いて行われた上記の研究集会の報告集である. 講演件数

28

^{件のうも,}

27

件を収録した. 講究録では講演の順番に従いまとめた. また,

Calfornia

大学

Davis

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

読した.

今回の研究集会は期間の割に講演数が多く ^, かなり過密なプログラムになったが, 期間中は活発な議論と質疑応答が展開され、有意義な研究集会となった

.

最後に, このような研究集会の機会を与えていただいた数理解析研究所に感謝申し上げます.

2001

午

6

^月

今岡輝男 (島根大学総合理工学部)

(3)

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

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{B}$

研究代表者今岡輝男($\mathrm{T}\pi \mathrm{u}\mathrm{o}$ Imaoka)

1. Some remarks

on

generah.zed inverse ^$*$-semigroupsI1 島根大・総合理工今岡輝男(TemoImaoka)

2. ONORDERED MONOID

RINGS——————————————————–5

岡山大・理平野康之(Yasuyuki Hirano)

3. ALocalization of aSemigroup Ring, If———————————————-ll 茨城大・理松田隆輝(Ry\^uh. Matsuda)

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$

愛知教育大金光三男(Mitsuo Kanemitsu)

5. Some $\mathfrak{N}\mathrm{e}$ofcommutative artinalgebras—————————————————24

山口大

.

_理菊政 _勲_(Isao _Kh_皿あ_a)

” 吉村浩(Hiroshi Yoshimura)

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

7. Topics

on

fmite and countable infmite BCK————————————————-AO 神戸大・名誉教授井関清志(Kiyoshi Iseki)

8. ^$CPN$ Languages andCodes——————————————————————-A6

京都産業大・理伊藤正美(Masmi Ito)

静岡理工科大国持良行(Yoshiyuh. Kunimochi)

9. $\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}$ in equallengffiforfmite semigroups——————————————-50

Debreoen Univ. ^P\’al D\"om\"osi

京都産業大・理伊藤正美(Masami Ito)

1 0. Characterization of fmite Automatabyffie Images andthe Kemels of their Transition

$\mathrm{F}\mathrm{u}\mathrm{n}\mathrm{c}\mathrm{t}\mathrm{i}_{\mathrm{o}\mathrm{n}\mathrm{s}-}---53$

下関水産大・名誉教授斎藤立彦(Tatsuhiko Saito)

1 1. Weiersffass semigroups ofapair of points whose $\mathrm{f}_{1}\mathrm{r}\mathrm{s}\mathrm{t}$ non-gaps

are

ffiee—————–5\S 神奈川工科大米田二良($\mathrm{J}\mathrm{i}_{\mathrm{I}}\mathrm{y}\mathrm{o}$ Komeda)

1 2. Subgroup ^Members^石$\mathrm{p}$ Problem and Its Applications to Information Security—————64 通信総合研究所山村明弘(Akihiro Ymmura)

- 1 ^-

(4)

13. Van Kampen Diagrams and $\mathrm{E}$-unitag

Coextensions———————————————74

通信総合研究所山村明弘(Akihiro Ymmura)

14. Finiteregular semigroupswhich

are

amalgamation bases for finite SemigIOuPS————-\S 3 島根大・総合理工庄司邦孝(Kunitaka Shoji)

15. ^FinitelyGenerated Idempotent-free Semilattice-Indecomposable Semigroups

with Relations

I————————————————————————————86

Univ. of$\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}$ 田村孝行($\mathrm{T}\mathrm{a}\mathrm{k}\mathfrak{B}’\mathrm{u}\mathrm{k}\mathrm{i}$ Tamura)

16. On Some

Trices—————————————————————————————90

甲南大・理堀内清光(Kiyomitsu Horiuchi)

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

京都産業大・理勝良昌司(Masashi Katsura)

18. ParaUel Computation and Synchronized Term Rewriting Systems

-ExtmdedAbsrac’ ————————————————-105

島根大・総合理工藤田 ^憲悦(Ken-Etsu Fujita) 筑波大・電子・情報工学系 Aart Middeldorp

19. The

measure

of

an

^omega$\mathrm{r}\mathrm{e}\mathrm{g}\mathrm{u}\mathrm{l}\pi$languageis

rariona1———————————114

京大・情報学竹内泉$(\mathrm{h}_{1}\mathrm{m}\mathrm{i} \mathrm{T}*\mathrm{e}\mathrm{u}\dot{0})$

20. An AutomatonforDecidingWheffiera Given Set ofWords is aCode—————123

天理大・教養辻佳代子(Kayoko Tsuji)

$\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}$

21.

pgwv

$\mathrm{G}\mathrm{r}\Phi^{\mathrm{h}}$Models for$\mathrm{M}\mathrm{o}1\mathrm{o}\mathrm{e}\mathrm{u}1\pi$Computmg in silu—

国際電気通信基礎技術研究所 Jim-Qin Liu

Il 下原勝憲(Ka自unori S石mohとa)

22. Abracket representation of the monoid oflinks————————————–138 東邦大・理片海直樹(Naoki Katmuni)

Il 稲田勇(Ismu石ata)

11 小林ゆう治$\sigma \mathrm{u}\mathrm{j}\mathrm{i}$ Kobayashi)

23. ALGORITHMS VERIFYING LOCAL THRESHOLD ^ANDPIECEWISE

TESTABILITY OF $\mathrm{s}\mathrm{B}\mathrm{M}\mathrm{I}\mathrm{G}\mathrm{R}\mathrm{O}\mathfrak{M}$ AND SOLVINGALMEIDAPROBLEM————-145 Bm-IlanUniv. A. N. Trahbnan

24. Notrade theorem in

an

SAlogic 152

慶應大・経済学平瀬和基(Kazuh. Hirase)

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

茨城高専 ^松久 ^隆(Takashi Matsuhisa)

Il 笹沼寿人(Hisato Sasmuma)

26. CONSENSUS ON^$P$-BELIEFCOMMUNICATI ¹⁷⁰ 一橋大・経済学 ^石川 ^竜一郎(Ryuichiro Ishikawa)

(5)

7. ⁽ $\mathrm{n}$ Linear Arrangement Plroblems

on

Multidimensional Torus Graphs—————178 岡山大・エ神保秀司(ShujiJimbo)

”

橋口攻三郎$\mathrm{C}$osaburoHffiiguc石)

武藤仁之\Phi 而s石 $\mathrm{M}$曲)

-3 ^-

数理解析研究所講究録 1222