Logic and Database Theory Prof. Dr. Nicole Schweikardt

Logic in Computer Science, Dept. of Computer Science, Humboldt-University Berlin

Invited Papers:

• Machine models and lower bounds for query processing. Nicole Schweikardt. PODS'07: 26th ACM Sigact-Sigart Symposium on Principles of Database Systems, Beijing, China, June 2007. ACM.
  Abstract:  here.   Download:   ps (420 kB)   pdf (247 kB)   slides of my talk at PODS'07 (pdf) (759 kB).
   
• The Complexity of Querying External Memory and Streaming Data. Martin Grohe, Christoph Koch, and Nicole Schweikardt. FCT'05: 15th International Symposium on Fundamentals of Computation Theory, volume 3623 of Lecture Notes in Computer Science, pages 1-16. Lübeck, Germany, August 2005. Springer-Verlag.
  Abstract:  here.   Download:   ps.gz (192 kB)   ps (456 kB)   pdf (213 kB).  
   
• Logik und Informatik. Stephan Kreutzer und Nicole Schweikardt. it - Information Technology, Vol. 46, No. 3, 2004, pages 162-166.
  Abstract:  here.   Download:   pdf (159 kB).  
   
• Die Ausdrucksstärke der Logik erster Stufe mit eingebauten Prädikaten. Nicole Schweikardt. In Ausgezeichnete Informatikdissertationen 2002, Dorothea Wagner et al., editors, volume D-3 of GI-Edition Lecture Notes in Informatics (LNI) - Dissertations, pages 153-162, Gesellschaft für Informatik, 2003. ISBN 3-88579-407-1.
  Abstract:  here.   Download:   pdf (132 kB). 

Journal Papers:

• Tight Lower Bounds for Query Processing on Streaming and External Memory Data. Martin Grohe, Christoph Koch, and Nicole Schweikardt. To appear in Theoretical Computer Science. Special issue for selected papers from ICALP'05, Track B.
  Abstract:  here.   Download:   pdf (314 kB).  
   
• An Ehrenfeucht-Fraïssé Game Approach to Collapse Results in Database Theory. Nicole Schweikardt. Information and Computation, volume 205, issue 3, pages 311-379, 2007.
  Abstract:  here.   Download:   ps.gz (379 kB)   ps (1107 kB)   pdf (697 kB). 
   
• On the expressive power of monadic least fixed point logic. Nicole Schweikardt. Theoretical Computer Science, volume 350, pages 325-344, 2006. Special issue for selected papers from ICALP'04, Track B.
  Abstract:  here.   Download:   ps.gz (164 kB)   ps (404 kB)   pdf (242 kB).
   
• The succinctness of first-order logic on linear orders. Martin Grohe and Nicole Schweikardt. Logical Methods in Computer Science, volume 1 (1:6) 2005, pages 1-25.
  Abstract:  here.   Download here from http://www.lmcs-online.org/.
   
• First-Order Expressibility of Languages with Neutral Letters Or: The Crane Beach Conjecture. David A. Mix Barrington, Neil Immerman, Clemens Lautemann, Nicole Schweikardt and Denis Thérien. Journal of Computer and System Sciences, volume 70, pages 101-127, 2005.
  Abstract:  here.  Download:   ps.gz (260 kB)   ps (626 kB)   pdf (298 kB).
   
• Arithmetic, First-Order Logic, and Counting Quantifiers. Nicole Schweikardt. ACM Transactions on Computational Logic (ACM ToCL), volume 6, issue 3, July 2005, pages 634-671.
  Abstract:  here.   Download:   ps.gz (263 kB)   ps (698 kB)   pdf (384 kB). 
   
• Comparing the succinctness of monadic query languages over finite trees. Martin Grohe and Nicole Schweikardt. RAIRO - Theoretical Informatics and Applications (ITA), volume 38, pages 343-373, 2004.
  Abstract:  here.   Download:   ps.gz (186 kB)   ps (461 kB)   pdf (262 kB). 
   
• The monadic quantifier alternation hierarchy over grids and graphs. Oliver Matz, Nicole Schweikardt, and Wolfgang Thomas. Information and Computation, volume 179, number 2, 2002, pages 356-383. Special issue for selected papers from LICS'97.
  Abstract:  here.   Download:   ps.gz (208 kB)   ps (912 kB)   pdf (553 kB).  

Conference Papers:

• Model theory makes formulas large. Anuj Dawar, Martin Grohe, Stephan Kreutzer, and Nicole Schweikardt. ICALP'07: 34th International Colloquium on Automata, Languages and Programming. Wroclaw, Poland, July 2007. Springer-Verlag.
  Abstract:  here.   Download:   ps (199 kB)   pdf (126 kB).  
   
• Boundedness of Monadic FO over Acyclic Structures. Stephan Kreutzer, Martin Otto, and Nicole Schweikardt. ICALP'07: 34th International Colloquium on Automata, Languages and Programming. Wroclaw, Poland, July 2007. Springer-Verlag.
  Abstract:  here.   Download:   ps (214 kB)   pdf (129 kB).  
   
