Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-27T10:20:34.721Z Has data issue: false hasContentIssue false
  • English
  • Français

CHARACTERIZING DOWNWARDS CLOSED, STRONGLY FIRST-ORDER, RELATIVIZABLE DEPENDENCIES

Published online by Cambridge University Press:  04 March 2019

PIETRO GALLIANI
PIETRO GALLIANI*
Affiliation:
FREE UNIVERSITY OF BOZEN-BOLZANO FACOLTÀ DI SCIENZE E TECNOLOGIE INFORMATICHE PIAZZA DOMENICANI 3, 39100 BOLZANO, ITALYE-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In Team Semantics, a dependency notion is strongly first order if every sentence of the logic obtained by adding the corresponding atoms to First-Order Logic is equivalent to some first-order sentence. In this work it is shown that all nontrivial dependency atoms that are strongly first order, downwards closed, and relativizable (in the sense that the relativizations of the corresponding atoms with respect to some unary predicate are expressible in terms of them) are definable in terms of constancy atoms.

Additionally, it is shown that any strongly first-order dependency is safe for any family of downwards closed dependencies, in the sense that every sentence of the logic obtained by adding to First-Order Logic both the strongly first-order dependency and the downwards closed dependencies is equivalent to some sentence of the logic obtained by adding only the downwards closed dependencies.

Keywords

