Automata and Logic Workshop in AKITA

秋田大学にてオートマトンとロジックのワークショップを行います．

参加申し込みは不要です．部分参加も歓迎です．入門的な招待講義(invited lecture)もありますのでぜひ学生の皆様もご気軽にお参加ください．


ワークショップは無事終了いたしました．25名の参加者(うち講演者11名)の皆様，大変ありがとうございました．

日時・場所

  • 日時：2019年3月26日(火) 14:00 -- 3月27日(水) 19:00
  • 場所：〒010-8502 秋田市手形学園町1番1号 秋田大学手形キャンパス総合研究棟 2階講義室 (学内地図)
  • 世話人：新屋良磨 (秋田大学 数理科学コース)
  • 連絡先： ryoma@math.akita-u.ac.jp
  • 備考：26日(火)の講演は14:00からの開始ですが，東京から秋田への移動には新幹線で4時間ほどかかるのでご注意ください．また27日(水)には19:00から懇親会を開始いたしますので秋田に後泊されることをお勧めします．ぜひ懇親会にもご参加ください．

プログラム

3月26日(火)

  • 13:00：開場
  • 13:45--14:00：開会式
  • 14:00--15:00：湯山孝雄(東工大)「Decidability of Presburger Arithmetic via Finite Automata」(invited lecture) (スライド)
  • 15:20--16:00：中林美郷(東北大)「オートマトンとゲームと論理」
  • 16:00--16:20：木内詠美(東工大)「Lindström Theorem」(スライド)
  • 16:30--16:45：本間海斗(秋田大)「The Number of Parikh Matrices on Shuffle Words」
  • 16:45--17:00：星 魁人(秋田大)「Automata reading discontinuous character strings」
  • 17:00--17:15：保坂大介(秋田大)「Computer experiment for extension of Konig-Egervary theorem」
  • 17:15--17:30：加瀬 力(秋田大)「Multi Colored Rearrangement Problem of Arrays by Prefix Reversals」
  • 17:45--20:00：交流会@秋田大学大学会館「クレール」2F

3月27日(水)

  • 10:30--12:00：荒武永史(京都大)「モデル理論から見る数学」(invited lecture) (スライド)
  • 12:00--13:20：昼休み
  • 13:20--14:00：新屋良磨(秋田大)「有限モデル理論入門：MSOとオートマトン」(lecture) (スライド)
  • 14:20--15:20：前原貴憲(理研AIP)「劣モジュラ最大化に対するアルゴリズム的メタ定理」(スライド)
  • 15:40--16:40：中村誠希(東工大)「ポジティブ関係計算について」(スライド)
  • 17:00--17:40：湯山孝雄(東工大)「Undecidability of Hilbert's Tenth Problem and its Applications」(スライド) (Best Presentation Award)
  • 17:40--18:00：閉会式
  • 19:00--21:00：懇親会 (開催予定地：ビアカフェあくら)

交流会・懇親会への参加

26日に18:30~20:00にかけて秋田大学生協にて簡単な交流会(参加費1000円程度，軽食とドリンク付き)を，27日は大学から2kmほどのビアカフェで懇親会(参加費3000円程度，飲み放題夕食込み)を行う予定です．

人数を把握する必要があるため，交流会・懇親会への参加を希望されるかたは，参加希望の旨を3月11日(月)までに新屋( ryoma@math.akita-u.ac.jp )にご連絡よろしくお願いします．

参加申し込みは締め切りました．


各講演概要

湯山孝雄(東工大)「Decidability of Presburger Arithmetic via Finite Automata」(invited lecture, 60 minutes)

Presburger arithmetic is the theory of the natural numbers which lacks the multiplication symbol $\times$.

Amazingly, while the full theory of the naturals is undecidable due to G\"odel's incompleteness theorem, Presburger arithmetic is decidable.

That is, one can construct an algorithm for deciding whether a given formula without multiplication is true or not.

We demonstrate the decidability by using the theory of automata.


中林美郷(東北大)「オートマトンとゲームと論理」(40 minutes)

オートマトンとゲーム，論理の関係性について，様相μ計算と交替性木オートマトン，パリティゲームを用いて説明する．

