On the Kolmogorov Expressive Power of Boolean Query Languages.

Jerzy Tyszkiewicz: On the Kolmogorov Expressive Power of Boolean Query Languages. ICDT 1995: 97-110
  author    = {Jerzy Tyszkiewicz},
  editor    = {Georg Gottlob and
               Moshe Y. Vardi},
  title     = {On the Kolmogorov Expressive Power of Boolean Query Languages},
  booktitle = {Database Theory - ICDT'95, 5th International Conference, Prague,
               Czech Republic, January 11-13, 1995, Proceedings},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {893},
  year      = {1995},
  isbn      = {3-540-58907-4},
  pages     = {97-110},
  ee        = {db/conf/icdt/Tyszkiewicz95.html},
  crossref  = {DBLP:conf/icdt/95},
  bibsource = {DBLP,}

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 2 Issue 2, EDBT, ICDT, MFDBS, DASFAA" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX


Serge Abiteboul, Kevin J. Compton, Victor Vianu: Queries Are Easier Than You Thought (Probably). PODS 1992: 23-32 BibTeX
Serge Abiteboul, Allen Van Gelder: Optimizing Active Databases using the Split Technique. ICDT 1992: 171-187 BibTeX
Serge Abiteboul, Victor Vianu: Datalog Extensions for Database Queries and Updates. J. Comput. Syst. Sci. 43(1): 62-124(1991) BibTeX
Serge Abiteboul, Victor Vianu: Generic Computation and Its Complexity. STOC 1991: 209-219 BibTeX
Ashok K. Chandra: Programming Primitives for Database Languages. POPL 1981: 50-62 BibTeX
Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980) BibTeX
Neil Immerman: Languages that Capture Complexity Classes. SIAM J. Comput. 16(4): 760-778(1987) BibTeX
Ming Li, Paul M. B. Vitányi: Kolmogorov Complexity and its Applications. Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A) 1990: 187-254 BibTeX
Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX

Referenced by

  1. Jerzy Tyszkiewicz: Fine Hierarchies of Generic Computation. ICDT 1997: 125-139
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
Lecture Notes in Computer Science: Copyright © by Springer
Digitization of EDBT/ICDT/MFDBS proceedings was supported by the EDBT Endowment.
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:19:07 2009