2015-10-22から1日間の記事一覧
遷移インスタンスは次のように書くことにする。 s|-(x, y)→s' a, bを非ブランク記号、ブランク記号を_とすると、次の分類がある。 s|-(a, b)→s' s|-(_, b)→s' s|-(a, _)→s' s|-(_, _)→s' ブランクを省略すると、 s|-(a, b)→s' s|-(, b)→s' s|-(a,)→s' s|-(,)…
ラベル概念がクセモノ。ラベルは遷移グラフの辺に付くナニカだが、 入力となる記号、データ、イベント、メッセージ 出力となる記号、データ、イベント、メッセージ 命令、アクション、コマンドの名前 その他、コンストラクタやオブザーバーの名前 おおざっぱ…
マイヒル/ネロードの定理はメイヤーオートマトンに対するものとする。 エルブランの定理 マイヒル/ネロードの定理 定数記号 コンストラクタ記号 関数記号 コマンド・メソッド記号 述語記号 クエリー・メソッド記号 基礎項 コマンド列=状態項≒プログラムコ…
2-豊饒化(2-enrichments)とベッチ・オートマトン - 檜山正幸のキマイラ飼育記 メモ編に2-豊穣化が出てる。http://arxiv.org/abs/cs/0602077 に基づく議論。だが、これは大げさ。次で十分だろう。Mを順序モノイドとする。典型的には Lang(Σ) = Pow(Σ*) に連…
Definition 6.3.Let A = (M, A, s, ・, Ω) be a left K-linear automaton. The language accepted by A is the function ρA : A → K such that ρA(a) = Ω(a・s). オートマトンの受理言語(accepted language)を集合ではなくて線形写像(射)として捉える。 …
↓とか見ると、ベッチが何言ってるか分かる。 Title: Tree Automata and Enriched Category Theory Authors: Renato Betti, Stefano Kasangian URL: http://rendiconti.dmi.units.it/volumi/17/07.pdf Pages: 8p
あれれれっ!? James Worthingtonのオートマトンに言及してなかった。例えば、 Title: A Bialgebraic Approach to Automata and Formal Language Theory Author: James Worthington URL: http://www.math.cornell.edu/~worthing/bialgebra.pdf Kを基礎半環(…