On Transitive Closure Logic

Abstract We present Ehrenfeucht-Fraïssé games for transitive closure logic (FO + TC) and for quantifier classes in (FO + TC). With this method we investigate the fine structure of positive transitive closure logic (FO + pos TC), and identify an infinite quantifier hierarchy inside (FO + pos TC), formed by interleaving universal quantifiers and TC-operators. It is also shown that transitive closure logic (and its fragments) have the same expressive power as the linear programs in certain extensions of Datalog.

Authors

• Erich Grädel

Keywords

No keywords are indexed for this paper.