An Ehrenfeucht-Fraïssé game approach to collapse results in database theory

DOI10.1016/j.ic.2006.10.002zbMath1110.68035arXivcs/0212049OpenAlexW1979165044MaRDI QIDQ870360

Nicole Schweikardt

Publication date: 12 March 2007

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0212049

Mathematics Subject Classification ID

Database theory (68P15)

Related Items (1)

On complexity of Ehrenfeucht-Fraïssé games

Cites Work

• Finite model theory and its applications.
• Elements of finite model theory.
• A collapse result for constraint queries over structures of small degree
• Extended order-generic queries
• First-order queries on databases embedded in an infinite structure
• Querying spatial databases via topological invariants
• First-order expressibility of languages with neutral letters or: The Crane Beach conjecture
• An application of games to the completeness problem for formalized theories
• Relational queries over interpreted structures
• Relational expressive power of constraint query languages
• Stability theory, permutations of indiscernibles, and embedded finite models
• On sets of relations definable by addition
• Arithmetic, first-order logic, and counting quantifiers
• Definability of Languages by Generalized First-Order Formulas over (N,+)
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An Ehrenfeucht-Fraïssé game approach to collapse results in database theory