Forschungsschwerpunkte
Das Interesse der Arbeitsgruppe "Theorie komplexer Systeme" gilt der theoretischen Informatik mit Schwerpunkten in den Bereichen Komplexitätstheorie, Logik und Datenbanktheorie. Besonderes Augenmerk wird hierbei auf die Verbindungen zwischen diesen Gebieten gelegt. Beispielsweise fungieren Logiken u.a. als Basis für Datenbankanfragesprachen und als Spezifikationssprachen, die im Bereich der Verifikation verwendet werden. Viele Aspekte komplexer Systeme lassen sich auf natürliche Weise durch logische Strukturen modellieren, so dass Eigenschaften komplexer Systeme durch logische Formeln beschrieben werden können.
Generelles Ziel der Arbeit der AG TKS ist, die Komplexität, die Problemen oder Systemen innewohnt, besser zu verstehen. Dabei interessieren uns die unterschiedlichsten Maße für Komplexität, darunter verschiedene Maße für die Berechnungskomplexität (Frage: Wie schwer ist es, das Problem algorithmisch zu lösen?) sowie für die Beschreibungskomplexität (Frage: Wie schwer ist es, das Problem in einem geeigneten Formalismus zu beschreiben?). Hierbei geht es u.a. darum, den Zusammenhang zwischen logischer Beschreibbarkeit und effizienter algorithmischer Lösbarkeit zu ergründen.
Ein Schwerpunkt der Arbeitsgruppe liegt in der Untersuchung der Ausdrucksstärke und Komplexität unterschiedlicher Logiken. Ein weiterer Schwerpunkt ist die Erforschung der Komplexität der Verarbeitung von großen Datenmengen und Datenströmen. Hierbei geht es uns insbesondere um die Entwicklung von Berechnungsmodellen, die den durch Speicherzugriffe verursachten Aufwand klassifizieren, um den Nachweis unterer Schranken, sowie um die Entwicklung effizienter Algorithmen zur Verarbeitung von großen Datenmengen und Datenströmen.
Publikationen von Mitgliedern der AG TKS
Nach Kategorien ordnen2015

R. Chitnis, G. Cormode, M. Hajiaghayi, and M. Monemizadeh,
Parameterized streaming: Maximal matching and vertex cover,
SODA 2015, 2015.

H. Esfandiari, M. Hajiaghayi, V. Liaghat, M. Monemizadeh, and K. Onak,
Streaming algorithms for estimating the matching size in planar graphs and beyond,
SODA 2015, 2015.
2014

S. Kreutzer and N. Schweikardt,
On Hanfequivalence and the number of embeddings of small induced subgraphs,
in Proc. of the 23thrd EACSL Annual Conference on Computer Science Logic (CSL'14) and the 29th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'14), 2014.

D. D. Freydenberger and T. Kötzing,
Fast learning of restricted regular expressions and DTDs,
Theory of Computing Systems, 2014. Special Issue ICDT 2013.

F. Harwath, L. Heimberg, and N. Schweikardt,
Preservation and Decomposition Theorems for Bounded Degree Structures,
in Proc. of the 23thrd EACSL Annual Conference on Computer Science Logic (CSL'14) and the 29th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'14), 2014.

A. Frochaux, M. Grohe, and N. Schweikardt,
Monadic datalog containment on trees,
in AMW 2014: Proceedings of the 8th Alberto Mendelzon Workshop on Foundations of Data Management, Cartagena de Indias, Colombia, June 46, 2014 (G. Gottlob and J. Pérez, eds.), vol. 1189 of CEUR Workshop Proceedings, CEURWS.org, 2014.PDF Slides

K. Eickmeyer, M. Elberfeld, and F. Harwath,
Expressivity and succinctness of orderinvariant logics on depthbounded structures,
2014. (accepted for MFCS 2014).

N. Schweikardt, V. Christophides, and V. Leroy, eds., Proceedings of the
17th International Conference on Database Theory (ICDT 2014), Athens, Greece,
March 2428, 2014, OpenProceedings.org, 2014.

K. S. Candan, S. AmerYahia, N. Schweikardt, V. Christophides, and V. Leroy,
eds., Proceedings of the Workshops of the EDBT/ICDT 2014 Joint
Conference (EDBT/ICDT 2014), no. 1133 in CEUR Workshop Proceedings,
(Aachen), 2014.

