Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-26T08:25:36.545Z Has data issue: false hasContentIssue false
  • English
  • Français

DEPENDENCE LOGIC IN PREGEOMETRIES AND ω-STABLE THEORIES

Published online by Cambridge University Press:  09 March 2016

GIANLUCA PAOLINI  and
JOUKO VÄÄNÄNEN
GIANLUCA PAOLINI
Affiliation:
DEPARTMENT OF MATHEMATICS AND STATISTICS UNIVERSITY OF HELSINKI FINLANDE-mail: [email protected]: http://www.mv.helsinki.fi/home/gianpaol/homepage.html
JOUKO VÄÄNÄNEN
Affiliation:
DEPARTMENT OF MATHETMATICS AND STATISTICS UNIVERSITY OF HELSINKIFINLAND INSTITUTE FOR LOGIC, LANGUAGE AND COMPUTATION UNIVERSITY OF AMSTERDAM THE NETHERLANDSE-mail:[email protected]: http://www.math.helsinki.fi/logic/people/jouko.vaananen/
Get access Rights & Permissions [Opens in a new window]

Abstract

We present a framework for studying the concept of independence in a general context covering database theory, algebra and model theory as special cases. We show that well-known axioms and rules of independence for making inferences concerning basic atomic independence statements are complete with respect to a variety of semantics. Our results show that the uses of independence concepts in as different areas as database theory, algebra, and model theory, can be completely characterized by the same axioms. We also consider concepts related to independence, such as dependence.

Keywords

independencedependencestability theorymatroid
Type
Articles
Information
The Journal of Symbolic Logic , Volume 81 , Issue 1 , March 2016 , pp. 32 - 55
Copyright
Copyright © The Association for Symbolic Logic 2016 

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

Abiteboul, SergeHill, Richard and Vianu, Victor, Foundations of Databases, Addison-Wesley, Amsterdam, 1995.Google Scholar
Ward Armstrong, William, Dependency Structures of Database Relationships, IFIP Congress, pp. 580–583, 1974.Google Scholar
Baldwin, John T., First-order Theories of Abstract Dependence Relations. Annals of Pure and Applied Logic, vol. 26 (1984), no. 3, pp. 215–243.Google Scholar
Crapo, Henry H. and Rota, Giancarlo, On the Foundations of Combinatorial Theory: Combinatorial Geometries, M.I.T. Press, Cambridge, MA, 1970.Google Scholar
Dawid, A. P., Separoids: A mathematical framework for conditional independence and irrelevance. Annals of Mathematics and Artificial Intelligence, vol. 32 (2001), no. 1–4, pp. 335–372.Google Scholar
Galliani, Pietro and Väänänen, Jouko, On Dependence Logic, Trends in Logic: Outstanding Contributions (Baltag, A. and Smets, S., editor), pp. 101–109, Springer, Berlin, 2014.Google Scholar
Geiger, Dan, Paz, Azaria, and Pearl, Judea, Axioms and Algorithms for Inferences Involving Probabilistic Independence. Information and Computation, vol. 91 (1991), no. 1, pp. 128–141.Google Scholar
Grädel, Erich and Väänänen, Jouko, Dependence and Independence. Studia Logica, vol. 101 (2013), no. 2, pp. 399–410.Google Scholar
Grossberg, Rami and Lessmann, Olivier, Dependence Relation in Pregeometries. Algebra Universalis, vol. 44 (2000), pp. 199–216.Google Scholar
Herrmann, Christian, On the Undecidability of Implications between Embedded Multivalued Database Dependencies. Information and Computation, vol. 122 (1995), no. 2, pp. 221–235.Google Scholar
Herrmann, Christian, Corrigendum to “On the Undecidability of Implications between Embedded Multivalued Database Dependencies” [Inform. and Comput. 122 (1995) 221–235]. Information and Computation, vol. 204 (2006), no. 12, pp. 1847–1851.Google Scholar
Hyttinen, Tapani and Paolini, Gianluca, Reduction of Database Independence to Dividing in Atomless Boolean Algebras. to appear.Google Scholar
Kontinen, Juha, Link, Sebastian, and Väänänen, Jouko, Independence in Database Relations. WoLLIC 2013, (Libkin, L., Kohlenbach, U., and de Queiroz, R., editors), Lecture Notes in Computer Science, vol. 8071, pp. 179–193, 2013.Google Scholar
Kontinen, Juha and Väänänen, Jouko, On definability in dependence logic. Journal of Logic, Language and Information, vol. 18 (2009), no. 3, pp. 317–332.Google Scholar
Marker, David, Introduction to Model Theory, Springer, Berlin, 2002.Google Scholar
Milne, James S., Fields and Galois Theory, 2008, (v4.21) available at www.jmilne.org/math/.Google Scholar
Naumov, Pavel and Nicholls, Brittany, R.E. Axiomatization of Conditional Independence, 2013, available at http://www2.mcdaniel.edu/pnaumov/papers/2013.tark.nn.pdf.Google Scholar
Paolini, Gianluca, Independence Logic and Abstract Independence Relations. Mathematical Logic Quarterly, to appear.Google Scholar
Parker, D. Stott Jr. and Parsaye-Ghomi, Kamran, Inferences Involving Embedded Multivalued Dependencies and Transitive Dependencies, Proceedings of the 1980 ACM SIGMOD international conference on Management of data, SIGMOD ’80, pp. 52–57, ACM, New York, NY, USA, 1980.Google Scholar
Pillay, Anand, Geometric Stability Theory, Oxford University Press, Oxford, 1996.Google Scholar
Väänänen, Jouko, Dependence Logic, London Mathematical Society Student Texts, vol. 70, Cambridge University Press, Cambridge, 2007.Google Scholar
van der Waerden, Bartel Leendert, Moderne Algebra, Springer, Berlin, 1940.CrossRefGoogle Scholar
Whitney, Hassler, On the Abstract Properties of Linear Dependence. American Journal of Mathematics, vol. 57 (1935), no. 3, pp. 509–533.CrossRefGoogle Scholar