Lics

IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Fifteenth Annual IEEE Symposium on

Logic in Computer Science (LICS 2000)

Paper: On First-Order Topological Queries (at LICS 2000)

Authors: Martin Grohe Luc Segoufin

Abstract

One important class of spatial database queries is the class of topological queries, i.e. queries invariant under homeomorphisms. We study topological queries expressible in the standard query language on spatial databases, first-order logic with various amounts of arithmetic. Our main technical result is a combinatorial characterization of the expressive power of topological first-order logic on regular spatial databases.

BibTeX

  @InProceedings{GroheSegoufin-OnFirstOrderTopolog,
    author = 	 {Martin Grohe and Luc Segoufin},
    title = 	 {On First-Order Topological Queries},
    booktitle =  {Proceedings of the Fifteenth Annual IEEE Symposium on Logic in Computer Science (LICS 2000)},
    year =	 {2000},
    month =	 {June}, 
    pages =      {349--360},
    location =   {Santa Barbara, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }
   

Last modified: 2018-06-2121:59
Andrzej Murawski