A. Durand, N. Schweikardt, and L. Segoufin,
Enumerating Answers to FirstOrder Queries over Databases of Low Degree,
in PODS'14: 33th ACM SIGMOD/PODS Symposium on Principles of Database Systems, (Snowbird, USA), 2014.
2013

J. Keppeler,
Erreichbarkeit ist für gerichtete Graphen schwerer als für ungerichtete Graphen,
Bachelorarbeit, GoetheUniversität Frankfurt am Main, 2013.

A. Frochaux and N. Schweikardt,
A note on monadic datalog on unranked trees,
CoRR, vol. abs/1310.1316, 2013.

E. Ikonomovska and M. Zelke,
Algorithmic techniques for processing data streams,
in Data Exchange, Integration, and Streams (P. G. Kolaitis, M. Lenzerini, and N. Schweikardt, eds.), vol. 5 of Dagstuhl FollowUps, pp. 237–274, Schloss Dagstuhl  LeibnizZentrum fuer Informatik, 2013.

P. G. Kolaitis, M. Lenzerini, and N. Schweikardt, eds., Data Exchange,
Integration, and Streams, vol. 5 of Dagstuhl FollowUps.
Schloss Dagstuhl  LeibnizZentrum fuer Informatik, 2013.

F. Harwath and N. Schweikardt,
On the locality of arbinvariant firstorder logic with modulo counting quantifiers,
in Computer Science Logic 2013 (CSL 2013), CSL 2013, vol. 23 of LIPIcs, pp. 363–379, Schloss Dagstuhl  LeibnizZentrum fuer Informatik, 2013.PDF SlidesPDF Full version

