ＩＳＳＮ 1880 − 2818

数理解析研究所講究録 1604

代数、言語のアルゴリズムと計算理論

京都大学数理解析研究所

2008 年 6 月

RIMS K6kyOroku 1604

Aigorithmic and Computational Theo7yin Aigebra and Languages

1tzne, 2008

Research Institute for Mathematzcal Sczences.Kyoto University, K)2oto, ,7izpan

TIMs is a report of research done at Research lnstitute fbr Mathematical
Sciences, Kyoto Umversity The papers contamed herein are m final form
and will not be submitted for publication elsewhereまえがき

この報告集は,2008 年 2 月 20 日〜22 日に京都大学数理解析研究所で行われた研究集会「代数、言語のアルゴリズムと計算理論」における研究発表に基づくものである。この研究集会では, 代数系, 言語理論, 計算理論にかかわる様々な研究発表と討論が行われた。ここに, 発表された 22 件の講演から 20 件の報告を収録している。代数と計算科学が交錯する分野の研究の進展の一一助となれば幸いである。
Ｔｈｌｓ ｖｏｌｕｍｅ ｃｏｎｔａｌｎｓ 20 ａｒ七 1 ｃｌｅｓ ｗｈｉｃｈ ｗｅｒｅ ｐｒｅｓｅｎ七ｅｄ ｌｎ ｔｈｅ ｓｙｍｐ（〉・・

ｓｉｕｍ ｏｎ Ａｌｇｏｎｔｈｍｉｃ ａｎｄ Ｃｏｍｐｕｔ ａｔｉｏｎａｌ Ｔｈｅｏｒｙ ｍ Ａｌｇｅｂｒａ ａｎｄ Ｌａｎ−ｇｕａｇｅｓ ｈｅｌｄ ａ七ＲＩＭＳ, Ｋｙｏ七〇Ｕｍｖｅｒｓｌ七ｙ丘ｏｍ Ｆｅｂｒｕａｒｙ 20 ｔｏ 22,2008
Ｔｈｅ ｐｕｒｐｏｓｅ ｏｆ七ｈｅ ｓｙｍｐｏｓｌｕｍ ｗａｓ七〇 ｄｌｓｃｕｓｓ ｗｌｄｅｌｙ ｒｅｌａｔｅｄ七〇ａｌｇｅｂｒａｓ,
ｃｏｍｂｍａｔｏｒｉｃｓ, ｆｏｒｍａｌ ｌａｎｇｕａｇｅｓ, ａｕｔｏｍａｔ ａ, ｌｏｇｉｃ ａｎｄ ｃｏｍｐｕｔａｔｉｏｎ

2008 年 6 月置Ｊｕｎｅ,2008）

米田二良（Ｊｉｒｙｏ Ｋｏｍｅｄａ）

神奈川工科大学（Ｋａｎａｇａｗａ Ｉｎｓｔ 1 七ｕ七ｅ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ）

代数、言語のアルゴリズムと計算理論

Ａｌｇｏｒｉｔｈｍｉｃ ａｎｄ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｔｈｅｏｒｙ ｉｎ Ａｌｇｅｂｒａ ａｎｄ Ｌａｎｇｕａｇｅｓ
ＲＩＭＳ研究集会報告集

2008 年 2 月 20 日〜2 月 22 日

研究代表者 米田 二良（Ｊｌｒｙｏ Ｋｏｍｅｄａ）
目 次

1 Ｃｏｍｍｕｔａｔｌｖｅ ｒｅｓｉｄｕａｔｅｄ ｌａｔｔｉｃｅｓで特徴づけられる論理につし】て一一一一一一一一一一一 1

東京電機大・情報環境（Ｔｏｋｙｏ Ｄｅｎｋｌ Ｕ） 近藤 二二（Ｍｌｃｈｌｒｏ Ｋｏｎｄｏ）
2 定理証明ツールによる証明可能安全性 一一一一・一一コー一一一一一……一一……一一一一…一。一一一 9

産業技術総合研究所（ＡＩＳＴ） 田中 三貴（Ｍｌｋｌ Ｔａｎａｋａ）
3 完全二部グラフを用いたＲＡＩＤ 6 でのＤａｔａとＰａｎｔｙの配置 一・一一一一一一一ｄｌ一一一.19
東邦大・理（Ｔｏｈｏ Ｕ） 足立 智子（Ｔｏｍｏｋｏ Ａｄａｃｈ 1）〃 杉浦 智吉（Ｔｏｍｏｙｏｓｈｌ Ｓｕｇｉｕｒａ）
4 Ｍｅｃｈａｎｉｓｍ ｏｆ Ｈｏｍｏｍｏｒｐｈｌｃ Ｅｎｃｒｙｐｔｌｏｎｓ 一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一 31