また，それらのtransfinite extensionモデルを導入し，どのような性質を持つのかをみていく．


木内詠美(東工大)「Lindström Theorem」(20 minutes)

本発表では、一階述語論理に対するLindstrom Theoremの証明をします。

一階述語論理が満たす性質にはさまざまなものがありますが、逆にLindstrom Theoremでは、どのような性質を与えれば一階述語論理になるのか、つまり一階述語論理の十分性に関する主張です。これは一階述語論理の特徴付けとも言え、モデル理論における重要な定理です。


本間海斗(秋田大)「The Number of Parikh Matrices on Shuffle Words」(15 minutes)

Parikh matrix mapping は文字列の特定の部分文字列の出現回数の情報を保持した行列に写す写像です。

今回は特定の形をした文字列の集合(suffle words)のParikh matrix mappingの像の濃度について話させていただきます。


星 魁人(秋田大)「Automata reading discontinuous character strings」(15 minutes)

文字列を不連続に読み込むジャンピングオートマトンが考えられています。

その中で右一方向ジャンピング有限オートマトンとスタック機能を持った右一方向ジャンピング有限オートマトンについて説明します。


保坂大介(秋田大)「Computer experiment for extension of Konig-Egervary theorem」(15 minutes)

Konig-Egervary theoremを3次元に拡張できるかどうか考察しました。

いくつかの例について計算機実験で確認しました。


加瀬 力(秋田大)「Multi Colored Rearrangement Problem of Arrays by Prefix Reversals」(15 minutes)

本発表では、Rearrangement Problem of two-dimensional colored arrays by Prefix Reversalsと呼ばれる再配置問題を、一般化したMulti Colored Rearrangement Problem of Arrays by Prefix Reversalsについて説明し、色の種類が奇数だった場合の標準配列に帰着可能な配列の必要十分条件とその証明の概略について話す。


荒武永史(京都大)「モデル理論から見る数学」(invited lecture, 90 minutes)

古典一階述語論理のTarski意味論から始めて、初等的なモデル理論を概説する。

特に、具体的な数学へのモデル理論の応用例を紹介しつつ、モデル理論における種々の概念と数学的現象との関わりに重点を置いて話す。


新屋良磨(秋田大)「有限モデル理論入門：MSOとオートマトン」(lecture, 40 minutes)

理論計算機科学(計算論，形式言語理論)における正則性(regularity)はとても素朴ですが重要な概念です．

本講演では言語(文字列の集合)を表現する上でMSO(単項二階述語論理)と有限オートマトンが同じ表現力を持つという Büchi の定理を通じて論理式とオートマトンの関係をみていきます．


前原貴憲(理研AIP)「劣モジュラ最大化に対するアルゴリズム的メタ定理」(60 minutes)

劣モジュラ関数は凸関数に似た性質をもつ離散関数のクラスであり，機械学習・経済学など様々な応用領域で自然に現れる．

与えられた劣モジュラ関数を最大化する問題は最も基本的な離散最適化問題の１つであり，これまでに様々な実行可能領域上で(近似的に) 最大化する方法が研究されてきた．

本研究では「実行可能領域がグラフに関する論理式で指定される」という設定を初めて考察し，グラフ・論理式がそれぞれ適当なクラスに属する場合に効率的な近似アルゴリズムが存在することを示す．


中村誠希(東工大)「ポジティブ関係計算について」(60 minutes)

関係計算 (The Calculus of Relations) とは二項関係の結合と反転の演算に加えて集合の積、和、補の演算を持つ代数で、FO3 (3変数制限付き一階述語論理) と表現力が等しい。

発表では、関係計算から補演算を除いたポジティブ関係計算 (The Positive Calculus of Relations) について紹介する。


湯山孝雄(東工大)「Undecidability of Hilbert's Tenth Problem and its Applications」(40 minutes) (Best Presentation Award)

Hilbert's tenth problem is a decision problem that asks whether a given polynomial equation with integer coefficients has an integer solution.

In 1970, Y. V. Matiyasevich completed a proof of undecidability of the problem.

We explain an outline of the proof and some consequences of the undecidability.