| 大会名称 |
|---|
| 1995年 総合大会 |
| 大会コ－ド |
| 1995G |
| 開催年 |
| 1995 |
| 発行日 |
| 1995-03-27 |
| 講演日 |
| 講演場所(会議室等) |
| 講演番号 |
| A-109 |
| タイトル |
| ゼロサプレス型BDDを用いた系列長制限つき正規表現処理方法 |
| 著者名 |
| 石原 晋也, 湊 真一, |
| キーワード |
| 抄録 |
| 有限状態機械の表現や操作法はLSIの形式的仕様記述や検証の基礎技術として重要である.しかしながら,現状では有限状態機械が大規模であったり複雑であったりすると,とたんに計算上での処置が困難になっていた.本稿では,言語の系列長を制限することによって正規表現を計算機上で処理する方法を提案する.今回の実装では,O-suppressed-BDD[Min93](以下、ZBDDと予呼ぶ)処理系を利用することにより計算機上でのコンパクトかつ高速な処理を実現した.ここでいうZBDDは,組合せ集合の表現を通常のBDD[Bry86]よりも効率的かつ自然に渡すことができるという特徴を持っている.実験評価した結果から見て今回の実装は,有限長ではあるが正規表現を簡単に処理することが可能であり,有限状態機械のあるステップまでの動作の確認を容易に行うことが期待できる. |
| 本文pdf |
|
PDF download
|