L. Heimberg, D. Kuske, and N. Schweikardt,
An optimal Gaifman normal form construction for structures of bounded degree,
in Proc. 28th IEEE Symposium on Logic in Computer Science (LICS'13), 2013.PDF Full version of LICS 2013 paper

N. Schweikardt,
A short tutorial on orderinvariant firstorder logic,
in Proc. 8th International Computer Science Symposium in Russia (CSR'13), 2013. To appear in Springer LNCS.

A. Czumaj, C. Lammersen, M. Monemizadeh, and C. Sohler,
(1 + ε)Approximation for Facility Location in Data Streams,
in Proceedings of the 24th Annual ACMSIAM Symposium on Discrete Algorithms (SODA'2013), pp. 1710–1728, 2013.

D. D. Freydenberger and T. Kötzing,
Fast learning of restricted regular expressions and DTDs,
in Proc. 16th International Conference on Database Theory, ICDT 2013, pp. 45–56, 2013.

D. D. Freydenberger and D. Reidenbach,
Inferring descriptive generalisations of formal languages,
Journal of Computer and System Sciences, vol. 79, pp. 622–639, 2013.

D. D. Freydenberger and N. Schweikardt,
Expressiveness and static analysis of extended conjunctive regular path queries,
Journal of Computer and System Sciences, vol. 79, pp. 892–909, 2013. Special Issue on Foundations of Data Management.

D. D. Freydenberger,
Extended regular expressions: Succinctness and decidability,
Theory of Computing Systems, vol. 53, pp. 159–193, 2013. Special Issue STACS 2011.
2012

C. Burschka,
Die Nutzung von Schaltkreisschranken zum Nachweis von Lokalitätseigenschaften von Logiken,
Bachelorarbeit, GoetheUniversität Frankfurt am Main, 2012.

J. Bremer and D. D. Freydenberger,
Inclusion problems for patterns with a bounded number of variables,
Information and Computation, vol. 220–221, pp. 15–43, 2012.PDF Preprint

L. Heimberg,
GaifmanNormalformen auf Strukturklassen beschränkten Grades,
Diplomarbeit, Institut für Informatik, HumboldtUniversität zu Berlin, July 2012.

D. D. Freydenberger, H. Nevisi, and D. Reidenbach,
Weakly unambiguous morphisms,
Theoretical Computer Science, vol. 448, pp. 21–40, 2012.

M. Anderson, D. van Melkebeek, N. Schweikardt, and L. Segoufin,
Locality from circuit lower bounds,
SIAM Journal on Computing, no. 41, pp. 1481–1523, 2012.

M. Zelke,
Weighted matching in the semistreaming model,
Algorithmica, vol. 62, no. 12, pp. 1–20, 2012.

F. Harwath and N. Schweikardt,
Regular tree languages, cardinality predicates, and additioninvariant FO,
in STACS 2012 : 29th International Symposium on Theoretical Aspects of Computer Science (C. Dürr and T. Wilke, eds.), vol. 14 of LIPIcs, Schloss Dagstuhl  LeibnizZentrum fuer Informatik, 2012.PDF Slides
2011

G. Rieger,
Analyse und Vergleich der Performanz von DatenstromAlgorithmen und konventionellen Algorithmen anhand verschiedener Anwendungsszenarien,
Diplomarbeit, GoetheUniversität Frankfurt, 2011.

P. G. Kolaitis, M. Lenzerini, and N. Schweikardt,
Report on DEIS'10: advanced school on data exchange, information, and streams (A GIDagstuhl seminar),
SIGMOD Record, vol. 40, no. 1, pp. 40–42, 2011.

N. Schweikardt and T. Schwentick,
A note on the expressive power of linear orders,
Logical Methods in Computer Science, vol. 7, no. 4, 2011.

D. D. Freydenberger,
Inclusion of pattern languages and related problems,
PhD thesis, Institut für Informatik, GoetheUniversität Frankfurt am Main, 2011.

A. Czumaj, M. Monemizadeh, C. Sohler, and K. Onak,
Planar graphs: Random walks and bipartiteness testing,
in Proceedings of 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011), 2011.

M. Anderson, D. van Melkebeek, N. Schweikardt, and L. Segoufin,
Locality of queries definable in invariant firstorder logic with arbitrary builtin predicates,
in Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP 2011), vol. 6756 of Lecture Notes in Computer Science, pp. 368–379, Springer, 2011. Abstract

D. D. Freydenberger and N. Schweikardt,
Expressiveness and static analysis of extended conjunctive regular path queries,
in Proc. 5th Alberto Mendelzon International Workshop on Foundations of Data Management, AMW 2011, vol. 749 of CEUR Workshop Proceedings, CEURWS.org, 2011. Abstract

A. Hernich, L. Libkin, and N. Schweikardt,
Closed world data exchange,
ACM Transactions on Database Systems, vol. 36, no. 2, 2011. Abstract

M. Zelke,
Intractability of min and maxcut in streaming graphs,
Information Processing Letters, vol. 111, no. 3, pp. 145–150, 2011.

D. D. Freydenberger, H. Nevisi, and D. Reidenbach,
Weakly unambiguous morphisms,
in Proc. 28th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2011, 2011.

D. D. Freydenberger,
Extended regular expressions: Succinctness and decidability,
in Proc. 28th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2011, 2011.PDF Full version

E. D. Demaine, S. P. Fekete, G. Rote, N. Schweer, D. Schymura, and M. Zelke,
Integer point sets minimizing average pairwise ℓ1 distance: What is the optimal shape of a town?,
Computational Geometry: Theory and Applications, vol. 44, pp. 82–94, 2011.
2010

F. Harwath,
Entscheidbare Charakterisierungen von Erweiterungen der Logik erster Stufe über Bäumen,
Masterarbeit, Institut für Informatik, Goethe Universität, Frankfurt am Main, Germany, November 2010.

J. Bremer,
Inklusionsprobleme für nichtlöschenden Patternsprachen,
Diplomarbeit, Institut für Informatik, GoetheUniversität Frankfurt am Main, 2010. In German.

M. Monemizadeh,
Nonuniform sampling in clustering and streaming,
2010.

A. Hernich,
Foundations of query answering in relational data exchange,
PhD thesis, Institut für Informatik, GoetheUniversität Frankfurt am Main, 2010. Abstract

L. Heimberg,
Untere Schranken für GaifmanNormalformen und die Theorie endlicher Bäume,
Studienarbeit, HumboldtUniversität zu Berlin, 2010.

H. Björklund, W. Martens, N. Schweikardt, and T. Schwentick,
Logik und Automaten: ein echtes Dreamteam,
InformatikSpektrum, vol. 33(5), pp. 452–461, 2010. [ DOI  http ] Abstract

D. D. Freydenberger and D. Reidenbach,
Existence and nonexistence of descriptive patterns,
Theoretical Computer Science, vol. 411, no. 3436, pp. 3274 – 3286, 2010.Link Preprint

D. D. Freydenberger and D. Reidenbach,
Bad news on decision problems for patterns,
Information and Computation, vol. 208, no. 1, pp. 83–96, 2010.Link Preprint

D. D. Freydenberger and D. Reidenbach,
Inferring descriptive generalisations of formal languages,
in Proc. 23rd Annual Conference on Learning Theory, COLT 2010, pp. 194–206, 2010.

J. Bremer and D. D. Freydenberger,
Inclusion problems for patterns with a bounded number of variables,
in Proc. 14th International Conference on Developments in Language Theory, DLT 2010, vol. 6224 of LNCS, pp. 100–111, 2010. Best paper award.PreprintPDF Full version

M. Monemizadeh and D. Woodruff,
1pass relativeerror lpsampling with applications,
in SODA, 2010.

D. Feldman, M. Monemizadeh, C. Sohler, and D. Woodruff,
Coresets and sketches for high dimensional subspace problems,
in SODA, 2010.

N. Schweikardt and L. Segoufin,
Additioninvariant FO and regularity,
in Proceedings of the 25th IEEE Symposium on Logic in Computer Science (LICS 2010), (Edinburgh, Scotland, U.K.), pp. 285–294, IEEE Computer Society, July 2010. AbstractPDF Full version of LICS 2010 paper

A. Hernich,
Answering nonmonotonic queries in relational data exchange,
in ICDT 2010: 13th International Conference on Database Theory, pp. 143–154, ACM, Mar. 2010. Received one of the two ICDT 2010 Best Student Paper Awards.

S. Hougardy, F. H. Lutz, and M. Zelke,
Surface realization with the intersection segment functional,
Exp. Mathematics, vol. 19, no. 1, pp. 79–92, 2010.

A. Hernich and N. Schweikardt,
Logic and data exchange: Which solutions are ”good” solutions?,
in Logic and the Foundations of Game and Decision Theory  LOFT 8 (G. Bonanno, B. Löwe, and W. van der Hoek, eds.), vol. 6006 of Lecture Notes in Computer Science, pp. 61–85, SpringerVerlag, 2010. Abstract
2009

N. Schweikardt, T. Schwentick, and L. Segoufin,
Database theory: Query languages,
in Algorithms and Theory of Computation Handbook (M. J. Atallah and M. Blanton, eds.), vol. 2: Special Topics and Techniques, ch. 19, CRC Press, second ed., Nov 2009. Abstract

S. Hougardy, S. Kirchner, and M. Zelke,
Zuschauer beim BerlinMarathon,
in Besser als Mathe: Moderne angewandte Mathematik aus dem MATHEON zum Mitmachen (K. Biermann, M. Grötschel, and B. LutzWestphal, eds.), pp. 62–67, Vieweg Verlag, 2009.

D. D. Freydenberger and D. Reidenbach,
The unambiguity of segmented morphisms,
Discrete Applied Mathematics, vol. 157, no. 14, pp. 3055–3068, 2009.Link Preprint

D. D. Freydenberger and D. Reidenbach,
Existence and nonexistence of descriptive patterns,
in Proc. 13th Conference on Developments in Language Theory, DLT 2009, vol. 5583 of LNCS, pp. 228–239, 2009.Link Preprint

D. Sabel, M. SchmidtSchauß, and F. Harwath,
Reasoning about contextual equivalence: From untyped to polymorphically typed calculi,
in INFORMATIK 2009, Im Focus das Leben, Beiträge der 39. Jahrestagung der Gesellschaft für Informatik e.V. (GI), 28.9  2.10.2009 in Lübeck (S. Fischer, E. Maehle, and R. Reischuk, eds.), vol. 154 of GI Edition  Lecture Notes in Informatics, pp. 369; 2931–45, October 2009. (4. Arbeitstagung Programmiersprachen (ATPS)).

A. Böhm,
mDatalog  Monadisches Datalog über Bäumen,
Diplomarbeit, Department of Computer Science, HumboldtUniversity Berlin/Germany, June 2009. DE, Available online at http://www.tks.informatik.unifrankfurt.de/aboehm/files/diplom.pdf.

E. D. Demaine, S. P. Fekete, G. Rote, N. Schweer, D. Schymura, and M. Zelke,
Integer point sets minimizing average pairwise ℓ1 distance: What is the optimal shape of a town?,
in Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG2009), pp. 145–148, 2009.

