Approximation and dependence via multiteam semantics

1. Böttcher, S., Link, S., Zhang, L.: Pulling conjunctive query equivalence out of the bag. In: Proceedings 23rd ACM CIKM, pp. 41–50. ACM (2014)

2. Chaudhuri, S., Vardi, M.Y.: Optimization of real conjunctive queries. In: Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS ’93, pp. 59–70, New York, NY, USA. ACM (1993)

3. Durand, A., Kontinen, J., de Rugy-Altherre, N., Väänänen, J.: Tractability frontier of data complexity in team semantics. Proc. 6th GandALF, EPTCS 193, 73–85 (2015)

   Article  MathSciNet  Google Scholar 

4. Durand, A., Kontinen, J., Vollmer, H.: Expressivity and complexity of dependence logic. In: Abramsky, S., Kontinen, J., Väänänen, J., Vollmer, H. (eds.) Dependence Logic: Theory and Applications, pp. 5–32. Springer International Publishing (2016)

5. Ebbing, J., Hella, L., Meier, A., Müller, J.-S., Virtema, J., Vollmer, H.: Extended modal dependence logic. In: WoLLIC, volume 8071 of Lecture Notes in Computer Science, pp. 126–137. Springer Berlin Heidelberg (2013)

6. Galliani, P.: Probabilistic dependence logic. Manuscript (2008)

7. Galliani, P.: Inclusion and exclusion dependencies in team semantics - on some logics of imperfect information. Ann. Pure Appl. Logic 163(1), 68–84 (2012)

   Article  MathSciNet  MATH  Google Scholar 

8. Galliani, P., Hannula, M., Kontinen, J.: Hierarchies in independence logic. In: Ronchi, S., Rocca, D. (eds.) Computer Science Logic 2013 (CSL 2013), CSL 2013, September 2-5, 2013, Torino, Italy, volume 23 of LIPIcs, pp. 263–280 (2013)

9. Galliani, P., Hella, L.: Inclusion logic and fixed point logic. In: Proc. CSL, pp. 281–295 (2013)

10. Galliani, P., Mann, A.L.: Lottery semantics: A compositional semantics for probabilistic first-order logic with imperfect information. Studia Logica 101(2), 293–322 (2013)

    Article  MathSciNet  MATH  Google Scholar 

11. Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified np-complete graph problems. Theor. Comput. Sci. 1, 237–267 (1976)

    Article  MathSciNet  MATH  Google Scholar 

12. Grȧdel, E., Vȧȧnȧnen, J.A.: Dependence and independence. Studia Logica 101(2), 399–410 (2013)

    Article  MathSciNet  Google Scholar 

13. Gyssens, M., Niepert, M., Gucht, D.V.: On the completeness of the semigraphoid axioms for deriving arbitrary from saturated conditional independence statements. Inf. Process. Lett. 114(11), 628–633 (2014)

    Article  MathSciNet  MATH  Google Scholar 

14. Hannula, M., Kontinen, J.: Hierarchies in independence and inclusion logic with strict semantics. J. Log. Comput. 25(3), 879–897 (2015)

    Article  MathSciNet  MATH  Google Scholar 

15. Hannula, M., Kontinen, J.: A finite axiomatization of conditional independence and inclusion dependencies. Inf. Comput. 249, 121–137 (2016)

    Article  MathSciNet  MATH  Google Scholar 

16. Hannula, M., Kontinen, J., Link, S.: On the finite and general implication problems of independence atoms and keys. J. Comput. Syst. Sci. 82(5), 856–877 (2016)

    Article  MathSciNet  MATH  Google Scholar 

17. Hannula, M., Kontinen, J., Virtema, J., Vollmer, H.: Complexity of propositional independence and inclusion logic. In: Proceedings 40th MFCS, volume 9234 of LNCS, pp. 269–280. Springer (2015)

18. Hella, L., Kuusisto, A., Meier, A., Virtema, J.: Model checking and validity in propositional and modal inclusion logics. In: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), volume 83 of Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik (2017)

19. Hintikka, J., Sandu, G.: Informational independence as a semantical phenomenon. In: Logic, Methodology and Philosophy of Science, volume 8, pp. 571–589. Elsevier, Amsterdam (1989)

20. Hodges, W.: Compositional semantics for a language of imperfect information. Log. J. IGPL 5(4), 539–563 (1997). electronic

    Article  MathSciNet  MATH  Google Scholar 