• CWA-Solutions for Data Exchange Settings with Target Dependencies. André Hernich and Nicole Schweikardt. PODS'07: 26th ACM Sigact-Sigart Symposium on Principles of Database Systems, Beijing, China, June 2007. ACM.
  Abstract:  here.   Download:   ps (692 kB)   pdf (234 kB).  
   
• Database Query Processing Using Finite Cursor Machines. Martin Grohe, Yuri Gurevich, Dirk Leinders, Nicole Schweikardt, Jerzy Tyszkiewicz, Jan Van den Bussche. ICDT'07: 11th International Conference on Database Theory, vol. 4353 of Lecture Notes in Computer Science, pp. 284-298, Barcelona, Spain, January 2007. Springer-Verlag.
  Abstract:  here.   Download:   pdf (447 kB).  
   
• Approximation Schemes for First-Order Definable Optimisation Problems. Anuj Dawar, Martin Grohe, Stephan Kreutzer, and Nicole Schweikardt. LICS'06: 21st Annual IEEE Symposium on Logic in Computer Science, pages 411-420, Seattle, USA, August 2006. IEEE Computer Society.
  Abstract:  here.   Download:   ps (259 kB)   pdf (152 kB).   Full version:   ps (314 kB)   pdf (190 kB).  
   
• Randomized Computations on Large Data Sets: Tight Lower Bounds. Martin Grohe, André Hernich, and Nicole Schweikardt. PODS'06: 25th ACM Sigact-Sigart Symposium on Principles of Database Systems, pages 243-252, Chicago, USA, June 2006. ACM.
  Abstract:  here.   Download:   pdf (208 kB).   Full version:   CoRR Report, arXiv:cs.DB/0703081, March 2007, 29 pages.   Download:   ps (524 kB)   pdf (356 kB).  
   
• The Expressive Power of Two-Variable Least Fixed-Point Logics Martin Grohe, Stephan Kreutzer, and Nicole Schweikardt. MFCS'05: 30th International Symposium on Mathematical Foundations of Computer Science , volume 3618 of Lecture Notes in Computer Science, pages 422-434. Gdansk, Poland, August/September 2005. Springer-Verlag.
  Abstract:  here.   Download:   ps.gz (1192 kB)   ps (449 kB)   pdf (183 kB).  
   
• Tight Lower Bounds for Query Processing on Streaming and External Memory Data. Martin Grohe, Christoph Koch, and Nicole Schweikardt. ICALP'05: 32nd International Colloquium on Automata, Languages and Programming, volume 3580 of Lecture Notes in Computer Science, pages 1076-1088. Lisbon, Portugal, July 2005. Springer-Verlag.
  Abstract:  here.   Download:   pdf (182 kB).   Received the Best Paper Award at ICALP'05, Track B.   Full version:   CoRR Report, arXiv:cs.DB/0505002, 29 April 2005, 25 pages.   Download:   pdf (303 kB).  
   
• Lower Bounds for Sorting with Few Random Accesses to External Memory. Martin Grohe and Nicole Schweikardt. PODS'05: 24th ACM Sigact-Sigart Symposium on Principles of Database Systems, pages 238-249, Baltimore, USA, June 2005. ACM.
  Abstract:  here.   Download:   ps.gz (104 kB)   ps (260 kB)   pdf (164 kB).  
   
• Schema-based Scheduling of Event Processors and Buffer Minimization for Queries on Structured Data Streams. Christoph Koch, Stefanie Scherzinger, Nicole Schweikardt, and Bernhard Stegmaier. VLDB'04: 30th International Conference on Very Large Data Bases, pages 228-239, Toronto, Canada, August/September 2004. Morgan Kaufmann.
  Abstract:  here.   Download:   pdf (220 kB).   Full version: CoRR Report, arXiv:cs.DB/0406016, 07 June 2004, 14 pages.   Errata: here.   Download:   ps (281 kB)  
   
• FluXQuery: An Optimizing XQuery Processor for Streaming XML Data. Christoph Koch, Stefanie Scherzinger, Nicole Schweikardt, and Bernhard Stegmaier. VLDB'04: 30th International Conference on Very Large Data Bases, pages 1309-1312, Toronto, Canada, August/September 2004. Demo Paper, 4 pages. Morgan Kaufmann.
  Abstract:  here.   Download:   pdf (101 kB).  
  
  
• On the expressive power of monadic least fixed point logic. Nicole Schweikardt. ICALP'04: 31st International Colloquium on Automata, Languages and Programming, volume 3142 of Lecture Notes in Computer Science, pages 1123-1135, Turku, Finland, July 2004. Springer-Verlag.
  Abstract:  here.   Download:   ps.gz (119 kB)   ps (284 kB)   pdf (144 kB).   Full version:   ps.gz (177 kB)   ps (433 kB)   pdf (237 kB).  
   
• The succinctness of first-order logic on linear orders. Martin Grohe and Nicole Schweikardt. LICS'04: 19th Annual IEEE Symposium on Logic in Computer Science, pages 438-447, Turku, Finland, July 2004. IEEE Computer Society.
  Abstract:  here.   Download:   ps.gz (120 kB)   ps (162 kB)   pdf (177 kB).   Full version:   ps.gz (147 kB)   ps (380 kB)   pdf (201 kB).  
   
