組合せ遷移は有界モデル検査とどういう関係にあるのかについて聞かれることがあるそうです.このことを議論できるようにするための準備として,有界モデル検査についてはじめて聞く人にも分かるようなレベルで解説する予定です.さらに組合せ遷移の観点では,AIプランニングとの関係も見逃せないと個人的に思うので簡単に解説します.これら2つは古典的な話題です(最近の研究動向には一切触れません). 一方で,組合せ遷移の理論と実践が交差する,興味深い最近の話題としてネットワークアップデートがあります.現実のネットワークでは設定(例えばあるルータでどのパケットをどこに転送するか)を変更するときに,ネットワークを止めないで安全かつ迅速に更新をすることが求められます.安全性や許される操作などの問題設定がさまざまだったので,理論アルゴリズムの観点から手が出しにくい状況でしたが,最近モデルが整備されアクセスしやすくなっています.そのような中,組合せ遷移の観点からの理論研究はAmiriらを中心に始ったばかりのようです. 横断的な(欲張りな?)テーマであり,十分に説明できないところがあるかもしれません.