×

Towards a characterization of order-invariant queries over tame graphs. (English) Zbl 1161.03018

Summary: This work deals with the expressive power of logics on finite graphs with access to an additional “arbitrary” linear order. The queries that can be expressed this way are the order-invariant queries for the logic. For the standard logics used in computer science, such as first-order logic, it is known that access to an arbitrary linear order increases the expressiveness of the logic. However, when we look at the separating examples, we find that they have satisfying models whose Gaifman graph is complex – unbounded in valence and in treewidth. We thus explore the expressiveness of order-invariant queries over well-behaved graphs. We prove that first-order order-invariant queries over strings and trees have no additional expressiveness over first-order logic in the original signature. We also prove new upper bounds on order-invariant queries over bounded treewidth and bounded valence graphs. Our results make use of a new technique of independent interest: the application of algebraic characterizations of definability to show collapse results.

MSC:

03C13 Model theory of finite structures
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Finite Automata, Formal Logic, and Circuit Complexity (1994) · Zbl 0816.68086
[2] Finite Model Theory (1995)
[3] DOI: 10.1016/0304-3975(91)90387-H · Zbl 0754.68065
[4] DOI: 10.1016/0890-5401(90)90043-H · Zbl 0722.03008
[5] Model Theory (1990)
[6] ACM Transactions of Computational Logic (2008)
[7] Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP) (1989)
[8] Foundations of Databases (1995) · Zbl 0842.68022
[9] Proceedings of the IEEE Conference on Logic in Computer Science (LICS) (2003)
[10] DOI: 10.1016/0095-8956(84)90013-3 · Zbl 0548.05025
[11] Epsilon-logic is more expressive than first-order logic on finite structures 65 pp 749– (2000) · Zbl 0994.03028
[12] Proceedings of the IEEE Conference on Logic in Computer Science (LICS) (2005)
[13] Elements of Finite Model Theory (2004)
[14] Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS) (1998)
[15] On the strength of the interpretation method 54 pp 305– (1989) · Zbl 0699.03031
[16] DOI: 10.1145/343369.343386 · Zbl 1365.68204
[17] Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS) pp 313– (2008)
[18] DOI: 10.1016/0304-3975(95)00083-6 · Zbl 0877.68087
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.