• Comparing the succinctness of monadic query languages over finite trees. Martin Grohe and Nicole Schweikardt. CSL'03: 12th Annual Conference of the European Association for Computer Science Logic, volume 2803 of Lecture Notes in Computer Science, pages 226-240, Vienna, Austria, August 2003. Springer.
  Abstract:  here.   Download:   ps.gz (63 kB)   ps (161 kB)   pdf (177 kB).   Full version: Technical Report EDI-INF-RR-0168, School of Informatics, University of Edinburgh, Scotland, U.K., 2003.
  Download:   ps.gz (745 kB)   ps (1745 kB)   pdf (345 kB).
   
• The natural order-generic collapse for omega-representable databases over the rational and the real ordered group. Nicole Schweikardt. CSL'01: 10th Annual Conference of the European Association for Computer Science Logic, volume 2142 of Lecture Notes in Computer Science, pages 130-144, Paris, France, September 2001. Springer.
  Abstract:  here.   Download:   ps.gz (104 kB)   ps (288 kB)   pdf (235 kB). 
   
• The Crane Beach Conjecture. David A. Mix Barrington, Neil Immerman, Clemens Lautemann, Nicole Schweikardt and Denis Thérien. LICS'01: 16th Annual IEEE Symposium on Logic in Computer Science, pages 187-196, Boston, Massachusetts, USA, June 2001. IEEE Computer Society.
  Abstract:  here.   Download:   ps.gz (126 kB)   ps (538 kB)   pdf (296 kB). 
   
• An Ehrenfeucht-Fraisse approach to collapse results for first-order queries over embedded databases. Clemens Lautemann and Nicole Schweikardt. STACS'01: 18th Annual Symposium on Theoretical Aspects of Computer Science, volume 2010 of Lecture Notes in Computer Science, pages 455-466, Dresden, Germany, February 2001. Springer.
  Abstract:  here.   Download:   ps.gz (86 kB)   ps (225 kB)   pdf (208 kB).  Full version: Technical Report 01/2001, Institut für Informatik, Johannes Gutenberg-Universität Mainz, Germany, 2003.
  Download:   ps.gz (126 kB)   ps (538 kB)   pdf (296 kB).
  
  
• A logical characterisation of linear time on nondeterministic Turing machines. Clemens Lautemann, Nicole Schweikardt, and Thomas Schwentick. STACS'99: 16th Annual Symposium on Theoretical Aspects of Computer Science, volume 1563 of Lecture Notes in Computer Science, pages 143-152, Trier, Germany, March 1999. Springer.
  Abstract:  here.   Download:   ps.gz (98 kB)   ps (437 kB)   pdf (210 kB).   Full version:   ps.gz (126 kB)   ps (538 kB)   pdf (296 kB).
  
  
• The monadic quantifier alternation hierarchy over grids and pictures. Nicole Schweikardt. CSL'97: 6th Annual Conference of the European Association for Computer Science Logic, volume 1414 of Lecture Notes in Computer Science, pages 441-460, Aarhus, Denmark, August 1997. Springer. Selected Papers.
  Abstract:  here.   Download:   ps.gz (155 kB)   ps (577 kB)   pdf (288 kB).   Full version: Preliminary Proceedings of CSL'97, BRICS Notes Series NS-97-1, ISSN 0909-3206, pages 383-398.
  Download:   ps.gz (130 kB)   ps (603 kB)   pdf (308 kB).

Miscellaneous:

• Reversal Complexity Revisited. André Hernich and Nicole Schweikardt. CoRR Report, arXiv:cs.CC/0608036, 7 Aug 2006, 19 pages. Submitted in August 2006.
  Abstract:  here.   Download:   pdf (250 kB).  
   
• On quantifier elimination in weak direct powers. Malika More and Nicole Schweikardt. Technical report, 24 pages. In Patrick Cegielski, editor, JAF 20: Journées sur les Arithmétiques Faibles (Weak Arithmetic Days), Fontainebleau, France, June 2001.
  Abstract:  here.   Download:   ps.gz (117 kB)   ps (315 kB)   pdf (293 kB). 

Theses:

• On the Expressive Power of First-Order Logic with Built-In Predicates. Nicole Schweikardt. Ph.D. thesis, Fachbereich Mathematik und Informatik, Johannes Gutenberg-Universität Mainz, Germany, December 2001, 237 pages. Published at Logos Verlag Berlin, 2002, ISBN 3-8325-0017-0.
  Abstract:  here.   Download:   ps.gz (1214 kB)   ps (2821 kB).  Received the GI-Dissertationspreis 2002.
   
• The monadic second-order quantifier alternation hierarchy over grids and pictures. Nicole Schweikardt. Diplomarbeit (Master's thesis), Institut für Informatik, Johannes Gutenberg-Universität Mainz, Germany, August 1997, 116 pages.
  Abstract:  here.   Download:   ps.gz (420 kB)   ps (1755 kB)   pdf (1359 kB).