2015 | 2014 | 2013 | 2012 | 2011 | 2010 | 2009 | 2008 | 2007 | 2006 | 2005 | 2004 | 2003 | 2002 | 2001 | 1999 | 1997  

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 ordnen

2015

  • 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 Hanf-equivalence 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 4-6, 2014 (G. Gottlob and J. Pérez, eds.), vol. 1189 of CEUR Workshop Proceedings, CEUR-WS.org, 2014.
    PDF Link Full version
    PDF Slides
  • N. Schweikardt, V. Christophides, and V. Leroy, eds., Proceedings of the 17th International Conference on Database Theory (ICDT 2014), Athens, Greece, March 24-28, 2014, OpenProceedings.org, 2014.
  • K. S. Candan, S. Amer-Yahia, 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 First-Order 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, Goethe-Universität Frankfurt am Main, 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 Follow-Ups, pp. 237–274, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2013.
  • F. Harwath and N. Schweikardt,
    On the locality of arb-invariant first-order logic with modulo counting quantifiers,
    in Computer Science Logic 2013 (CSL 2013), CSL 2013, vol. 23 of LIPIcs, pp. 363–379, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2013.
    PDF Slides
    PDF 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 order-invariant first-order 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 ACM-SIAM 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, Goethe-Universität Frankfurt am Main, 2012.
  • L. Heimberg,
    Gaifman-Normalformen auf Strukturklassen beschränkten Grades,
    Diplomarbeit, Institut für Informatik, Humboldt-Universitä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. Zelke,
    Weighted matching in the semi-streaming model,
    Algorithmica, vol. 62, no. 1-2, pp. 1–20, 2012.
  • F. Harwath and N. Schweikardt,
    Regular tree languages, cardinality predicates, and addition-invariant 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 - Leibniz-Zentrum fuer Informatik, 2012.
    PDF Slides

2011

  • G. Rieger,
    Analyse und Vergleich der Performanz von Datenstrom-Algorithmen und konventionellen Algorithmen anhand verschiedener Anwendungsszenarien,
    Diplomarbeit, Goethe-Universität Frankfurt, 2011.
  • Der Doktorhut D. D. Freydenberger,
    Inclusion of pattern languages and related problems,
    PhD thesis, Institut für Informatik, Goethe-Universitä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 first-order logic with arbitrary built-in 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, CEUR-WS.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 max-cut 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

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, Goethe-Universität Frankfurt am Main, 2010. In German.
  • Der Doktorhut A. Hernich,
    Foundations of query answering in relational data exchange,
    PhD thesis, Institut für Informatik, Goethe-Universität Frankfurt am Main, 2010. Abstract
  • L. Heimberg,
    Untere Schranken für Gaifman-Normalformen und die Theorie endlicher Bäume,
    Studienarbeit, Humboldt-Universität zu Berlin, 2010.
  • H. Björklund, W. Martens, N. Schweikardt, and T. Schwentick,
    Logik und Automaten: ein echtes Dreamteam,
    Informatik-Spektrum, 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. 34-36, pp. 3274 – 3286, 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.
    Preprint
    PDF Full version
  • 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,
    Addition-invariant 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. Abstract
    PDF Full version of LICS 2010 paper
  • A. Hernich,
    Answering non-monotonic 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.
  • 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, Springer-Verlag, 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 Berlin-Marathon,
    in Besser als Mathe: Moderne angewandte Mathematik aus dem MATHEON zum Mitmachen (K. Biermann, M. Grötschel, and B. Lutz-Westphal, eds.), pp. 62–67, Vieweg Verlag, 2009.
  • 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. Schmidt-Schauß, 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)).
  • N. Schweikardt,
    Short-entry on zero-one laws,
    in Encyclopedia of Database Systems (L. Liu and M. T. Öszu, eds.), p. 3683, Springer-Verlag, 2009. Abstract
  • N. Schweikardt,
    Short-entry on one-pass algorithms,
    in Encyclopedia of Database Systems (L. Liu and M. T. Öszu, eds.), pp. 1948–1949, Springer-Verlag, 2009. Abstract
  • N. Schweikardt,
    Short-entry on Ehrenfeucht-Fraïssé games,
    in Encyclopedia of Database Systems (L. Liu and M. T. Öszu, eds.), pp. 963–964, Springer-Verlag, 2009. Abstract
  • N. Schweikardt,
    Machine models for query processing,
    in Sigmod Record, vol. 38(2), June 2009. Abstract
  • N. Schweikardt,
    Lower bounds for multi-pass 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, Humboldt-Universitä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
  • M. Zelke,
    Weighted Matching in the Semi-Streaming 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(1-3), pp. 191–205, 2008. Abstract

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 k-means clustering based on weak coresets,
    Proc. 23st Annu. ACM Sympos. Comput. Geom. (SOCG), pp. 11–18, 2007.
  • M. Zelke,
    Optimal per-edge processing times in the semi-streaming model,
    Inf. Process. Lett., vol. 104, no. 3, pp. 106–112, 2007.
  • N. Schweikardt,
    An Ehrenfeucht-Fraï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, Springer-Verlag, July 2007. Abstract
  • N. Schweikardt,
    Machine models and lower bounds for query processing,
    in PODS'07: 26th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, (Beijing, China), pp. 41–52, ACM, June 2007. Abstract
    PDF 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, Springer-Verlag, July 2007. Abstract
    PDF Full version. Preprint NI07003-LAA, Isaac Newton Institute of Mathematical Sciences (2007).
  • A. Hernich and N. Schweikardt,
    CWA-solutions for data exchange settings with target dependencies,
    in PODS'07: 26th ACM SIGACT-SIGMOD-SIGART 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(1-2), pp. 199–217, 2007. Special issue for selected papers from ICALP'05. Abstract

