Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-28T05:36:30.487Z Has data issue: false hasContentIssue false
  • English
  • Français

Towards a characterization of order-invariant queries over tame graphs

Published online by Cambridge University Press:  12 March 2014

Michael Benedikt  and
Luc Segoufin
Michael Benedikt
Affiliation:
University of Oxford, Department of Computer Science, Wolfson Building, Oxford, Ox1 3Qd, UK, E-mail: [email protected]
Luc Segoufin
Affiliation:
Inria, LSV-ENS de Cachan, 61, Avenue du Président Wilson, 94235 Cachan Cedex, France, URL: http://www-rocq.inria.fr/~segoufin
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 74 , Issue 1 , March 2009 , pp. 168 - 186
Copyright
Copyright © Association for Symbolic Logic 2009

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

[1]Open problems in finite model theory, http://www-mgi.informatik.rwth-aachen.de/FMT.Google Scholar
[2]Abiteboul, Serge, Hull, Richard, and Vianu, Victor, Foundations of Databases, Addison-Wesley, 1995.Google Scholar
[3]Beauquier, Daniele and Pin, Jean-Eric, Factors of words, Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), 1989.Google Scholar
[4]Benedikt, Michael and Segoufin, Luc, Regular tree languages definable in FO and FOmod, ACM Transactions of Computational Logic, (2008), to appear.Google Scholar
[5]Chang, C. C. and Keisler, H. Jerome, Model Theory, Elsevier, North-Holland, 1990.Google Scholar
[6]Comon, Hubertet al, Tree automata: Techniques and applications, available at http://tata.gforge.inria.fr/.Google Scholar
[7]Courcelle, Bruno, The monadic second order logic of graphs F. Recognizable sets of finite graphs, Information and Computation, vol. 85 (1990), no. 1, pp. 12–75.CrossRefGoogle Scholar
[8]Courcelle, Bruno, The monadic second order logic of graphs V: On closing the gap between definability and recognizability, Theoretical Computer Science, vol. 80 (1991), no. 2, pp. 153–202.CrossRefGoogle Scholar
[9]Courcelle, Bruno, The monadic second order logic of graphs X: Linear orders, Theoretical Computer Science, vol. 160 (1996), no. 1-2, pp. 87–143.CrossRefGoogle Scholar
[10]Ebbinghaus, Hans-Dieter and Flum, Jörg, Finite Model Theory, Springer-Verlag, 1995.Google Scholar
[11]Ganzow, Tobias and Rubin, Sasha, Order-invariant MSO is stronger than counting MSO in the finite, Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS), 2008, pp. 313–324.Google Scholar
[12]Grohe, Martin and Schwentick, Thomas, Locality of order-invariant first-order queries, ACM Transactions of Computational Logic, vol. 1 (2000), no. 1, pp. 112–130.CrossRefGoogle Scholar
[13]Gurevich, Yuri and Shelah, Saharon, On the strength of the interpretation method, this Journal, vol. 54 (1989), no. 2, pp. 305–323.Google Scholar
[14]Lapoire, Denis, Recognizability equals monadic second-order definability for sets of graphs of bounded tree-width, Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS), 1998.Google Scholar
[15]Libkin, Leonid, Elements of Finite Model Theory, Springer, 2004.CrossRefGoogle Scholar
[16]Niemistö, Hannu, On locality and uniform reduction, Proceedings of the IEEE Conference on Logic in Computer Science (LICS), 2005.Google Scholar
[17]Otto, Martin, Epsilon-logic is more expressive than first-order logic on finite structures, this Journal, vol. 65 (2000), no. 4, pp. 749–757.Google Scholar
[18]Robertson, Neil and Seymour, Paul D., Graph minors III: Planar tree-width, Journal of Combinatorial Theory, Series B, vol. 36 (1984), pp. 49–64.CrossRefGoogle Scholar
[19]Rossman, Benjamin, Successor-invariance in the finite, Proceedings of the IEEE Conference on Logic in Computer Science (LICS), 2003.Google Scholar
[20]Straubing, Howard, Finite Automata, Formal Logic, and Circuit Complexity, Birkhäuser, 1994.CrossRefGoogle Scholar