ISSN 1880-2Sl8

数理解析研究所講究録 1846

クローン理論と離散数学

計算機科学をめ$\langle^{\backslash }\backslash$

る代数と論理

京都大学数理解析研究所
2013 年 8 月

数理解析研究所講究録は，京都大学数理解析研究所の共同利用研究集会および共同研究の記録として 1964 年に刊行が開始されました．現在の共同利用共同研究拠点(2010 年発足) の前身である，全国共同利用研究所として当研究所が発足した翌年のことでしたが以来半世紀，毎年数十巻を刊行し，2012 年には第 1800 巻が刊行されるに至りました．第 1 巻から第 1840 巻までに収録された論文数は 26,808 編，総頁数は 317.199 頁という膨大なものであり，最先端の数学数理科学分野の研究状況を伝えるのみならず，我が国の数学数理科学の発展の歴史を留める文献として，他に類例を見ない論文集となっています．

講究録の内容は当研究所のウエブサイトおよび京都大学の学術情報リポジトリにおいても公開され 年間の総アクセス数は 1254383 回 (2012 年度) を数えるなど，多数の方にご利用いただいています．

講究録の使用言語は論文著者の判断に任されていますが結果的に日本語が多用されていることが特徴の一つとなっています．その結果，講究録は，数学数理科学の広い領域における最先端の専門知識に母国語でアクセスできるものとして，近年の英語化の流れの中で，重要な文献となりつつあります．
当研究所の共同利用事業に参加し講究録の論文を執筆していただいた多数の方々に対し，講究録を大きく成長させていただいたことを深く感謝いたしますとともに，これからも，当研究所の共同利用共同研究拠点としての活動にご参加いただき，講究録の発展にご協力いただけますよう心よりお願い申し上げます．

RIMS K\^oky\^uroku 1846

Clone Theory and Discrete Mathematics
June $13\sim 15,2005$

Algebra andScience
LogicRelatedtoComputerctober2$2\sim 23,2009$edited by Hajime Machida

August, 2013
Research Institute for Mathematical Sciences
Kyoto University, Kyoto, Japan

Preface
This volume consists of combined collections of articles presented at the following

RIMS Research Meetings.
1. “Clone Theory and Discrete Mathematics“ June 13–June 15, 2005

2. “Algebra and Logic Related to Computer Science” October 22–October 23, 2009
Some of the articles contain the same contents as those of the lectures given at themeetings while others contain the contents which were evolved and extended from thelectures presented at the meetings.
Due to various reasons the publication of this volume was largely delayed. As theeditor of the volume I express my heartfelt apology for this big delay of the publication.
In particular, my deep apology goes to those authors who submitted their articles very
early and promptly.
Lastly, with regret and sorrow I report that Prof. Kiyoshi Iseki, one of the authors
in the volume, passed away in 2011. Prof. K. Iseki was a truly creative and eminent
mathematician who led the area of algebra and logic for many decades.

February 22, 2013
Hajime Machida(Tokyo, Japan)

クローン理論と離散数学

Clone Theory and Discrete Mathematics

2005 年 6 月 13 日

月 15 日$\sim 6$

計算機科学をめぐる代数と論理
Algebra and Logic Related to Computer Science2009 年 10 月 22 日 〜10 月 23 日

RIMS 研究集会報告集
研究代表者

町田元 (Hajime Machida)

目次

1. Basic algebras$——————————————1$

Palack\’y U. Olomouc

Ivan Chajda

Jan K\"uhr’/

2. 一様遅れ演算の完全性$—————————————————-14$

明治大理工 (Meiji $U$ )疋田輝雄 (Teruo Hikita)

3. Homomorphism on TriPle-semilattice $————————————————–19$
甲南大理工 (Konan $U$ .)堀内

4. Degree of Nondeterminism for Pushdown Automata

5.

清光 (Kiyomitsu Horiuchi)$————————————-27$

