論文 / 著書情報
Article / Book Information
題目(和文)
Title(English)

Computational Complexity of Several Extensions of Kleene Algebra

著者(和文)

中村誠希

Author(English)

Yoshiki Nakamura

出典(和文)

学位:博士(理学),学位授与機関:東京工業大学,
報告番号:甲第11065号,授与年月日:2019年3月26日,
学位の種別:課程博士,
審査員:鹿島 亮,南出 靖彦,伊東 利哉,田中 圭介,森 立平

Citation(English)

Degree:Doctor (Science),
Conferring organization: Tokyo Institute of Technology,
Report number:甲第11065号,
Conferred date:2019/3/26,
Degree Type:Course doctor,
Examiner:,,,,

学位種別(和文)

博士論文

Category(English)

Doctoral Thesis

種別(和文)

要約

Type(English)

OutlinePowered by T2R2 (Tokyo Institute Research Repository)

（博士課程）Doctoral Program論 文 要 旨ＴＨＥＳＩＳ ＳＵＭＭＡＲＹ

系・コース：
Department of, Graduate major in

数理・計算科学
数理・計算科学

学生氏名：
Student’s Name系コース

中村 誠希

申請学位（専攻分野）： 博士
Academic Degree Requested

指導教員（主）：Academic Supervisor(main)

Doctor of（理学）鹿島 亮 准教授

指導教員（副）：Academic Supervisor(sub)要旨（和文 2000 字程度）
Thesis Summary （approx.2000 Japanese Characters ）Kleene 代数とは、正規表現を一般化した代数系であり３つの演算：和、結合、繰り返し(Kleene star) と２つの定数：和の単位元、結合の単位元 からなる。”繰り返し”は計算の表現やモデルの性質を表現する上で基本的な演算であり、とくに計算機科学において様々な文脈で現れる。Kleene 代数における主要な例としては言語の構造のほかに二項関係の構造があり、関係代数や様相論理（例えば、動的論理、記述論理、時相論理）との関連がある。また、その等式理論（即ち、正規表現の等価性判定問題）は PSPACE 完全で決定可能である。本論
文「Computational Complexity of Several Extensions of Kleene Algebra」では、Kleene 代数を拡張した体系の等式理論の決定可能性および計算複雑性について議論する。本論文は、５つの章からなる英語論文であり、序章「Introduction」と終章「Concluding Remarks」のほか以下の 3 つの章からなる。
第２章「Preliminaries」:本章では、はじめに述語論理に関する基本的な定義を述べたあと、Kleene 代数に関する既存の結果のうち基本的な性質や重要な性質を二項関係の構造と言語の構造に分けて紹介する。二項関係の構造においては、とくに関係代数との関係性や関係代数における基本的な性質を紹介する。言語の構造においては、オートマトンとの関係性や正規表現の微分 (derivatives) について説明する。章の終わりでは言語の構造と二項関係の構造でそれぞれ定義される等式理論が一致することとその等式理論の代数的な公理化について紹介する。
第３章「Derivatives for Kleene Allegories」: 本章では、二項関係の構造における Kleene 代数について２つの演算（積、逆関係）を加えた代数（Kleene 寓圏と呼ばれる）の等式理論が EXPSPACE 完全で決定可能であることを示す。本問題は、LICS’ 15 において open とされていた問題である。Kleene 寓圏における等式理論は、グラフ言語間のグラフ準同型性判定問題として特徴づけられる。決定可能性を示す道具として、Antimirov による（正規表現に対する）文字列上の微分をグラフにおいても実行できるように拡張したグラフ上の微分を新たに導入する。この微分を用いることで、Kleene 寓圏の等式をある２つの有限オートマトンの等価性判定問題に変換できる。これにより Kleene 寓圏の等式理論が決定可能でありかつ EXPSPACE に属することが示される。
EXPSPACE 困難であることは、積演算付き正規表現の普遍性判定問題を用いて示される。
第４章「Kleene Algebra Under Weak Equivalences」:本章では、言語の構造における Kleene 代数（即ち、正規表現）の等価性の条件の弱化について考察する。とくに「２つの言語が p-同値である」ことを、「⾧さ 𝑛の文字列のうちいずれか一方の言語にのみ属する文字列の割合が 𝑛 → ∞ で漸近的に 0 に近づく」として定義し、p-同値の下での言語の問題（等価性/普遍性/空性判定問題）の計算複雑性の解析を行った。この等価性は、有限モデル論における概恒真性（almost-sure validity）を一般の構造から文字列の構造に制限することで得られる。本章では言語を表現するいくつかの主要なモデル（正規表現、有限オートマトン、文脈自由文法）に対して、とくに以下を示した：(1) p-同値の下での等価性/普遍性判定問題は、通常の等価性/普遍性判定問題の場合と同じ計算量クラスに対して完全。(2) （アルファベットの個数が２個以上の場合）p-同値の下での空性判定問
題は、通常の普遍性判定問題の場合と同じ計算量クラスに対して完全。計算量の上界については、p-同値性の述語論理的な特徴付けをオートマトン構造に対して与えることで（記述計算量理論の結果を経由して）示した。
下界の証明の主要な部分は、通常の普遍性判定問題から p-同値の下での普遍性/空性判定問題への帰着を与えることにより示した。系として、文脈自由文法に対しては（通常の空性判定問題が決定可能である一方で）p同値の下での空性判定問題が決定不可能になることを示した。本章の終わりでは、有限モデル論の概恒真性に基づく（即ち、二項関係の構造における）Kleene 代数の p-同値を導入し、２つの p-同値に関する比較を行う。