秋田大・工学資源（Ａｋｌｔａ Ｕ） 山村 明弘（Ａｋｌｈｌｒｏ Ｙａｍａｍｕｒａ）
5 ｄ−ｐｎｍＭｖｅ ｗｏｒｄｓ ａｎｄ Ｄ（1）一ｃｏｎｃａｔｅｎａｔｅｄ ｗｏｒｄｓ 一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一 37

国士舘大・理工（Ｋｏｋｕｓｈｌｋａｎ Ｕ） 片面 格（Ｉｔａｒｕ Ｋａｔａｏｋａ）〃 守谷 哲夫（Ｔｅｔｓｕｏ Ｍｏｎｙａ）
6 Ｂａｒｇａｍｍｇ Ｍｏｄｅｌ ｏｎ ｔｈｅ Ｐｌａｎｅ 一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一 42
Ｋａｒｅｌｉａｎ Ｒｅｓ Ｃｅｎｔｅｒ, Ｒｕｓｓｉａｎ Ａｃａｄ Ｓｃｉ Ｖｌａｄｒｍｒｒ Ｖ Ｍａｚａｌｏｖ

Ｚａｂａｉｋａｌｓｋｙ Ｓｔａｔｅ Ｈｕｍａｎｉｔａｎａｎ Ｐｅｄａｇｏｇｉｃａｌ Ｕ Ｊｕｈａ Ｓ Ｔｏｋａｒｅｖａ

7 Ｃｏｍｍｕｍｃａｔｉｏｎ Ｒｅａｃｈｍｇ Ｃｏｎｓｅｎｓｕｓ ｔｈｒｏｕｇｈ Ｒｏｂｕｓｔ Ｍｅｓｓａｇｅｓ 一一一一一一一一一一一一一一一一…一… 50
茨城工業高専（ｌｂａｒａｋｌ Ｎａｔ Ｃｏｌｌ Ｔｅｃｈ） 松久 隆（Ｔａｋａｓｈｉ Ｍａｔｓｕｈｉｓａ）
8 ＰＬ多様体の本間の曲率の意味付け 一一。一一一一一一一ｉｔ一・・ｎ. 一一一一. 一一一. 一一一一一一一一一一一一一 57

玉川大・工（Ｔａｍａｇａｗａ Ｕ） 佐藤 健治（Ｋｅｎｚｌ Ｓａｔ 6）
9 組合せ子の非循環性と非停止性一ｅ一・一…一一一…一一一・・一…一一一・・一一一一一一。・・一・一一一一一・一一一一一…一一 60

島根大・総合理工（Ｓｈｌｍａｎｅ Ｕ） 岩見 宗弘（Ｍｕｎｅｈｌｒｏ Ｉｗａｍ 1）
1 Ｏ Ｒｅｇｕｌａｒｉｔｙ Ｐｒｅｓｅｒｖａｔｉｏｎ ｂｙ Ｓｔｒｍｇ−Ｒｅｗｎｔｍｇ Ｓｙｓｔｅｍｓ Ｂａｓｅｄ ｏｎ Ｐｅｎｏｄｓ 一一一一一一一一一一一一一一一一一一一一 69
京産大・理（Ｋｙｏｔｏ Ｓａｎｇｙｏ Ｕ） Ｐｅｔｅｒ Ｌｅｕｐｏｌｄ
1 1 Ｐｌａｃｅ Ｄｅｐｅｎｄｅｎｃｙ ｏｆ ａ Ｐｅｔｎ Ｎｅｔ Ｇｅｎｅｒａｔｍｇ ａ Ｍａｘｉｍａｌ Ｐｒｅｆｉｘ Ｃｏｄｅ 一一一一一一一一一一一一一一一一一一一一一一一 80
静岡理工科大（Ｓｈｌｚｕｏｋａ Ｉｎｓｔ Ｓｃｌ Ｔｅｃｈ） 心持 良行（Ｙｏｓｈｌｙｕｋ 1 Ｋｕｎｉｍｏｃｈ 1）
12 Ｗｅｌｅｒｓｔｒａｓｓ半群とＧｏｐｐａ符号 …一一一一一一一一一・一。一一一一一一一…一一一・一一一一一一一一一一 90
神奈川大・工（Ｋａｎａｇａｗａ Ｕ） 本間 正明（Ｍａｓａａｋｌ Ｈｏｍｍａ）
13 スペクトル分布によるセルラーオートマトンの単射性・全射性の判定ｅ…一一・・一一 101
東洋大・工（Ｔｏｙｏ Ｕ） 佐藤 忠一（Ｔａｄａｋａｚｕ Ｓａｔｏ）

一噸 1 ｖ一一一一.

