Publication List
There are also some preprint available form arXiv.org, see this link.
| Quantitative Monadic Second-Order Logic.(.pdf) |
| Cristian Riveros, Stephan Kreutzer |
| in ACM/IEEE Symp. on Logic in Computer Science (LICS), 2013. (to appear) |
| First-Order and Monadic Second-Order Model-Checking on Ordered Structures.(.pdf) |
| Kord Eickmeyer, Ken-ichi Kawarabayashi, Stephan Kreutzer |
| in ACM/IEEE Symp. on Logic in Computer Science (LICS), 2013. (to appear) |
| Graph Operations on Parity Games and Polynomial-Time Algorithms. |
| Christoph Dittmann, Stephan Kreutzer, Alexandru I. Tomescu |
| in Short Presentation at ACM/IEEE Symp. on Logic in Computer Science (LICS), 2013. (to appear) |
| Packing directed cycles through a specified vertex set. (.pdf) |
| Ken-ichi Kawarabayashi, Marek Krcal, Daniel Kral, Stephan Kreutzer |
| in ACM/SIAM Symp. on Discrete Algorithms (SODA), pp. 365--377, 2013. |
| On the Parameterized Intractability of Monadic Second-Order Logic. (.pdf) |
| Stephan Kreutzer |
| in Logical Methods in Computer Science 8(1), 2012. |
| Linkless and Flat Embeddings in 3-Space. (.pdf) |
| Ken-ichi Kawarabayashi, Stephan Kreutzer, Bojan Mohar |
| in Discrete & Computational Geometry 47(4), pp. 731--755 , 2012. |
| The dag-width of directed graphs. (.pdf) |
| Dietmar Berwanger, Anuj Dawar, Paul Hunter, Stephan Kreutzer, Jan Obdrzálek |
| in Journal of Combinatorial Theory, Series B 102(4), pp. 900--923, 2012. |
| First-Order and Monadic Second-Order Model-Checking on Ordered Structures. (.pdf) |
| Viktor Engelmann, Stephan Kreutzer, Sebastian Siebertz |
| in IEEE Symp. on Logic in Computer Science (LICS), pp. 275--284, 2012. |
| Directed Nowhere Dense Classes of Graphs (.pdf) |
| Stephan Kreutzer and Siamak Tazari |
| in Proc. of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA), 2012. |
| Methods for Algorithmic Meta-Theorems (.pdf) |
| Martin Grohe and Stephan Kreutzer |
| in Model Theoretic Methods in Finite Combinatorics, Contemporary Mathematics vol. 588, American Mathematical Society, 2011. |
| Algorithmic Meta-Theorems (.pdf, .ps.gz, .ps) |
| Stephan Kreutzer |
| in Finite and Algorithmic Model Theory, London Mathematical Society Lecture Notes, No. 379, Cambridge University Press, 2011. |
| Digraph decompositions and Monotonicity in Digraph Searching (.pdf) |
| Stephan Kreutzer, Sebastian Ordyniak |
| Theoretical Computer Science (TCS) (in press), 2011. |
| Graph Searching Games (.pdf) |
| Stephan Kreutzer |
| in Lectures in Game Theory for Computer Scientists, K. Apt and E. Grädel (eds.), Cambridge University Press, 2011. |
| DAG-width and Parity Games (.pdf, .ps.gz, .ps) |
| Dietmar Berwanger, Anuj Dawar, Paul Hunter, Stephan Kreutzer, Jan Obdrzalek |
| Journal of Combinatorial Theory, Series B (accepted for publication), 2011. |
| Linkless and flat embeddings in the 3-space (.pdf, .ps.gz, .ps) |
| Ken-ichi Kawarabayashi, Stephan Kreutzer, Bojan Mohar |
| Journal of Discrete and Computational Geometry (DCG) (accepted for publication), 2011. |
| Linkless and flat embeddings in 3-space and the Unknot problem (.pdf, .ps.gz, .ps) |
| Ken-ichi Kawarabayashi, Stephan Kreutzer and Bojan Mohar |
| Symposium on Computational Geometry (SOCG), 2010.. |
| Lower Bounds for the Complexity of Monadic Second-Order Logic (.pdf, .ps.gz, .ps) |
| Stephan Kreutzer, Siamak Tazari |
| Logic in Computer Science (LICS), 2010. |
| On Brambles, Grid-Like Minors, and Parameterized Intractability of Monadic Second-Order Logic (.pdf, .ps.gz, .ps) |
| Stephan Kreutzer, Siamak Tazari |
| Symposium on Discrete Algorithms (SODA), 2010. |
| Extended Computation Tree Logic (.pdf, .ps.gz, .ps) |
| Roland Axelsson, Matthew Hague, Stephan Kreutzer, Martin Lange and Markus Latt |
| LPAR, 2010. |
| Domination Problems in Nowhere-Dense Classes of Graphs (.pdf, .ps.gz, .ps) |
| Anuj Dawar, Stephan Kreutzer |
| Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2009. |
| On the Parameterised Intractability of Monadic Second-Order Logic (.pdf, .ps.gz, .ps) |
| Stephan Kreutzer |
| Proc. of the 18th EACSL Conference on Computer Science Logic (CSL), 2009. |
| Reachability in Succinct and Parametric One-Counter Automata (.pdf, .ps.gz, .ps) |
| Christoph Haase, Stephan Kreutzer, Joel Ouaknine and James Worrel |
| 20th Intl. Conference on Concurrency Theory (CONCUR), 2009. |
| Distance-d-Domination Games (.pdf, .ps.gz, .ps) |
| Stephan Kreutzer and Sebastian Ordyniak |
| 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), 2009. |
| On Datalog vs. LFP (.pdf, .ps.gz, .ps) |
| Anuj Dawar, Stephan Kreutzer |
| 35th International Colloquium on Automata, Languages and Programming (ICALP), 2008. |
| Algorithmic Meta-Theorems (.pdf, .ps.gz, .ps) |
| Stephan Kreutzer |
| International Workshop on Exact and Parameterized Computation (IWPEC), 2008. |
| Computing Excluded Minors (.pdf, .ps.gz, .ps) |
| Isolde Adler, Martin Grohe, Stephan Kreutzer |
| SODA 2008. |
| Digraph Decompositions and Monotonocity in Digraph Searching (.pdf, .ps.gz, .ps) |
| Stephan Kreutzer and Sebastian Ordyniak |
| 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), 2008. |
| Digraph Measures: Kelly Decompositions, Games, and Ordering (.pdf, .ps.gz, .ps) |
| Paul Hunter and Stephan Kreutzer |
| Theoretical Computer Science (TCS) 399(3), 2008. |
| Non-Regular Modal Logics (.pdf, .ps.gz, .ps) |
| Stephan Kreutzer and Martin Lange |
| in Logic and Automata - History and Perspectives, Texts in Logic and Games, Vol. 2, Amsterdam University Press, 2008. |
| Model theory makes formulas large (.pdf, .ps.gz, .ps) |
| Anuj Dawar, Martin Grohe, Stephan Kreutzer, Nicole Schweikardt |
| ICALP 2007.. |
| Boundedness of Monadic FO over Acyclic Structures (.pdf, .ps.gz, .ps) |
| Stephan Kreutzer, Martin Otto, Nicole Schweikardt |
| ICALP 2007. |
| Locally Excluding a Minor (.pdf, .ps.gz, .ps) |
| Anuj Dawar, Martin Grohe, Stephan Kreutzer |
| LICS 2007. |
| Digraph Measures: Kelly Decompositions, Games, and Orderings (.pdf, .ps.gz, .ps) |
| Paul Hunter, Stephan Kreutzer |
| SODA 2007. |
| Backtracking Games and Inflationary Fixed Points (.pdf, .ps.gz, .ps) |
| Anuj Dawar, Erich Grädel, Stephan Kreutzer, |
| Theoretical Computer Science 350(2-3), ICALP 2004 Selected Paper issue, 171 - 187, 2006. |
| Generalising Automaticity to Model Properties of Finite Structures (.pdf, .ps.gz, .ps) |
| Anuj Dawar, Stephan Kreutzer |
| Theoretical Computer Science 379(1-2), pages 266-285, 2007. |
| Approximation Schemes for First-Order Definable Optimisation Problems (.pdf, .ps.gz, .ps) |
| Anuj Dawar, Martin Grohe, Stephan Kreutzer, Nicole Schweikardt |
| IEEE Symp. on Logic in Computer Science (LICS), 2006. |
| DAG-Width and Parity Games (.pdf, .ps.gz, .ps) |
| Dietmar Berwanger, Anuj Dawar, Paul Hunter, Stephan Kreutzer |
| STACS 2006. |
| The Expressive Power of Two Variable Least Fixed-Point Logics (.pdf, .ps.gz, .ps) |
| Martin Grohe, Stephan Kreutzer, Nicole Schweikardt |
| Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, 422-434, 2005. |
| An Extension of Muchnik's Theorem (.pdf, .ps.gz, .ps) |
| Achim Blumensath, Stephan Kreutzer |
| Journal of Logic and Computation, 15(1), pages 59 - 74, 2005. |
| The Complexity of Independence-Friendly Fixpoint Logic (.pdf, .ps.gz, .ps) |
| Julian Bradfield, Stephan Kreutzer |
| 14th Annual Conference of the European Association for Computer Science Logic (CSL), Lecture Notes in Computer Science 3634, Springer-Verlag, 2005. |
| Expressive Equivalence of Least and Inflationary Fixed-Point Logic (.pdf, .ps.gz, .ps) |
| Stephan Kreutzer |
| Annals of Pure and Applied Logic, LICS 2002 Selected Paper Issue, Volume 130, Issues 1-3, Pages 61-78, 2004. |
| Inflationary Fixed Points in Modal Logics (.pdf, .ps.gz, .ps) |
| Anuj Dawar, Erich Grädel, and Stephan Kreutzer, |
| ACM Transactions on Computational Logic (TOCL), 5(2), pages 282 - 315, 2004. |
| Backtracking games and inflationary fixed points (.pdf, .ps.gz, .ps) |
| Anuj Dawar, Erich Grädel, Stephan Kreutzer |
| 31st International Colloquium on Automata, Languages and Programming (ICALP), 2004.. |
| The Complexity of Independence-Friendly Fixpoint Logic, (.pdf, .ps.gz, .ps) |
| Julian Bradfield, Stephan Kreutzer |
| Foundations of the Formal Sciences V - Infinite Games (FotFS V),2004.. |
| Once upon a time in the west. Determinacy, complexity and definability of path games (.pdf, .ps.gz, .ps) |
| Dietmar Berwanger, Erich Grädel, Stephan Kreutzer |
| Proceedings of the 10th International Conference on Logic for Programming and Automated Reasoning, LPAR 2003, Almaty (M. Vardi and A. Voronkov, eds.), vol. 2850 of LNCS, pp. 226-240, Springer-Verlag, 2003. . |
| Will Deflation Lead to Depletion? On Non-Monotone Fixed Point Inductions (.pdf, .ps.gz, .ps) |
| Erich Grädel, Stephan Kreutzer |
| IEEE Symp. on Logic in Computer Science (LICS), 2003.. |
| Logik und Informatik (in german) (.pdf, .ps.gz, .ps) |
| Stephan Kreutzer and Nicole Schweikardt |
| "it - Information Technology", Vol. 46, No. 3, pages 162-166, 2004. |
| Pure and Applied Fixed-Point Logics (in german) (.pdf, .ps.gz, .ps) |
| Stephan Kreutzer |
| in "Ausgezeichnete Informatik Dissertationen 2003" (D. Wagner et al., ed.), vol. D-3 of Lecture Notes in Informatics - Dissertations, pp. 59-68, German Informatics Society (GI), 2003.. |
| Generalising Automaticity to Modal Properties of Finite Structures (.pdf, .ps.gz, .ps) |
| Anuj Dawar, Stephan Kreutzer |
| Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2002. |
| Partial Fixed-Point Logic on Infinite Structures (.pdf, .ps.gz, .ps) |
| Stephan Kreutzer |
| Annual Conference of the European Association for Computer Science Logic (CSL), 2002. |
| Expressive Equivalence of Least and Inflationary Fixed-Point Logic (.pdf, .ps.gz, .ps) |
| Stephan Kreutzer |
| Proceedings of the 17th IEEE Symp. on Logic in Computer Science (LICS), 2002. |
| Operational Semantics for Fixed-Point Logics on Constraint Databases (.pdf, .ps.gz, .ps) |
| Stephan Kreutzer |
| Proceedings of the 8th International Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR), LNAI 2250, 2001. |
| Inflationary Fixed Points in Modal Logics (.pdf, .ps.gz, .ps) |
| Anuj Dawar, Erich Grädel, Stephan Kreutzer |
| Proceedings of the 10th Annual Conference of the
European Association for Computer Science Logic (CSL),
2001. © Springer Verlag ( LNCS series ) |
| Query Languages for Constraint Databases: First-Order Logic, Fixed-Points, and Convex Hulls (.pdf, .ps.gz, .ps) |
| Stephan Kreutzer |
| Proceedings of the 8th International
Conference on Database Theory (ICDT), 2001. © Springer Verlag ( LNCS series ) |
| Fixed-Point Query Languages for Linear Constraint Databases (.pdf, .ps.gz, .ps) |
| Stephan Kreutzer |
| Proceedings of the 19th ACM Symp. on Principles of Database Systems (PODS), 2000. |
| Descriptive Complexity Theory for Constraint Databases (.pdf, .ps.gz, .ps) |
| Erich Grädel, Stephan Kreutzer |
| Proceedings of CSL
'99, Lecture Notes in Computer Science 1683, Springer 1999. © Springer Verlag ( LNCS series ) |
| Pure and Applied Fixed-Point Logics (.pdf, .ps.gz, .ps) |
| Stephan Kreutzer |
| dissertation thesis, RWTH Aachen, 2002. |
| Descriptive Complexity Theory for Constraint Databases (.pdf, .ps.gz, .ps) |
| Stephan Kreutzer |
| diploma thesis, RWTH Aachen, 1999. |