03C8003C85Team Semantics. Dependence LogicSecond Order Logic
Type
Articles
Information
The Journal of Symbolic Logic , Volume 84 , Issue 3 , September 2019 , pp. 1136 - 1167
Copyright
Copyright © The Association for Symbolic Logic 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Armstrong, W. W., Dependency structures of data base relationships, Proceedings of IFIP World Computer Congress (Rosenfeld, J. L., editor), North-Holland, Amsterdam, 1974, pp. 580–583.Google Scholar
Barbero, F., Some observations about generalized quantifiers in logics of imperfect information, arXiv preprint, 2017, arXiv:1709.07301.Google Scholar
Casanova, M. A., Fagin, R., and Papadimitriou, C. H., Inclusion dependencies and their interaction with functional dependencies, Proceedings of the 1st ACM Sigact-Sigmod Symposium on Principles of Database Systems, PODS ’82, ACM, 1982, New York, NY, USA, pp. 171–176.Google Scholar
Chang, C. C., Some new results in definability. Bulletin of the American Mathematical Society, vol. 70 (1964), no. 6, pp. 808–813.Google Scholar
Chang, C. C. and Keisler, H. J., Model Theory, Studies in Logic and the Foundations of Mathematics, vol. 73, Elsevier, Amsterdam, 1990.Google Scholar
Codd, E. F., Further normalization of the data base relational model, Data Base Systems (Rustin, R., editor), Prentice-Hall, New York, 1972, pp. 33–64.Google Scholar
Durand, A., Ebbing, J., Kontinen, J., and Vollmer, H., Dependence logic with a majority quantifier. Journal of Logic, Language and Information, vol. 24 (2015), no. 3, pp. 289–305.Google Scholar
Durand, A. and Kontinen, J., Hierarchies in dependence logic. ACM Transactions on Computational Logic, vol. 13 (2012), no. 4, pp. 31:1–31:21.Google Scholar
Durand, A., Kontinen, J., and Vollmer, H., Expressivity and complexity of dependence logic, Dependence Logic (Abramsky, S., Kontinen, J., Väänänen, J., and Vollmer, H., editors), Springer, Cham, 2016, pp. 5–32.Google Scholar
Engström, F., Generalized quantifiers in dependence logic. Journal of Logic, Language and Information, vol. 21 (2012), no. 3, pp. 299–324.Google Scholar
Engström, F., Kontinen, J., and Väänänen, J., Dependence logic with generalized quantifiers: Axiomatizations. Journal of Computer and System Sciences, vol. 88 (2017), pp. 90–102.Google Scholar
Fagin, R., Multivalued dependencies and a new normal form for relational databases. ACM Transactions on Database Systems, vol. 2 (1977), pp. 262–278.Google Scholar
Galliani, P., Inclusion and exclusion dependencies in team semantics: On some logics of imperfect information. Annals of Pure and Applied Logic, vol. 163 (2012), no. 1, pp. 68–84.Google Scholar
Galliani, P., The doxastic interpretation of team semantics, Logic Without Borders: Essays on Set Theory, Model Theory, Philosophical Logic and Philosophy of Mathematics (Hirvonen, Å., Kontinen, J., Kossak, R., and Villaveces, A., editors), Ontos Mathematical Logic, vol. 5, Walter de Gruyter, Berlin, 2015, pp. 167–191.Google Scholar
Galliani, P., Upwards closed dependencies in team semantics. Information and Computation, vol. 245 (2015), pp. 124–135.Google Scholar
Galliani, P., On strongly first-order dependencies, Dependence Logic (Abramsky, S., Kontinen, J., Väänänen, J., and Vollmer, H., editors), Springer, Cham, 2016, pp. 53–71.Google Scholar
Galliani, P., Safe Dependency Atoms and Possibility Operators in Team Semantics, Proceedings Ninth International Symposium on Games, Automata, Logics, and Formal Verification, GandALF 2018 (Orlandini, A. and Zimmermann, M., editors), Open Publishing Association, 2018, pp. 58–72.Google Scholar
Galliani, P., Hannula, M., and Kontinen, J., Hierarchies in independence logic, Computer Science Logic 2013 (CSL 2013) (Rocca, S. R. D., editor), Leibniz International Proceedings in Informatics (LIPIcs), vol. 23, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2013, pp. 263–280.Google Scholar
Galliani, P. and Hella, L., Inclusion logic and fixed point logic, Computer Science Logic 2013 (CSL 2013) (Rocca, S. R. D., editor), Leibniz International Proceedings in Informatics (LIPIcs), vol. 23, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2013, pp. 281–295.Google Scholar
Grädel, E. and Väänänen, J., Dependence and independence. Studia Logica, vol. 101 (2013), no. 2, pp. 399–410.Google Scholar
Hannula, M., Axiomatizing first-order consequences in independence logic. Annals of Pure and Applied Logic, vol. 166 (2015), no. 1, pp. 61–91.Google Scholar
Hannula, M., Hierarchies in inclusion logic with lax semantics. ACM Transactions on Computational Logic (TOCL), vol. 19 (2018), no. 3, p. 16.Google Scholar
Hintikka, J., The Principles of Mathematics Revisited, Cambridge University Press, Cambridge, 1996.Google Scholar
Hintikka, J. and Sandu, G., Informational independence as a semantic phenomenon, Logic, Methodology and Philosophy of Science (Fenstad, J. E., Frolov, I. T., and Hilpinen, R., editors), Elsevier, Amsterdam, 1989, pp. 571–589.Google Scholar
Hodges, W., A Shorter Model Theory, Cambridge University Press, Cambridge, 1997.Google Scholar
Hodges, W., Compositional semantics for a language of imperfect information. Journal of the Interest Group in Pure and Applied Logics, vol. 5 (1997), no. 4, pp. 539–563.Google Scholar
Kontinen, J., Coherence and computational complexity of quantifier-free dependence logic formulas. Studia Logica, vol. 101 (2013), no. 2, pp. 267–291.Google Scholar
Kontinen, J., Definability of second order generalized quantifiers. Archive for Mathematical Logic, vol. 49 (2010), no. 3, pp. 379–398.Google Scholar
Kontinen, J., Kuusisto, A., and Virtema, J., Decidability of predicate logics with team semantics, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) (Faliszewski, P., Muscholl, A., and Niedermeier, R., editors), Leibniz International Proceedings in Informatics (LIPIcs), vol. 58, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2016, pp. 60:1–60:14.Google Scholar
Kontinen, J., Link, S., and Väänänen, J., Independence in database relations, Logic, Language, Information, and Computation (Libkin, L., Kohlenbach, U., and de Queiroz, R., editors), Springer, Cham, 2013, pp. 179–193.Google Scholar
Kontinen, J. and Nurmi, V., Team logic and second-order logic. Fundamenta Informaticae, vol. 106 (2011), no. 2–4, pp. 259–272.Google Scholar
Kontinen, J. and Väänänen, J., On definability in dependence logic. Journal of Logic, Language and Information, vol. 3 (2009), no. 18, pp. 317–332.Google Scholar
Kontinen, J. and Väänänen, J., A remark on negation of dependence logic. Notre Dame Journal of Formal Logic, vol. 52 (2011), no. 1, pp. 55–65.Google Scholar
Kontinen, J. and Väänänen, J., Axiomatizing first-order consequences in dependence logic. Annals of Pure and Applied Logic, vol. 164 (2013), no. 11, pp. 1101–1117.Google Scholar
Kuusisto, A., A double team semantics for generalized quantifiers. Journal of Logic, Language and Information, vol. 24 (2015), no. 2, pp. 149–191.Google Scholar
Lück, M., Axiomatizations of team logics. Annals of Pure and Applied Logic, vol. 169 (2018), no. 9, pp. 928–969.Google Scholar
Mann, A. L., Sandu, G., and Sevenster, M., Independence-Friendly Logic: A Game-Theoretic Approach, Cambridge University Press, Cambridge, 2011.Google Scholar
Rönnholm, R., Arity fragments of logics with team semantics, Ph.D. thesis, Tampere University, 2018.Google Scholar
Väänänen, J., Dependence Logic, Cambridge University Press, Cambridge, 2007.Google Scholar
Väänänen, J., Team logic, Interactive Logic. Selected Papers from the 7th Augustus de Morgan Workshop (van Benthem, J., Gabbay, D., and Löwe, B., editors), Amsterdam University Press, Amsterdam, 2007, pp. 281–302.Google Scholar