Hierarchies in Inclusion Logic with Lax Semantics - Logic and Its Applications - page 111

LOGSPACE < PTIME. It might be possible to prove similar results for inclusion
logic by relating the fragments FO( )( k -inc) to arity fragments of fixed-point

logics. However, the translations between FO(

ↆ

ↆ

) and GFP provided in [5] do not
respect arities. It remains open whether collapse of the FO( )( k -inc)-hierarchy

or its negation have such strong consequences or whether it is possible to relate
the FO(

ↆ

)( k -inc)-fragments in ordered models to the degree hierarchy within
PTIME? Another line would be to find some other syntactical parameter that
would fit for this purpose.

References

1. Galliani, P.: Inclusion and exclusion dependencies in team semantics: On some
logics of imperfect information. Annals of Pure and Applied Logic 163(1), 68 (2012)
2. Vaananen, J.: Dependence Logic. Cambridge University Press (2007)
3. Hodges, W.: Compositional Semantics for a Language of Imperfect Information.
Journal of the Interest Group in Pure and Applied Logics 5(4), 539-563 (1997)
4. Galliani, P., Hannula, M., Kontinen, J.: Hierarchies in independence logic. In:
Rocca, S.R.D. (ed.) Computer Science Logic 2013 (CSL 2013). Leibniz Interna-
tional Proceedings in Informatics (LIPIcs), vol. 23, pp. 263-280. Schloss Dagstuhl-
Leibniz-Zentrum fuer Informatik, Dagstuhl (2013)
5. Galliani, P., Hella, L.: Inclusion Logic and Fixed Point Logic. In: Rocca, S.R.D.
(ed.) Computer Science Logic 2013 (CSL 2013). Leibniz International Proceedings
in Informatics (LIPIcs), vol. 23, pp. 281-295. Schloss Dagstuhl-Leibniz-Zentrum
fuer Informatik, Dagstuhl (2013)
6. Abramsky, S., Vaananen, J.: From IF to BI. Synthese 167, 207-230 (2009),
doi:10.1007/s11229-008-9415-6
7. Yang, F.: Expressing Second-order Sentences in Intuitionistic Dependence Logic.
Studia Logica 101(2), 323-342 (2013)
8. Gradel, E.: Model-checking games for logics of imperfect information. Theor. Com-
put. Sci. 493, 2-14 (2013)
9. Kontinen, J.: Coherence and computational complexity of quantifier-free depen-
dence logic formulas. In: Kontinen, J., Vaananen, J. (eds.) Proceedings of Depen-
dence and Independence in Logic. ESSLLI, pp. 58-77 (2010)
10. Durand, A., Kontinen, J.: Hierarchies in dependence logic. ACM Transactions on
Computational Logic (TOCL) 13(4), 31 (2012)
11. Galliani, P., Vaananen, J.A.: On dependence logic. In: Baltag, A., Smets, S. (eds.)
Johan van Benthem on Logical and Informational Dynamics, pp. 101-119. Springer
(2014)
12. Ajtai, M.: ʣ 1 -formulae on finite structures. Ann. Pure Appl. Logic 4(1), 1-48
(1983)
13. Grohe, M.: Arity hierarchies. Ann. Pure Appl. Logic 82(2), 103-163 (1996)
14. Hannula, M., Kontinen, J.: Hierarchies in independence and inclusion logic with
strict semantics. Journal of Logic and Computation (2014), doi: 10.1093/log-
com/exu057