M. Zelke,
Algorithms for streaming graphs,
PhD thesis, MathematischNaturwissenschaftliche Fakultät II, HumboldtUniversität zu Berlin, 2009. Published at Südwestdeutscher Verlag für Hochschulschriften, 2009, ISBN 9783838108063.

N. Schweikardt,
Shortentry on zeroone laws,
in Encyclopedia of Database Systems (L. Liu and M. T. Öszu, eds.), p. 3683, SpringerVerlag, 2009. Abstract

N. Schweikardt,
Shortentry on onepass algorithms,
in Encyclopedia of Database Systems (L. Liu and M. T. Öszu, eds.), pp. 1948–1949, SpringerVerlag, 2009. Abstract

N. Schweikardt,
Shortentry on EhrenfeuchtFraïssé games,
in Encyclopedia of Database Systems (L. Liu and M. T. Öszu, eds.), pp. 963–964, SpringerVerlag, 2009. Abstract

N. Schweikardt,
Machine models for query processing,
in Sigmod Record, vol. 38(2), June 2009. Abstract

N. Schweikardt,
Lower bounds for multipass processing of multiple data streams,
in STACS'09: 26th International Symposium on Theoretical Aspects of Computer Science, (Freiburg, Germany), pp. 51–61, 2009. Abstract