一橋大商 (Hitotsubashi $U$ .)茨木辰也 (Tatsuya Ibaraki)

一橋大社会 (Hitotsubashi $U$ .)窪澤駿平 (Shumpei Kubosawa)

To BCI from Subtractive Algebra$——$$—-46$
井関清志 (Kiyoshi Iseki)

6. Logic characterized by Boolean algebras with conjugate
東京電機大情報環境 (Tokyo Denki

$U$.)

近藤

7. Report on Centralizing Monoids on a Three-Element Set
国際基督教大アーツサイエンス (ICU)
U. Montr\’eal$- 1 -$

町田通朗 (Michiro Kondo)$———————–$

元 (Hajime Machida)

Ivo G. Rosenberg

53

8. Graphical Compositions of Semirigid Equivalence Relations
筑波技術大保健科学 (Tsukuba U. Tech.)宮川

U. Claude-Bemard
U. Montr\’eal

Maurice Pouzet
Ivo G. Rosenberg

筑波技術大保健科学 (Tsukuba U. Tech.)巽

9. Hyperalgebras and hyperclones-different approaches

正弘 (Masahiro Miyakawa)

久行 (Hisayuki Tatsumi)$———————————–80$

Jovanka Pantovi\v{c}Gradimir Vojvodi\v{c}U. Novi Sad’/10.

$—————————66$$T_{2}--------------------------87$
Technische U. Wien

Michael Pinsker

1 1. A Consideration on Functions Preserving Set Inclusion Relation $————————94$
富山県立大工 (Toyama Pref. U.)

高木昇 (Noboru Takagi)

12. Upper and Lower Bounds on the Number of Disjunctive Forms $———————–113$
筑波技術大保健科学 (Tsukuba U. Tech.)巽久行 (Hisayuki Tatsumi)〃

宮川正弘 (Masahiro Miyakawa)

明治大理工 (Meiji $U$ .)向殿政男 (Masao Mukaidono)$- 11$

講究録$K\hat{o}\infty\hat{u}\mathfrak{v}ku$$RmISK\hat{o}ky\hat{u}mku$

was started in 1964 as the proceedings of symposia colloquia andworkshops supported by RIMS, the Research Institute for Mathematical Sciences, Kyoto
University It was the next year of the establishment of RIMS as one of the nationwide

Cooperative Research Centers, the preceding system of the current Joint Usage/ResearchCenters that started in 2010. For half a century since then, about 50 to 60 volumes have been

issued each year, and the 1, $800th$ volume was issued in 2012. The volumes of K\^oky\^uroku fromthe lst through the 1, $840t4$ containing enormous 26,808 articles and 317,199 pages, not only

deliver the latest research activities in mathematics and mathematical sciences but alsovaluable and incomparable collections of articles that pass down history of progress$\infty oe\dot{u}tute$of mathematics and mathematical science in Japanare available on the websites of RIMS and Kyoto University ResearchInformation Repository They are very frequently aooessed on the internet, with a total of as
many as 1,254,383 accesses in 2012.
Articles in$K\hat{n}\infty\hat{m}ku$

The authors choose the languages to write articles, and many are written in Japanese, whichis regarded as a significant. As a result,is one of the characteristics of$K\hat{o}\mathfrak{g}_{r}\hat{u}roku$$K\hat{\mathfrak{v}}\mathfrak{g}r\hat{u}r\mathfrak{v}ku$

and important literature which allows easy access to the latest speciahzed knowledge in thelarge fields of mathematics and mathematical sciences written in native language for Japanesereaders, while more and more research papers are being written in English in recent years.
We are deeply grateful to many of those who have participated in cooperative research. We heartily ask $f0r$ your $\infty nbnuous$acdvities of RIMS and greatly developed$K^{\wedge}ky\hat{u}roku$participation in oesearch activities at RIMS as a Joint Usage Research Center and your warm
support and cooperation $fOr$ the fruitful development of K6ky\^uroku.