2006

  • 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. Grohe, A. Hernich, and N. Schweikardt,
    Randomized computations on large data sets: Tight lower bounds,
    in PODS'06: 25th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, (Chicago, USA), pp. 243–252, ACM, June 2006. Abstract
    PDF Link Full version: CoRR Report, March 2007, 29 pages.
  • A. Dawar, M. Grohe, S. Kreutzer, and N. Schweikardt,
    Approximation schemes for first-order 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 2-Spanners in planaren Triangulationen,
    Diplomarbeit Informatik, Humboldt-Universitä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 SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, (Baltimore, USA), pp. 238–249, ACM, June 2005. Abstract
  • A. Hernich and A. Nickelsen,
    Combining self-reducibility and partial information algorithms,
    in MFCS (J. Jedrzejowicz and A. Szepietowski, eds.), vol. 3618 of Lecture Notes in Computer Science, pp. 483–494, Springer-Verlag, 2005. © Springer-Verlag. 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, Springer-Verlag, August 2005. Abstract
  • A. Hernich,
    Combining self-reducibility and partial information algorithms,
    Diplomarbeit Informatik, Technische Universität Berlin, Germany, 2005. Available at http://www.eccc.uni-trier.de/eccc/. Abstract
  • M. Grohe, S. Kreutzer, and N. Schweikardt,
    The expressive power of two-variable least fixed-point 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, Springer-Verlag, August/September 2005. Abstract
  • D. A. M. Barrington, N. Immerman, C. Lautemann, N. Schweikardt, and D. Thérien,
    First-order 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 first-order logic on linear orders,
    in Logical Methods in Computer Science, vol. 1(1:6), pp. 1–25, 2005. Download here from http://www.lmcs-online.org/. Abstract
  • N. Schweikardt,
    Arithmetic, first-order 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, Springer-Verlag, July 2005. Received the Best Paper Award at ICALP'05, Track B. Abstract
    Link Full version: CoRR Report, 29 April 2005, 25 pages.

2004

  • M. Grohe and N. Schweikardt,
    The succinctness of first-order 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. Abstract
    PDF Full version
  • M. Zelke,
    Eine neue hinreichende Bedingung für die Existenz eines Hamiltonkreises,
    Studienarbeit, Humboldt-Universitä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, Springer-Verlag, July 2004. Abstract
    PDF Full version
  • C. Koch, S. Scherzinger, N. Schweikardt, and B. Stegmaier,
    Schema-based 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
    PDF Link Full version: CoRR Report, 07 June 2004, 14 pages.
  • 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, Springer-Verlag, August 2003. Abstract
    PDF Full version: Technical Report EDI-INF-RR-0168, 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 first-order logic with built-in predicates,
    PhD thesis, Fachbereich Mathematik und Informatik, Johannes Gutenberg-Universität Mainz, December 2001. 237 pages. Received the GI-Dissertationspreis 2002. Published at Logos Verlag Berlin, 2002, ISBN 3-8325-0017-0.
  • 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 Ehrenfeucht-Fraïssé approach to collapse results for first-order 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, Springer-Verlag, February 2001. Abstract
    PDF Full version: Technical Report 01/2001, Institut für Informatik, Johannes Gutenberg-Universität Mainz, Germany, 2003.
  • N. Schweikardt,
    The natural order-generic collapse for omega-representable 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, Springer-Verlag, September 2001. Abstract
    PDF Technical Report 02/2001, Institut für Informatik, Johannes Gutenberg-Universitä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, Springer-Verlag, March 1999. Abstract
    PDF Full version

1997

  • N. Schweikardt,
    The monadic second-order quantifier alternation hierarchy over grids and pictures,
    Master's thesis, Johannes Gutenberg-Universitä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, Springer-Verlag, August 1997. Selected Papers. Abstract
    PDF Full version: Preliminary Proceedings of CSL'97, BRICS Notes Series NS-97-1, ISSN 0909-3206, pages 383-398.