M. Grohe, Y. Gurevich, D. Leinders, N. Schweikardt, J. Tyszkiewicz, and J. V.
den Bussche,
Database query processing using finite cursor machines,
in Theory of Computing Systems, vol. 44(4), pp. 533–560, 2009. Special issue for selected papers from ICDT'07. (Link to the journal). Abstract

M. Grohe, A. Hernich, and N. Schweikardt,
Lower bounds for processing data with few random accesses to external memory,
in Journal of the ACM, vol. 56(3), pp. 1–58, 2009. Special issue for selected papers from PODS'06. Abstract
2008

A. Böhm,
Ausdrucksstärke von monadischem Datalog über Baumstrukturen,
Studienarbeit, HumboldtUniversität zu Berlin, 2008.

D. D. Freydenberger and D. Reidenbach,
Bad news on decision problems for patterns,
in Proc. 12th International Conference on Developments in Language Theory, DLT 2008, vol. 5257 of LNCS, pp. 327–338, 2008.Link Preprint

O. Matz and N. Schweikardt,
Expressive power of monadic logics on words, trees, pictures and graphs,
in Logic and Automata: History and Perspectives (J. Flum, E. Grädel, and T. Wilke, eds.), Texts in Logic and Games, pp. 531–552, Amsterdam University Press, 2008. Abstract

S. Hougardy, F. H. Lutz, and M. Zelke,
Polyhedral tori with minimal integer coordinates,
Electronic Geometry Models, 2008.10.001, 2008.

M. Zelke,
Weighted Matching in the SemiStreaming Model,
in 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008) (S. Albers and P. Weil, eds.), pp. 669–680, 2008.

A. Hernich and N. Schweikardt,
Reversal complexity revisited,
in Theoretical Computer Science, vol. 401(13), pp. 191–205, 2008. Abstract
2007

M. Grohe, Y. Gurevich, D. Leinders, N. Schweikardt, J. Tyszkiewicz, and J. V.
den Bussche,
Database query processing using finite cursor machines,
in ICDT'07: 11th International Conference on Database Theory, pp. 284–298, 2007.

D. D. Freydenberger and D. Reidenbach,
The unambiguity of segmented morphisms,
in Proc. 11th International Conference on Developments in Language Theory, DLT 2007, vol. 4588 of LNCS, pp. 181–192, 2007.Link Preprint

D. Feldman, M. Monemizadeh, and C. Sohler,
A ptas for kmeans clustering based on weak coresets,
Proc. 23st Annu. ACM Sympos. Comput. Geom. (SOCG), pp. 11–18, 2007.

