Definability and Descriptive Complexity on Databases of Bounded Tree-Width.

@inproceedings{DBLP:conf/icdt/GroheM99,
  author    = {Martin Grohe and
               Julian Mari{\~n}o},
  editor    = {Catriel Beeri and
               Peter Buneman},
  title     = {Definability and Descriptive Complexity on Databases of Bounded
               Tree-Width},
  booktitle = {Database Theory - ICDT '99, 7th International Conference, Jerusalem,
               Israel, January 10-12, 1999, Proceedings},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {1540},
  year      = {1999},
  isbn      = {3-540-65452-6},
  pages     = {70-82},
  ee        = {db/conf/icdt/GroheM99.html, http://link.springer.de/link/service/series/0558/bibs/1540/15400070.htm},
  crossref  = {DBLP:conf/icdt/99},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Online Edition: Springer LINK

References

[1]

Serge Abiteboul, Victor Vianu: Fixpoint Extensions of First-Order Logic and Datalog-Like Languages. LICS 1989: 71-79 BibTeX

[2]

...

[3]

Hans L. Bodlaender: NC-Algorithms for Graphs with Small Treewidth. WG 1988: 1-10 BibTeX

[4]

Hans L. Bodlaender: Polynomial Algorithms for Graph Isomorphism and Chromatic Index on Partial k-Trees. J. Algorithms 11(4): 631-643(1990) BibTeX

[5]

Hans L. Bodlaender: Treewidth: Algorithmoc Techniques and Results. MFCS 1997: 19-36 BibTeX

[6]

...

[7]

Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) BibTeX

[8]

Bruno Courcelle: Graph Rewriting: An Algebraic and Logic Approach. Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B) 1990: 193-242 BibTeX

[9]

...

[10]

Tomás Feder, Moshe Y. Vardi: Monotone monadic SNP and constraint satisfaction. STOC 1993: 612-622 BibTeX

[11]

...

[12]

Erich Grädel, Martin Otto: Inductive Definability with Counting on Finite Structures. CSL 1992: 231-247 BibTeX

[13]

...

[14]

Martin Grohe: Fixed-Point Logics on Planar Graphs. LICS 1998: 6-15 BibTeX

[15]

...

[16]

Neil Immerman: Relational Queries Computable in Polynomial Time. Information and Control 68(1-3): 86-104(1986) BibTeX

[17]

...

[18]

...

[19]

...

[20]

Neil Robertson, Paul D. Seymour: Graph Minors. II. Algorithmic Aspects of Tree-Width. J. Algorithms 7(3): 309-322(1986) BibTeX

[21]

...

[22]

...

[23]

...

[24]

Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX