6A-4
シャフル表現による非同期イベント系列の記述
○阿部真也(東京都立産業技術研究センター)
システムの動作テストにおいて,実行時に発生したイベント系列が
開発者の意図する系列であるかどうかを判定するのは重要である.
イベント系列の記述には正規表現が用いられることが多い.ところ
が,各々のイベントが非同期並行的に実行されるようなシステムで
は,正規表現の記述能力では不十分であることが知られている.た
とえば,セマフォによる同期機構の動作を記述するには現在の状態
を保持する必要があるが,正規表現では数を記憶できないため記述
が困難である.本稿では,シャフル表現による非同期イベント系列
の記述法を提案し,代表的な非同期問題であるキュー問題,read/w
rite問題,セマフォの記述例を与える.