14 セルオ・・…一トマトンの局所構造一一一一一一一一一一一一一一一一, 一一一一一＿一・一一一. 一一＿＿. 一. 一一 104

元・京大（Ｋｙｏｔｏ Ｕ） 西尾 英之助（Ｈｌｄｅｎｏｓｕｋｅ Ｎｌｓｈｌｏ）
ＵＫａｒｌｓｒｕｈｅ Ｔｈｏｍａｓ Ｗｏｒｓｃｈ

15 合成代数とピタゴラスの定理の拡張 一一一一一一一一一一一一・一一一・一・一一一一一・・一・・一・一一一一一一ｌｌＯ

会津大（ＵＡＩｚｕ） 神谷 徳昭（Ｎｏｎａｋｌ Ｋａｍｌｙａ）〃 森 和好（Ｋａｚｕｙｏｓｈｌ Ｍｏｎ）
新潟県立相川高校（Ａｌｋａｗａ Ｈｌｇｈ Ｓｃｈｏｏｌ） 青木 洋人（Ｈｌｒｏｔｏ Ａｏｋ 1）
1 6 Ｃｏｍｐｌｅｔｉｏｎｓ ｏｆ ｇｅｎｅｒａｈｚｅｄ ｍｖｅｒｓｅ ＊一ｓｅｍｉｇｒｏｕｐｓ 一一一一一・・一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一・ 114

島根大・総合理工（Ｓｈｌｍａｎｅ Ｕ） 太田 開己（Ｈａｒｕｋｉ Ｏｈｔａ）〃 今岡 輝男（Ｔｅｒｕｏ Ｉｍａｏｋａ）
1 7 Ａ ｒｅｍａｒｋ ｏｎ ｃｏｎｓｔｒｕｃｔｌｏｎ ｏｆ ｃｌｒｃｕｌａｒ ｃｏｄｅｓ 一一一 ｅ一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一 120

東海大短大部（Ｔｏｋａｌ Ｕ Ｊｕｎｌｏｒ Ｃｏ 11） 中畑 登（Ｎｏｂｏｒｕ Ｎａｋａｈａｔａ）
静岡理工科大（Ｓｈｌｚｕｏｋａ Ｉｎｓｔ Ｓｃｌ Ｔｅｃｈ） 國持 良行（Ｙｏｓｈｌｙｕｋｌ Ｋｕｎｌｍｏｃｈ 1）
田中 源次郎（ＧｅｎＪｉｒｏ Ｔａｎａｋａ）
1 8 Ａ ｎｏｔｅ ｏｎ ＳｃｈｍｌｔｔｅＶｏｇｅｌ ｌｅｍｍａ 一一一一ｅ一 ｅ 一一一一一一一一一一一一ｅ一 ｅ一一一一一一一一一一一一一一一一 一一一一一一一一一 一 125

名大・多元数理科学（Ｎａｇｏｙａ Ｕ） 木村 杏子（ＫｙｏＵｋｏ Ｋｉｍｕｒａ）
佐賀大・文化教育（Ｓａｇａ Ｕ） 寺井 直樹（Ｎａｏｋｌ Ｔｅｒａ 1）
名大・多元数理科学（Ｎａｇｏｙａ Ｕ） 吉田 健一（Ｋｅｎ・ｌｃｈｌ Ｙｏｓｈｌｄａ）
1 9 Ｔｈｅ ｄｉｍｅｎｓｉｏｎ ｏｆ ａ ｔｏｎｃ ｖａｒｉｅｔｙ ｏｂｔａｍｅｄ ｆｒｏｍ ａ ｎｕｍｅｎｃａｌ ｓｅｍｉｇｒｏｕｐ 一一一一一一一一一一一一一一一一一一一 131
神奈川工大・基礎・教養教育センター（Ｋａｎａｇａｗａ Ｉｎｓｔ Ｔｅｃｈ）

米田 二良（Ｊｌｒｙｏ Ｋｏｍｅｄａ）
2 Ｏ Ｇｒ 6 ｂｎｅｒ ｂａｓｅｓ ｏｎ ｐｒｏＪ ｅｃｔｉｖｅ ｂｉｍｏｄｕｌｅｓ ａｎｄ ｔｈｅ Ｈｏｃｈｓｃｈｉｌｄ ｃｏｈｏｍｏｌｏｇｙ
Ｐａｒｔ皿 Ｓｙｚｙｇｌｅｓ 一一一一一一一。一一一一一一一一一一一一一一一一・・一・・…一・■一一一・一一一一。一一一一一一一一一一一一一。一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一 142

東邦大・理（Ｔｏｈｏ Ｕ） 小林 ゆう治（ＹｕＪｉ Ｋｏｂａｙａｓｈｉ）

一一 ｉｌ 一