Recognizable Expressionと有限木オートマトンの等価性
スポンサーリンク
概要
- 論文の詳細を見る
近年のXMLの普及などにより, 木構造を持つ大量のデータを扱う機会が増えている. こうしたデータを処理するため, 簡潔に木言語を表現する方法が必要であると考えられる. そこで, Recognizable Expressionが提案された. Recognizable Expressionは木構造の表現を行なう従来研究の多くと比べ, 変数への束縛を明示せずに繰り返しを表現する点に特徴があり, 簡潔な表現に向いていると考えられる. これまでに, 任意の有限木オートマトンが受理する木の集合に対し, これを表現するRecognizable Expressionが存在することが分かっている. 本稿では, 任意のRecognizable Expressionが表現する木の集合に対し, これを受理する有限木オートマトンを構成できることを示す. これによって, Recognizable Expressionと有限木オートマトンの等価性が示されたことになる.
- 2005-03-11
著者
関連論文
- 剰余選択ゲームに基づいたくじ引きシステム
- プログラミング,何をどう教えているか 関数型言語Standard MLのプログラミング教育
- 関数型言語Standard MLのプログラミング教育(プログラミング,何をどう教えているか)
- 小規模なコーパスを用いた仮名漢字混じり文と仮名文の対応づけ
- 小規模なコーパスを用いた仮名漢字混じり文と仮名文の対応づけ
- Rongorongo符号列とイースター島古謡音韻列の対応
- Rongorongo符号列とイースター島古謡音韻列の対応
- 一般化されたプッシュダウン木変換器の合成と分解に関する一考察
- Recognizable Expressionと有限木オートマトンの等価性
- 3.国際大学対抗プログラミングコンテスト(未来のコンピュータ好きを育てる)
- Recognizable Expression と有限木オートマトンの等価性
- Recognizable Setの記号列表現
- プッシュダウン木変換器の合成と分解に関する一考察
- プッシュダウン木変換器の分類に関する一考察
- 上昇型プッシュダウン木オートマトンと文脈自由木文法の関係
- COMP2000-18 一般化されたプッシュダウン木変換器の変換能力に関する一考察
- 一般化されたプッシュダウン木変換器の基本的性能
- ★付き上昇型プッシュダウン木オートマトンの拡張
- 上昇型プッシュダウン木オートマトンと文脈自由木文法の関係
- 文脈自由木文法の変数に関する一考察
- 上昇型プッシュダウン木オートマトンの一構成法
- 上昇型プッシュダウン木変換器と下降型プッシュダウン木変換器の比較
- 上昇型プッシュダウン木変換器の基本的性質
- 上昇型プッシュダウン木オートマトンの一構成法
- プッシュダウン木オートマトンに対するuvwxy定理
- 上昇型プッシュダウン木オートマトンと下降型プッシュダウン木オートマトンの受理能力の比較について