21. Hyttinen, T., Paolini, G., Vȧȧnȧnen, J.: Quantum team logic and bell’s inequalities. Rew. Symb. Logic 8(4), 722–742 (2015)

    Article  MathSciNet  MATH  Google Scholar 

22. Hyttinen, T., Paolini, G., Väänänen, J.: A logic for arguing about probabilities in measure teams. Arch. Math. Log. 56(5), 475–489 (2017)

    Article  MathSciNet  MATH  Google Scholar 

23. Kivinen, J., Mannila, H.: Approximate inference of functional dependencies from relations. Theor. Comput. Sci. 149(1), 129–149 (1995)

    Article  MathSciNet  MATH  Google Scholar 

24. Kolaitis, P.G.: The query containment problem: Set semantics vs. bag semantics. In: Proceedings 7th AMW, volume 1087 of CEUR Workshop Proceedings (2013)

25. Kontinen, J.: Coherence and computational complexity of quantifier-free dependence logic formulas. Studia Logica 101(2), 267–291 (2013)

    Article  MathSciNet  MATH  Google Scholar 

26. Kontinen, J., Kuusisto, A., Lohmann, P., Virtema, J.: Complexity of two-variable dependence logic and if-logic. Inf. Comput. 239, 237–253 (2014)

    Article  MathSciNet  MATH  Google Scholar 

27. Kontinen, J., Kuusisto, A., Virtema, J.: Decidability of Predicate Logics with Team Semantics. In: Faliszewski, P., Muscholl, A., Niedermeier, R. (eds.) 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), volume 58 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 60:1–60:14, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik (2016)

28. Kontinen, J., Link, S., Väänänen, J.A.: Independence in database relations. In: Proceedings 20th WoLLIC, volume 8071 of LNCS, pp. 179–193. Springer (2013)

29. Kontinen, J., Müller, J.-S., Schnoor, H., Vollmer, H.: A Van Benthem Theorem for Modal Team Semantics. In: Proceedings 24th CSL, volume 41 of LIPIcs, pp. 277–291, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik (2015)

30. Krebs, A., Meier, A., Virtema, J.: A team based variant of CTL. In: Proceedings TIME, p 2015 (2015)

31. Lamperti, G., Melchiori, M., Zanella, M.: On multisets in database systems. In: Proceedings WMP, pp. 147–216, London, UK, UK. Springer-Verlag, Berlin (2001)

32. Liu, L., Ȯzsu, T.M. (eds.): Encyclopedia of Database Systems. Springer, US (2009)

    MATH  Google Scholar 

33. Papadimitriou, C.H.: Computational complexity. Addison-Wesley, Boston (1994)

    MATH  Google Scholar 

34. Vȧȧnȧnen, J.: Dependence Logic - A New Approach to Independence Friendly Logic, volume 70 of London Mathematical Society student texts. Cambridge University Press, Cambridge (2007)

    Book  Google Scholar 

35. Väänänen, J.: Modal dependence logic. In: van Rooij, R., Apt, K. (eds.) New Perspectives on Games and Interaction, volume 5 of Texts in Logic and Games, pp. 237–254. Amsterdam University Press (2008)

36. Väänänen, J.: The logic of approximate dependence. In: Başkent, C., Moss, L.S., Ramanujam, R. (eds.) Rohit Parikh on Logic, Language and Society, pp. 227–234. Springer International Publishing, Cham (2017)

37. Michael Wong, S.K.: An extended relational data model for probabilistic reasoning. J. Intell. Inf. Syst. 9(2), 181–202 (1997)

    Article  Google Scholar 

38. Wong, S.K.M., Butz, C.J., Wu, D.: On the implication problem for probabilistic conditional independency. IEEE Trans. Syst. Man Cybern. Syst. Hum. 30(6), 785–805 (2000)

    Article  Google Scholar 

39. Yang, F.: On Extensions and Variants of Dependence Logic – A study of intuitionistic connectives in the team semantics setting. PhD thesis, Department of Mathematics and Statistics. University of Helsinki, Helsinki (2014)

    Google Scholar 

40. Yang, F., Vȧȧnȧnen, J.: Propositional logics of dependence. Ann. Pure Appl. Logic 167(7), 557–589 (2016)

    Article  MathSciNet  MATH  Google Scholar 

Download references