Dr. Stephan Kreutzer
Professor of Computer Science
Fellow of Linacre College
| :: | :: | Research/Project | :: | :: | :: |
| Preprints |
| Publications |
| Technical Reports |
| Academic theses |
|
Algorithmic Meta-Theorems,
Stephan Kreutzer This survey on algorithmic meta theorems will appear in a workshop volume for a workshop held in Durham 2006 as part of the Newton institute special programme on Logic and Algorithms. |
ps | ps.gz | ||
|
|
Extended Computation Tree Logic, Roland Axelsson, Matthew Hague, Stephan Kreutzer, Martin Lange and Markus Latte, LPAR, 2010. | ps | ps.gz | ||
|
|
Linkless and flat embeddings in 3-space and the Unknot problem, Ken-ichi Kawarabayashi, Stephan Kreutzer and Bojan Mohar, Symposium on Computational Geometry (SOCG), 2010. | ps | ps.gz | ||
|
|
Lower Bounds for the Complexity of Monadic Second-Order Logic, Stephan Kreutzer and Siamak Tazari, Logic in Computer Science (LICS), 2010. | ps | ps.gz | ||
|
|
On Brambles, Grid-Like Minors, and Parameterized Intractability of Monadic Second-Order Logic, Stephan Kreutzer and Siamak Tazari, Symposium on Discrete Algorithms (SODA), 2010. | ps | ps.gz | ||
|
|
Domination Problems in Nowhere-Dense Classes of Graphs, Anuj Dawar and Stephan Kreutzer, Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2009. | ps | ps.gz | ||
|
|
On the Parameterised Intractability of Monadic Second-Order Logic, Stephan Kreutzer, Proc. of the 18th EACSL Conference on Computer Science Logic (CSL), 2009. | ps | ps.gz | ||
|
|
Reachability in Succinct and Parametric One-Counter Automata, Christoph Haase, Stephan Kreutzer, Joel Ouaknine and James Worrel, to appear at 20th Intl. Conference on Concurrency Theory (CONCUR), 2009. | ps | ps.gz | ||
|
|
Distance-d-Domination Games, Stephan Kreutzer and Sebastian Ordyniak, 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), 2009. | ps | ps.gz | ||
|
|
On Datalog vs. LFP , Anuj Dawar, Stephan Kreutzer, 35th International Colloquium on Automata, Languages and Programming (ICALP), 2008 | ps | ps.gz | ||
|
|
Algorithmic Meta-Theorems, Stephan
Kreutzer, International Workshop on Exact and
Parameterized Computation (IWPEC), 2008. This paper contains a reference to a survey Finite Model Theory of Tree-Like Structures. This survey is now available under the title algorithmic meta theorems, to appear in a workshop volume for a workshop held in Durham 2006. |
ps | ps.gz | ||
|
|
Computing Excluded Minors , Isolde Adler, Martin Grohe, Stephan Kreutzer, SODA 2008 | ps | ps.gz | ||
|
|
Digraph Decompositions and Monotonocity in Digraph Searching, Stephan Kreutzer and Sebastian Ordyniak, 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), 2008. | ps | ps.gz | ||
|
|
Digraph Measures: Kelly Decompositions, Games, and Ordering, Paul Hunter and Stephan Kreutzer, Theoretical Computer Science (TCS) 399(3), 2008 | ps | ps.gz | ||
|
|
Non-Regular Modal Logics , Stephan Kreutzer and Martin Lange, Logic and Automata - History and Perspectives, 2008. | ||||
|
|
Model theory makes formulas large , Anuj Dawar, Martin Grohe, Stephan Kreutzer, Nicole Schweikardt, ICALP 2007 | ps | ps.gz | ||
|
|
Boundedness of Monadic FO over Acyclic Structures , Stephan Kreutzer, Martin Otto, Nicole Schweikardt, ICALP 2007 | ps | ps.gz | ||
|
|
Locally Excluding a Minor , Anuj Dawar, Martin Grohe, Stephan Kreutzer, LICS 2007 | ps | ps.gz | ||
|
|
Digraph Measures: Kelly Decompositions, Games, and Orderings , Paul Hunter, Stephan Kreutzer, SODA 2007 | ps | ps.gz | ||
|
|
Backtracking Games and Inflationary Fixed Points Anuj Dawar, Erich Grädel, Stephan Kreutzer, Theoretical Computer Science 350(2-3), ICALP 2004 Selected Paper issue, 171 - 187, 2006 | ps | ps.gz | ||
|
|
Generalising Automaticity to Model Properties of Finite Structures, Anuj Dawar, Stephan Kreutzer, Theoretical Computer Science 379(1-2), pages 266-285, 2007 | ps | ps.gz | ||
|
|
Approximation Schemes for First-Order Definable Optimisation Problems , Anuj Dawar, Martin Grohe, Stephan Kreutzer, Nicole Schweikardt, LICS 2006 | ps | ps.gz | ||
|
|
DAG-Width and Parity Games , Dietmar Berwanger, Anuj Dawar, Paul Hunter, Stephan Kreutzer, STACS 2006 | ps | ps.gz | ||
|
|
The Expressive Power of Two Variable Least Fixed-Point Logics , Martin Grohe, Stephan Kreutzer, Nicole Schweikardt, Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, 422-434, Springer-Verlag, 2005. | ps | ps.gz | ||
|
|
An Extension of Muchnik's Theorem Achim Blumensath, Stephan Kreutzer, Journal of Logic and Computation, 15(1), pages 59 - 74, 2005 | ps | ps.gz | ||
|
|
The Complexity of Independence-Friendly Fixpoint Logic , Julian Bradfield, Stephan Kreutzer, Proceedings of the 14th Annual Conference of the European Association for Computer Science Logic (CSL), Lecture Notes in Computer Science 3634, Springer-Verlag, 2005. | ps | ps.gz | ||
|
|
Expressive Equivalence of Least and Inflationary Fixed-Point Logic, Stephan Kreutzer, Annals of Pure and Applied Logic, LICS 2002 Selected Paper Issue, Volume 130, Issues 1-3, Pages 61-78, 2004 | ps | ps.gz | ||
|
|
Inflationary Fixed Points in Modal Logics, Anuj Dawar, Erich Grädel, and Stephan Kreutzer, ACM Transactions on Computational Logic (TOCL), 5(2), pages 282 - 315, 2004 | ps | ps.gz | ||
|
|
Backtracking games and inflationary fixed points , Anuj Dawar, Erich Grädel, Stephan Kreutzer, 31st International Colloquium on Automata, Languages and Programming (ICALP), 2004. | ps | ps.gz | ||
|
|
The Complexity of Independence-Friendly Fixpoint Logic, Julian Bradfield, Stephan Kreutzer, Foundations of the Formal Sciences V - Infinite Games (FotFS V), accepted for publication, 2004. | ||||
|
|
Once upon a time in the west. Determinacy, complexity and definability of path games , Dietmar Berwanger, Erich Grädel, Stephan Kreutzer, in 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. | ps | ps.gz | ||
|
|
Will Deflation Lead to Depletion? On Non-Monotone Fixed Point Inductions , Erich Grädel, Stephan Kreutzer, IEEE Symp. on Logic in Computer Science (LICS), 2003. | ps | ps.gz | ||
|
|
Logik und Informatik, (in german), Stephan Kreutzer and Nicole Schweikardt, in "it - Information Technology", Vol. 46, No. 3, 2004, pages 162-166. | ||||
|
|
Pure and Applied Fixed-Point Logics, (in german), 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. | ps | ps.gz | ||
|
|
Generalising Automaticity to Modal Properties of Finite Structures , Anuj Dawar, Stephan Kreutzer, Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2002. | ps | ps.gz | ||
|
|
Partial Fixed-Point Logic on Infinite Structures , Stephan Kreutzer,Annual Conference of the European Association for Computer Science Logic (CSL), 2002. | ps | ps.gz | ||
|
|
Expressive Equivalence of Least and Inflationary Fixed-Point Logic , Stephan Kreutzer, Proceedings of the 17th IEEE Symp. on Logic in Computer Science (LICS), 2002. | ps | ps.gz | ||
|
|
Operational Semantics for Fixed-Point Logics on Constraint Databases , Stephan Kreutzer, Proceedings of the 8th International Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR), LNAI 2250, 2001. | ps | ps.gz | ||
|
|
Inflationary Fixed Points in Modal Logics
,
Anuj Dawar, Erich Grädel, and Stephan Kreutzer,
Proceedings of the 10th Annual Conference of the
European Association for Computer Science Logic (CSL),
2001.
© Springer Verlag ( LNCS series ) |
ps | ps.gz | ||
|
|
Query Languages for Constraint Databases: First-Order Logic, Fixed-Points,
and Convex Hulls
,
Stephan Kreutzer, Proceedings of the 8th International
Conference on Database Theory (ICDT), 2001.
© Springer Verlag ( LNCS series ) |
ps | ps.gz | ||
|
|
Fixed-Point Query Languages for Linear Constraint Databases , Stephan Kreutzer, Proceedings of the 19th ACM Symp. on Principles of Database Systems (PODS), 2000. | ps | ps.gz | ||
|
|
Descriptive Complexity Theory for Constraint Databases
,
Erich Grädel, Stephan Kreutzer, Proceedings of CSL
'99, Lecture Notes in Computer Science 1683, Springer 1999.
© Springer Verlag ( LNCS series ) |
ps | ps.gz | ||
|
|
On the Parameterised Intractability of Monadic Second-Order Logic, Stephan Kreutzer, arXiv:0904.1302v1, 2009. | ||||
|
|
Algorithmic Meta-Theorems, Stephan Kreutzer, arXiv:0902.3616v1, 2009. | ||||
|
|
Digraph Decompositions and Monotonicity in Digraph Searching, Stephan Kreutzer and Sebastian Ordyniak, arXiv:0802.2228v1, 2008. | ||||
|
|
Pure and Applied Fixed-Point Logics, Stephan Kreutzer, dissertation thesis, RWTH Aachen, 2002 | ps | ps.gz | ||
|
|
Descriptive Complexity Theory for Constraint Databases, Stephan Kreutzer, diploma thesis, RWTH Aachen, 1999 | ps | ps.gz | ||