ポスト対応問題(Post's Correspondence Problem：ＰＣＰ)は 与えられた記号列の対の有限集合に対して、その集合に含まれる対の 系列で次の条件を満たすものを発見する問題である。
・系列に含まれる対の第１要素、第２要素をそれぞれ取り出し、 連接した記号列が互いに等しくなる。
ＰＣＰは決定不能であることが知られている。
本研究はＰＣＰの記号アルファベットを限定した上で、
ＰＣＰを解く過程、つまり第１要素と第２要素の連接が等しくなるように
対の系列を構成していく過程に焦点を当て、各段階におけるＰＣＰの構成要素
がどのように変化してゆくのか、または構成要素間に何らかの関係が存在するのか
を、
ランダムにＰＣＰインスタンスを生成し、それらを統計的に調査したものである。
具体的な方法として、ＰＣＰの解発見過程を木で表し、その木を自動的に生成・調
査し、
必要な情報をデータ化するプログラムを作成し、
データを必要に応じて抽出することでＰＣＰの統計的な振舞を調査した。
調査の結果、ＰＣＰそのものの発見的な変化・関係は認められず、
例えば、ＰＣＰに与えられた記号列の数が増大すると
木の深さが増大する可能性が高まる、といったような
自然な統計的振舞は得ることができた。