×

The expressive power of \(k\)-ary exclusion logic. (English) Zbl 1477.03102

Väänänen, Jouko (ed.) et al., Logic, language, information, and computation. 23rd international workshop, WoLLIC 2016, Puebla, Mexico, August 16–19th, 2016. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 9803, 375-391 (2016).
Summary: In this paper we study the expressive power of \(k\)-ary exclusion logic, \(\text{EXC}[k]\), that is obtained by extending first order logic with \(k\)-ary exclusion atoms. It is known that without arity bounds exclusion logic is equivalent with dependence logic. From the translations between them we see that the expressive power of \(\text{EXC}[k]\) lies in between \(k\)-ary and \((k+1)\)-ary dependence logics. We will show that, at least in the case of unary exclusion logic, the both of these inclusions are proper.{ } In a recent work by the author it was shown that \(k\)-ary inclusion-exclusion logic is equivalent with \(k\)-ary existential second order logic, \(\text{ESO}[k]\). We will show that, on the level of sentences, it is possible to simulate inclusion atoms with exclusion atoms, and this way express \(\text{ESO}[k]\)-sentences by using only \(k\)-ary exclusion atoms. For this translation we also need to introduce a novel method for “unifying” the values of certain variables in a team. As a consequence, \(\text{EXC}[k]\) captures \(\text{ESO}[k]\) on the level of sentences, and thus we get a strict arity hierarchy for exclusion logic. It also follows that \(k\)-ary inclusion logic is strictly weaker than \(\text{EXC}[k]\).
For the entire collection see [Zbl 1343.03002].

MSC:

03B60 Other nonclassical logic
03B16 Higher-order logic
03C80 Logic with extra quantifiers and operators
03C85 Second- and higher-order model theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ajtai, M.: \[ \varSigma _1^1 \] -formulae on finite structures. Ann. Pure Appl. Logic 724(1), 1–48 (1983) · Zbl 0519.03021 · doi:10.1016/0168-0072(83)90038-6
[2] Dawar, A.: A restricted second order logic for finite structures. Inf. Comput. 143(2), 154–174 (1998) · Zbl 0909.68078 · doi:10.1006/inco.1998.2703
[3] Durand, A., Kontinen, J.: Hierarchies in dependence logic. ACM Trans. Comput. Log. 13(4), 31 (2012) · Zbl 1352.03039 · doi:10.1145/2362355.2362359
[4] Galliani, P.: The Dynamics of Imperfect Information. Institute for Logic Language and Computation, Amsterdam (2012) · Zbl 1250.03047
[5] Galliani, P.: Inclusion and exclusion dependencies in team semantics - on some logics of imperfect information. Ann. Pure Appl. Logic 163(1), 68–84 (2012) · Zbl 1250.03047 · doi:10.1016/j.apal.2011.08.005
[6] Galliani, P., Hannula, M., Kontinen, J.: Hierarchies in independence logic. In: CSL 2013, pp. 263–280 (2013) · Zbl 1356.03070
[7] Galliani, P., Hella, L.: Inclusion logic and fixed point logic. In: CSL 2013, pp. 281–295 (2013) · Zbl 1356.03071
[8] Grädel, E., Väänänen, J.A.: Dependence and independence. Studia Logica 101(2), 399–410 (2013) · Zbl 1272.03125 · doi:10.1007/s11225-013-9479-2
[9] Hannula, M.: Hierarchies in inclusion logic with lax semantics. In: Banerjee, M., Krishna, S.N. (eds.) ICLA. LNCS, vol. 8923, pp. 100–118. Springer, Heidelberg (2015) · Zbl 1304.03071 · doi:10.1007/978-3-662-45824-2_7
[10] Hannula, M., Kontinen, J.: Hierarchies in independence and inclusion logic with strict semantics. J. Log. Comput. 25(3), 879–897 (2015) · Zbl 1345.03051 · doi:10.1093/logcom/exu057
[11] Hintikka, J., Sandu, G.: Informational independence as a semantical phenomenon VIII. In: Fenstad, J.E. (ed.) Logic, Methodology and Philosophy of Science, pp. 571–589. Elsevier, Amsterdam (1989) · Zbl 0683.03004
[12] Hintikka, J., Sandu, G.: Game-theoretical semantics. In: van Benthem, J., ter Meulen, A. (eds.) Handbook of Logic and Language, pp. 361–410. Elsevier, Amsterdam (1997) · doi:10.1016/B978-044481714-3/50009-6
[13] Hodges, W.: Compositional semantics for a language of imperfect information. Log. J. IGPL 5(4), 539–563 (1997) · Zbl 0945.03034 · doi:10.1093/jigpal/5.4.539
[14] Hyttinen, T., Paolini, G., Väänänen, J.: Quantum team logic and Bell’s inequalities. Rev. Symb. Log. 8, 722–742 (2015) · Zbl 1371.03098 · doi:10.1017/S1755020315000192
[15] Kontinen, J., Link, S., Väänänen, J.: Independence in database relations. In: Libkin, L., Kohlenbach, U., de Queiroz, R. (eds.) WoLLIC 2013. LNCS, vol. 8071, pp. 179–193. Springer, Heidelberg (2013) · Zbl 1394.68116 · doi:10.1007/978-3-642-39992-3_17
[16] Kontinen, J., Väänänen, J.A.: On definability in dependence logic. J. Log. Lang. Inf. 18(3), 317–332 (2009) · Zbl 1182.03063 · doi:10.1007/s10849-009-9082-0
[17] Rönnholm, R.: Capturing k-ary inclusion-exclusion logic with k-ary existential second order logic (2015). arXiv:1502.05632 [math.LO] · Zbl 1477.03103
[18] Rönnholm, R.: The expressive power of k-ary exclusion logic (2016). arXiv:1605.01686 [math.LO] · Zbl 1477.03102
[19] Väänänen, J.A.: Dependence logic - a new approach to independence friendly logic. London Mathematical Society Student Texts, vol. 70. Cambridge University Press (2007) · Zbl 1117.03037 · doi:10.1017/CBO9780511611193
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.