S. Hougardy, F. H. Lutz, and M. Zelke,
Polyhedra of genus 3 with 10 vertices and minimal coordinates,
Electronic Geometry Models, 2006.02.001, 2007.

S. Hougardy, F. H. Lutz, and M. Zelke,
Polyhedra of genus 2 with 10 vertices and minimal coordinates,
Electronic Geometry Models, 2005.08.001, 2007.

M. Zelke,
Optimal peredge processing times in the semistreaming model,
Inf. Process. Lett., vol. 104, no. 3, pp. 106–112, 2007.

N. Schweikardt,
An EhrenfeuchtFraïssé game approach to collapse results in database theory,
in Information and Computation, vol. 205(3), pp. 311–379, 2007. Abstract

S. Kreutzer, M. Otto, and N. Schweikardt,
Boundedness of monadic FO over acyclic structures,
in ICALP'07: 34th International Colloquium on Automata, Languages and Programming, vol. 4596 of Lecture Notes in Computer Science, (Wroclaw, Poland), pp. 571–582, SpringerVerlag, July 2007. Abstract

N. Schweikardt,
Machine models and lower bounds for query processing,
in PODS'07: 26th ACM SIGACTSIGMODSIGART Symposium on Principles of Database Systems, (Beijing, China), pp. 41–52, ACM, June 2007. AbstractPDF Slides of my talk at PODS'07

A. Dawar, M. Grohe, S. Kreutzer, and N. Schweikardt,
Model theory makes formulas large,
in ICALP'07: 34th International Colloquium on Automata, Languages and Programming, vol. 4596 of Lecture Notes in Computer Science, (Wroclaw, Poland), pp. 1076–1088, SpringerVerlag, July 2007. AbstractPDF Full version. Preprint NI07003LAA, Isaac Newton Institute of Mathematical Sciences (2007).

A. Hernich and N. Schweikardt,
CWAsolutions for data exchange settings with target dependencies,
in PODS'07: 26th ACM SIGACTSIGMODSIGART Symposium on Principles of Database Systems, (Beijing, China), pp. 113–122, ACM, June 2007. Abstract

M. Grohe, C. Koch, and N. Schweikardt,
Tight lower bounds for query processing on streaming and external memory data,
Theoretical Computer Science, vol. 380(12), pp. 199–217, 2007. Special issue for selected papers from ICALP'05. Abstract
2006

D. D. Freydenberger,
Wortkombinatorische Überlegungen zu Patternsprachen,
Diplomarbeit, TU Kaiserslautern, 2006. In German.

D. D. Freydenberger, D. Reidenbach, and J. C. Schneider,
Unambiguous morphic images of strings,
International Journal of Foundations of Computer Science, vol. 17, pp. 601–628, 2006. Special Issue DLT 2005.Link Preprint

M. Zelke,
kConnectivity in the SemiStreaming Model,
2006.

M. Grohe, A. Hernich, and N. Schweikardt,
Randomized computations on large data sets: Tight lower bounds,
in PODS'06: 25th ACM SIGACTSIGMODSIGART Symposium on Principles of Database Systems, (Chicago, USA), pp. 243–252, ACM, June 2006. Abstract

A. Dawar, M. Grohe, S. Kreutzer, and N. Schweikardt,
Approximation schemes for firstorder definable optimisation problems,
in LICS'06: 21st Annual IEEE Symposium on Logic in Computer Science, (Seattle, USA), pp. 411–420, IEEE Computer Society, August 2006. Abstract

N. Schweikardt,
On the expressive power of monadic least fixed point logic,
in Theoretical Computer Science, vol. 350, pp. 325–344, 2006. Special issue for selected papers from ICALP'04, Track B. Abstract
2005

D. D. Freydenberger,
Eine vollständige Charakterisierung aller zweideutigen Wörter in L(xabxbcayabcy),
Projektarbeit, TU Kaiserslautern, 2005. In German.

D. D. Freydenberger, D. Reidenbach, and J. C. Schneider,
Unambiguous morphic images of strings,
in Proc. 9th Conference on Developments in Language Theory, DLT 2005, vol. 3572 of LNCS, pp. 248–259, 2005.Link Preprint