備考：論文要旨は、和文 2000 字と英文 300 語を 1 部ずつ提出するか、もしくは英文 800 語を 1 部提出してください。
Note : Thesis Summary should be submitted in either a copy of 2000 Japanese Characters and 300 Words (Engｌish) or 1copy of 800Words (English).
注意：論文要旨は、東工大リサーチリポジトリ（T2R2）にてインターネット公表されますので、公表可能な範囲の内容で作成してください。
Attention: Thesis Summary will be published on Tokyo Tech Research Repository Website (T2R2).

（博士課程）Doctoral Program論 文 要 旨ＴＨＥＳＩＳ ＳＵＭＭＡＲＹ

系・コース：
Department of, Graduate major in

数理・計算科学
数理・計算科学

学生氏名：
Student’s Name

中村 誠希

系
コース

申請学位（専攻分野）： 博士
Academic Degree Requested

指導教員（主）：Academic Supervisor(main)

Doctor of（理学）鹿島 亮 准教授

指導教員（副）：Academic Supervisor(sub)要旨（英文 300 語程度）
Thesis Summary （approx.300 English Words ）Kleene algebra is an algebraic generalization of regular expressions, which consists of two binaryoperations, union and concatenation, two nullary operations, the identity of union and the identity ofconcatenation, and one unary operation, iteration. Iteration is a basic operation for expressing behaviors ofprograms or expressing properties of models. Language semantics and relational semantics are two ofprincipal semantics in Kleene algebra. Relational semantics of Kleene algebra is related to relation algebra
and modal logic. The equational theory of Kleene algebra is decidable and PSPACE-complete. This thesis“Computational Complexity of Several Extensions of Kleene Algebra” consists of five chapters including thechapter of introduction and the chapter of concluding remarks. The other three chapters are outlined asfollows:
Chapter 2 “Introduction”: In this chapter we give some fundamental results of Kleene algebra in relationalsemantics and language semantics. In the section for Kleene algebra in relation semantics, we show that it
has relation to relation algebra and first-order logic and we introduce fundamental results of relation
algebra. In the section for Kleene algebra in language semantics, we introduce derivatives for regularexpressions. Actually the two equational theories of Kleene algebra defined in relational semantics andlanguage semantics are equivalent.
Chapter 3 “Derivatives for Kleene Allegories”: In this chapter we show that the equational theory of Kleene
algebra with relational intersection and relational converse in relational semantics (called Kleeneallegories) is decidable and EXPSPACE-complete. This problem was open in LICS ’15. For showing
decidability, we introduce derivatives on graphs based on derivatives on strings for regular expressions
introduced by Antimirov. The lower bound is proved by the EXPSPACE-hardness of the universality
problem for regular expressions with intersection.
Chapter 4 “Kleene Algebra Under Weak Equivalences”: In this chapter we study the equivalence problem
for Kleene algebra in language semantics under weak equivalences. In particular, we introduce pequivalence defined as follows: two languages are p-equivalent if and only if the limit of the density of thesymmetric difference of them is 0. We give several logical characterizations for p-equivalence and give thecomplexity upper bounds by the results of descriptive complexity theory. For lower bound, we show thateach language problem under p-equivalence is not easier than the one under normal equivalence in severalcases. In particular, for context-free grammars, the emptiness problem under p-equivalence is undecidable,
whereas the emptiness problem under the normal equivalence is decidable. Finally, we introduce pequivalence for Kleene algebra in relational semantics and compare the two p-equivalences.

備考 : 論文要旨は、和文 2000 字と英文 300 語を 1 部ずつ提出するか、もしくは英文 800 語を 1 部提出してください。
Note : Thesis Summary should be submitted in either a copy of 2000 Japanese Characters and 300 Words (Engｌish) or 1copy of 800
Words (English).
注意：論文要旨は、東工大リサーチリポジトリ（T2R2）にてインターネット公表されますので、公表可能な範囲の内容で作成してください。
Attention: Thesis Summary will be published on Tokyo Tech Research Repository Website (T2R2).