セルオートマトン

セルオートマトンは多数のセルを規則的に連結・配置して,そのセルの集合を表す状相が動的に変化するシステムのことです.

セルオートマトンの定義

セルオートマトン(CA)は以下のように定義されます.\[CA=(\mathbb{Z}^{k},Q,N,f,c)\]ここで,

状相

\[\alpha : \mathbb{Z}^{k} \to Q\]を満たす写像 $\alpha$ を集合 $Q$ 上の $k$ 次元の状相といいます.

集合 $Q$ 上の $k$ 次元の全ての状相の集合を,\[Conf_{k}(Q)=\{\alpha | \alpha :\mathbb{Z}^{k} \to Q\}\]と表します.

集合\[\{x | x \in \mathbb{Z}^{k} \land \alpha(x) \neq c\}\]であるとき,状相 $\alpha$ は有限と言われます.

大域関数

\[Conf_{k}(Q) \to Conf_{k}(Q)\]という関数を,\[\forall \alpha \in Conf_{k}(Q),\forall x \in \mathbb{Z}^{k}\]のとき,\[F(\alpha)(x)=f(\alpha(x+n_{1}),\cdots,\alpha(x+n_{m}))\]と定義して,$F$ を状相の遷移を定める大域関数といいます.

超離散化

微分方程式
(ソリトン方程式)
差分方程式セルオートマトン
(超離散方程式)
時間・空間連続離散離散
変数連続連続離散

多重文脈自由文法(MCFG)

文字列集合と,$m$ 組の文字列対を同時に帰納的に定義する文法のことを多重文脈自由文法(MCFG)といいます.

多重文脈自由文法(MCFG)は関浩之が1980年代に考案したもので,単数形の単文,複数形の単文を交差した文である交差構造を記述できる文法として多重文脈自由文法(MCFG)を提案しました.これが後に,機能RNAの2次構造の予測に役立つことに繋がっていきました.

文字列が格子の上を動く軌跡として表現できるような,$A$ と $\overline{A}$ を同数含むような原点回帰文字列の全てが多重文脈自由文法になるというわけではありません.


Kasami, Seki & Fujii, Tech. Rep., Osaka U. 1987, also in IEICE Trans., J71-D-I(5,6), 1988.

Vita brevis, ars longa. Omnia vincit Amor.





















濃度 真偽値の領域 プッシュダウンオートマトン スタック 連接 conjunction 正規表現 regular expression