M. Zelke,
Ein Approximationsalgorithmus zur Berechnung eines 2Spanners in planaren Triangulationen,
Diplomarbeit Informatik, HumboldtUniversität zu Berlin, 2005.

M. Grohe and N. Schweikardt,
Lower bounds for sorting with few random accesses to external memory,
in PODS'05: 24th ACM SIGACTSIGMODSIGART Symposium on Principles of Database Systems, (Baltimore, USA), pp. 238–249, ACM, June 2005. Abstract

A. Hernich and A. Nickelsen,
Combining selfreducibility and partial information algorithms,
in MFCS (J. Jedrzejowicz and A. Szepietowski, eds.), vol. 3618 of Lecture Notes in Computer Science, pp. 483–494, SpringerVerlag, 2005. © SpringerVerlag. Abstract

M. Grohe, C. Koch, and N. Schweikardt,
The complexity of querying external memory and streaming data,
in FCT'05: 15th International Symposium on Fundamentals of Computation Theory, vol. 3623 of Lecture Notes in Computer Science, (Lübeck, Germany), pp. 1–16, SpringerVerlag, August 2005. Abstract

A. Hernich,
Combining selfreducibility and partial information algorithms,
Diplomarbeit Informatik, Technische Universität Berlin, Germany, 2005. Available at http://www.eccc.unitrier.de/eccc/. Abstract

M. Grohe, S. Kreutzer, and N. Schweikardt,
The expressive power of twovariable least fixedpoint logics,
in MFCS'05: 30th International Symposium on Mathematical Foundations of Computer Science, vol. 3618 of Lecture Notes in Computer Science, (Gdansk, Poland), pp. 422–434, SpringerVerlag, August/September 2005. Abstract

D. A. M. Barrington, N. Immerman, C. Lautemann, N. Schweikardt, and
D. Thérien,
Firstorder expressibility of languages with neutral letters or: The Crane Beach conjecture,
in Journal of Computer and System Sciences, vol. 70, pp. 101–127, 2005. Abstract

M. Grohe and N. Schweikardt,
The succinctness of firstorder logic on linear orders,
in Logical Methods in Computer Science, vol. 1(1:6), pp. 1–25, 2005. Download here from http://www.lmcsonline.org/. Abstract

N. Schweikardt,
Arithmetic, firstorder logic, and counting quantifiers,
in ACM Transactions on Computational Logic, vol. 6(3), pp. 634–671, July 2005. Abstract

M. Grohe, C. Koch, and N. Schweikardt,
Tight lower bounds for query processing on streaming and external memory data,
in ICALP'05: 32nd International Colloquium on Automata, Languages and Programming, vol. 3580 of Lecture Notes in Computer Science, (Lisbon, Portugal), pp. 1076–1088, SpringerVerlag, July 2005. Received the Best Paper Award at ICALP'05, Track B. AbstractLink Full version: CoRR Report, 29 April 2005, 25 pages.
2004

M. Grohe and N. Schweikardt,
The succinctness of firstorder logic on linear orders,
in LICS'04: 19th Annual IEEE Symposium on Logic in Computer Science, (Turku, Finland), pp. 438–447, IEEE Computer Society, July 2004. AbstractPDF Full version

M. Zelke,
Eine neue hinreichende Bedingung für die Existenz eines Hamiltonkreises,
Studienarbeit, HumboldtUniversität zu Berlin, 2004.

M. Grohe and N. Schweikardt,
Comparing the succinctness of monadic query languages over finite trees,
Theoret. Informatics Appl., vol. 38, pp. 343–373, oct 2004. [ DOI  http ] Abstract

N. Schweikardt,
On the expressive power of monadic least fixed point logic,
in ICALP'04: 31st International Colloquium on Automata, Languages and Programming, vol. 3142 of Lecture Notes in Computer Science, (Turku, Finland), pp. 1123–1135, SpringerVerlag, July 2004. AbstractPDF Full version

C. Koch, S. Scherzinger, N. Schweikardt, and B. Stegmaier,
Schemabased scheduling of event processors and buffer minimization for queries on structured data streams,
in VLDB'04: 30th International Conference on Very Large Data Bases, (Toronto, Canada), pp. 228–239, Morgan Kaufmann, August/September 2004. Abstract

