おーぷんぷろぶれむ！（１） ～ PEL ⊃ CFL 問題 - kmizuの日記
こんばんは。久しぶりにブログ書いてみることにしたのですが、以前と同じネタだとモチベーションが保てないので、今回はちょっと変わったタイトルにしてみました。 平仮名にしたかっただけだろうおまえと言われそうですね。はいそうです。 というのはおいといて、たいとるのおーぷんぷろぶれむ(Open Problem)ですが、日本語では未解決問題と訳すことが多いようです。読んで字のごとく、未だ解決されていない問題のことです。存在する（はず）だけど見つかっていないアルゴリズムとか、真か偽かがまだわかってない命題とかのことですね。ちなみに、当たり前ですが、解決された時点でOpen Problemでなくなってしまいます。 第何回まで続くか１回で終わるかはわかりませんが、第１回では、PEL ⊃ CFL問題について紹介します。この問題は、2004年にBryan Fordによって、論文 "Parsing Express
形式言語理論のための代数 - 檜山正幸のキマイラ飼育記 (はてなBlog)
形式言語理論は、かなりの程度、代数的に定式化できます。例えば、形式言語の全体は順序半環、オートマトンはその順序半環を係数とする正方行列だと思えます。オートマトンの初期状態と終状態、オートマトンのあいだの模倣（simulation）関係なども行列により表現できます。 ここでは、できるだけ手短に形式言語理論のための代数、特に半環係数行列の概念を説明します。形式言語とオートマトンの基礎事項についても概要を述べますが、とてもラフな記述なので、他の資料や教科書で予備知識は仕入れておいたほうがいいでしょう。図を多用して幾何的・物理的な比喩を使うと分かりやすくなるとは思うのですが、今回は絵は描きませんでした。絵による説明はまたの機会に。 目標はオートマトンと模倣の圏を作ることです。オートマトンは代数的には正方行列となります。関係圏Rel（の部分圏）をインデキシング圏とするインデックス付き圏を作り、そのグ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
