26日に18:30~20:00にかけて秋田大学生協にて簡単な交流会(参加費1000円程度,軽食とドリンク付き)を,27日は大学から2kmほどのビアカフェで懇親会(参加費3000円程度,飲み放題夕食込み)を行う予定です.
人数を把握する必要があるため,交流会・懇親会への参加を希望されるかたは,参加希望の旨を3月11日(月)までに新屋( ryoma@math.akita-u.ac.jp )にご連絡よろしくお願いします.
参加申し込みは締め切りました.
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.
オートマトンとゲーム,論理の関係性について,様相μ計算と交替性木オートマトン,パリティゲームを用いて説明する.
また,それらのtransfinite extensionモデルを導入し,どのような性質を持つのかをみていく.
本発表では、一階述語論理に対するLindstrom Theoremの証明をします。
一階述語論理が満たす性質にはさまざまなものがありますが、逆にLindstrom Theoremでは、どのような性質を与えれば一階述語論理になるのか、つまり一階述語論理の十分性に関する主張です。これは一階述語論理の特徴付けとも言え、モデル理論における重要な定理です。
Parikh matrix mapping は文字列の特定の部分文字列の出現回数の情報を保持した行列に写す写像です。
今回は特定の形をした文字列の集合(suffle words)のParikh matrix mappingの像の濃度について話させていただきます。
文字列を不連続に読み込むジャンピングオートマトンが考えられています。
その中で右一方向ジャンピング有限オートマトンとスタック機能を持った右一方向ジャンピング有限オートマトンについて説明します。
Konig-Egervary theoremを3次元に拡張できるかどうか考察しました。
いくつかの例について計算機実験で確認しました。
本発表では、Rearrangement Problem of two-dimensional colored arrays by Prefix Reversalsと呼ばれる再配置問題を、一般化したMulti Colored Rearrangement Problem of Arrays by Prefix Reversalsについて説明し、色の種類が奇数だった場合の標準配列に帰着可能な配列の必要十分条件とその証明の概略について話す。
古典一階述語論理のTarski意味論から始めて、初等的なモデル理論を概説する。
特に、具体的な数学へのモデル理論の応用例を紹介しつつ、モデル理論における種々の概念と数学的現象との関わりに重点を置いて話す。
理論計算機科学(計算論,形式言語理論)における正則性(regularity)はとても素朴ですが重要な概念です.
本講演では言語(文字列の集合)を表現する上でMSO(単項二階述語論理)と有限オートマトンが同じ表現力を持つという Büchi の定理を通じて論理式とオートマトンの関係をみていきます.
劣モジュラ関数は凸関数に似た性質をもつ離散関数のクラスであり,機械学習・経済学など様々な応用領域で自然に現れる.
与えられた劣モジュラ関数を最大化する問題は最も基本的な離散最適化問題の1つであり,これまでに様々な実行可能領域上で(近似的に) 最大化する方法が研究されてきた.
本研究では「実行可能領域がグラフに関する論理式で指定される」という設定を初めて考察し,グラフ・論理式がそれぞれ適当なクラスに属する場合に効率的な近似アルゴリズムが存在することを示す.
関係計算 (The Calculus of Relations) とは二項関係の結合と反転の演算に加えて集合の積、和、補の演算を持つ代数で、FO3 (3変数制限付き一階述語論理) と表現力が等しい。
発表では、関係計算から補演算を除いたポジティブ関係計算 (The Positive Calculus of Relations) について紹介する。
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.