On the complexity of the two-variable guarded fragment with transitive guards

by Emanuel Kieronsk.
Information and Computation
Volume 204, Issue 11, November 2006, Pages 1663-1703
http://dx.doi.org/10.1016/j.ic.2006.08.001

筆者のSTACS2002論文とFOSSACS2003論文をまとめたもの。
表題にある「two-variable guarded fragment with transitive guards」という論理におけるsatisfiabilityを調べている。
ここら辺の論理は命題様相論理を含んでいるようで、satisfiabilityのcomplexityは割と高い。
論文1668ページに問題のクラスの包含関係とcomplexityの対応を描いたダイアグラムがあって、少しマニアックで楽しい。
だいたいアブストラクトとイントロだけを見て斜め読み終了。