C. Koch, S. Scherzinger, N. Schweikardt, and B. Stegmaier,
FluXQuery: An optimizing XQuery processor for streaming XML data,
in VLDB'04: 30th International Conference on Very Large Data Bases, (Toronto, Canada), pp. 1309–1312, Morgan Kaufmann, August/September 2004. Demo Paper. Abstract

S. Kreutzer and N. Schweikardt,
Logik und Informatik,
it  Information Technology, vol. 46, no. 3, pp. 162–166, 2004. Abstract
2003

N. Schweikardt,
Die Ausdrucksstärke der Logik erster Stufe mit eingebauten Prädikaten,
in Ausgezeichnete Informatikdissertationen 2002, Lecture Notes in Informatics, Gesellschaft für Informatik, 2003.

M. Grohe and N. Schweikardt,
Comparing the succinctness of monadic query languages over finite trees,
in CSL'03: 12th Annual Conference of the European Association for Computer Science Logic, vol. 2803 of Lecture Notes in Computer Science, (Vienna, Austria), pp. 226–240, SpringerVerlag, August 2003. AbstractPDF Full version: Technical Report EDIINFRR0168, School of Informatics, University of Edinburgh, Scotland, U.K., 2003.
2002

O. Matz, N. Schweikardt, and W. Thomas,
The Monadic Quantifier Alternation Hierarchy over Grids and Graphs,
Information and Computation, vol. 179, no. 2, pp. 356–383, 2002. Special issue for selected papers from LICS'97. Abstract
2001

N. Schweikardt,
On the expressive power of firstorder logic with builtin predicates,
PhD thesis, Fachbereich Mathematik und Informatik, Johannes GutenbergUniversität Mainz, December 2001. 237 pages. Received the GIDissertationspreis 2002. Published at Logos Verlag Berlin, 2002, ISBN 3832500170.

D. A. M. Barrington, N. Immerman, C. Lautemann, N. Schweikardt, and
D. Thérien,
The Crane Beach conjecture,
in LICS'01: 16th Annual IEEE Symposium on Logic in Computer Science, (Boston, Massachusetts, USA), pp. 187–196, IEEE Computer Society, June 2001. Abstract

C. Lautemann and N. Schweikardt,
An EhrenfeuchtFraïssé approach to collapse results for firstorder queries over embedded databases,
in STACS'01: 18th Annual Symposium on Theoretical Aspects of Computer Science, vol. 2010 of Lecture Notes in Computer Science, (Dresden, Germany), pp. 455–466, SpringerVerlag, February 2001. AbstractPDF Full version: Technical Report 01/2001, Institut für Informatik, Johannes GutenbergUniversität Mainz, Germany, 2003.

N. Schweikardt,
The natural ordergeneric collapse for omegarepresentable databases over the rational and the real ordered group,
in CSL'01: 10th Annual Conference of the European Association for Computer Science Logic, vol. 2142 of Lecture Notes in Computer Science, (Paris, France), pp. 130–144, SpringerVerlag, September 2001. AbstractPDF Technical Report 02/2001, Institut für Informatik, Johannes GutenbergUniversität Mainz, Germany, 2003.
1999

C. Lautemann, N. Schweikardt, and T. Schwentick,
A logical characterisation of linear time on nondeterministic Turing machines,
in STACS'99: 16th Annual Symposium on Theoretical Aspects of Computer Science, vol. 1563 of Lecture Notes in Computer Science, (Trier, Germany), pp. 143–152, SpringerVerlag, March 1999. AbstractPDF Full version
1997

N. Schweikardt,
The monadic secondorder quantifier alternation hierarchy over grids and pictures,
Master's thesis, Johannes GutenbergUniversität Mainz, 1997. Abstract

N. Schweikardt,
The monadic quantifier alternation hierarchy over grids and pictures,
in CSL'97: 6th Annual Conference of the European Association for Computer Science Logic, vol. 1414 of Lecture Notes in Computer Science, (Aarhus, Denmark), pp. 441–460, SpringerVerlag, August 1997. Selected Papers. AbstractPDF Full version: Preliminary Proceedings of CSL'97, BRICS Notes Series NS971, ISSN 09093206, pages 383398.