@inproceedings{KreutzerTaz10, author = "Stephan Kreutzer and Siamak Tazari", booktitle = "Symposium on Discrete Algorithms (SODA)", title = "On Brambles, Grid-Like Minors, and Parameterized Intractability of Monadic Second-Order Logic", url = "http://web.comlab.ox.ac.uk/people/Stephan.Kreutzer/Publications/10-soda.pdf", year = "2010", } @inproceedings{DawarKre09, author = "Anuj Dawar and Stephan Kreutzer", booktitle = "Foundations of Software Technology and Theoretical Computer Science (FSTTCS)", title = "Domination Problems in Nowhere-Dense Classes of Graphs,", url = "http://web.comlab.ox.ac.uk/people/Stephan.Kreutzer/Publications/09-fsttcs.pdf", year = "2009", } @article{KreutzerOrd09, author = "Stephan Kreutzer and Sebastian Ordyniak", journal = "34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)", title = "Distance-d-Domination Games", url = "http://web.comlab.ox.ac.uk/people/Stephan.Kreutzer/Publications/09-wg-final.pdf", year = "2009", } @inproceedings{Kreutzer09, author = "Stephan Kreutzer", booktitle = "Computer Science Logic (CSL)", journal = "Computer Science Logic (CSL)", title = "On the Parameterised Intractability of Monadic Second-Order Logic", url = "http://web.comlab.ox.ac.uk/people/Stephan.Kreutzer/Publications/csl09.pdf", year = "2009", } @inproceedings{HKOW-09concur, abstract = "One-counter automata are a fundamental and widely-studied class of infinite-state systems. In this paper we consider one-counter automata with counter updates encoded in binary -- which we refer to as the succinct encoding. It is easily seen that the reachability problem for this class of machines is in PSpace and is NP-hard. One of the main results of this paper is to show that this problem is in fact in NP, and is thus NP-complete. We also consider parametric one-counter automata, in which counter updates be integer-valued parameters. The reachability problem asks whether there are values for the parameters such that a final state can be reached from an initial state. Our second main result shows decidability of the reachability problem for parametric one-counter automata by reduction to existential Presburger arithmetic with divisibility.", author = "Christoph Haase and Stephan Kreutzer and Joel Ouaknine and James Worrell", booktitle = "Proceedings of the 20th International Conference on Concurrency Theory (CONCUR09)", copyright = "Springer-Verlag", editor = "M. Bravetti and G. Zavattaro", location = "Bologna, Italy", month = "September", pages = "369--383", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "Reachability in Succinct and Parametric One-Counter Automata", volume = "5710", year = "2009", } @inproceedings{Kreutzer08, author = "Stephan Kreutzer", booktitle = "International Workshop on Exact and Parameterized Computation (IWPEC)", title = "Algorithmic Meta-Theorems", url = "http://web.comlab.ox.ac.uk/people/Stephan.Kreutzer/Publications/amt-survey.pdf", year = "2008", } @inproceedings{KreutzerOrdyniak08, author = "Stephan Kreutzer and Sebastian Ordyniak", booktitle = "34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)", journal = "34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)", title = "Digraph Decompositions and Monotonocity in Digraph Searching", url = "http://web.comlab.ox.ac.uk/people/Stephan.Kreutzer/Publications/08-wg-final.pdf", year = "2008", } @inproceedings{DKreutzer08, abstract = "We show that the homomorphism preservation theorem fails for LFP, both in general and in restriction to finite structures. That is, there is a formula of LFP that is preserved under homomorphisms (in the finite) but is not equivalent (in the finite) to a Datalog program. This resolves a question posed by Atserias. The results are established by two different methods: (1) a method of diagonalisation that works only in the presence of infinite structures, but establishes a stronger result showing a hierarchy of homomorphism-preserved problems in LFP; and (2) a method based on a pumping lemma for Datalog due to Afrati, Cosmadakis and Yannakakis which establishes the result in restriction to finite structures. We refine the pumping lemma of Afrati et al. and relate it to the power of Monadic Second-Order Logic on tree decompositions of structures.", author = "Anuj Dawar and Stephan Kreutzer", booktitle = "35th International Colloquium on Automata, Languages and Programming (ICALP)", journal = "35th International Colloquium on Automata, Languages and Programming (ICALP)", title = "On Datalog vs. LFP", url = "http://www.comlab.ox.ac.uk/people/stephan.kreutzer/Publications/08-icalp.pdf", year = "2008", } @unpublished{arXiv:0802.2228v1, author = "Stephan Kreutzer and Sebastian Ordyniak", note = "Preprint. Slightly revised version of arXiv.org (no arXiv:0802.2228v1)", title = "Digraph Decompositions and Monotonocity in Digraph Searching", url = "http://web.comlab.ox.ac.uk/oucl/work/stephan.kreutzer/Publications/08-digraph-searching-preprint.pdf", year = "2008", } @article{HunterKre07, annote = "Special Issue for GRASTA'06", author = "Paul Hunter and Stephan Kreutzer", journal = "Theoretical Computer Science (TCS)", pages = "206-219", title = "Digraph Measures: Kelly Decompositions, Games, and Orderings", url = "http://web.comlab.ox.ac.uk/oucl/work/stephan.kreutzer/Publications/07-tcs-kelly.pdf", volume = "399", year = "2008", } @inproceedings{AdlerGroKre08, abstract = "By Robertson and Seymour's graph minor theorem, every minor ideal can be characterised by a finite family of excluded minors. (A minor ideal is a class of graphs closed under taking minors.) We study algorithms for computing excluded minor characterisations of minor ideals. We propose a general method for obtaining such algorithms, which is based on definability in monadic second-order logic and the decidability of the monadic second-order theory of trees. A straightforward application of our method yields algorithms that, for a given k, compute excluded minor characterisations for the minor ideal T_k of all graphs of tree width at most k, the minor ideal B_k of all graphs of branch width at most k, and the minor ideal G_k of all graphs of genus at most k. Our main results are concerned with constructions of new minor ideals from given ones. Answering a question that goes back to Fellows and Langston, we prove that there is an algorithm that, given excluded minor characterisations of two minor ideals C and D, computes such a characterisation for the ideal C\cup D. Furthermore, we obtain an algorithm for computing an excluded minor characterisation for the class of all apex graphs over a minor ideal C, given an excluded minor characterisation for C. (An apex graph over C is a graph G from which one vertex can be removed to obtain a graph in C.) A corollary of this result is a uniform ftp-algorithm for the ``distance k from planarity'' problem.", author = "Isolde Adler and Martin Grohe and Stephan Kreutzer", booktitle = "ACM-SIAM Symposium on Discrete Algorithms (SODA)", title = "Computing Excluded Minors", url = "http://web.comlab.ox.ac.uk/oucl/work/stephan.kreutzer/Publications/08-soda.pdf", year = "2008", } @inproceedings{HunterKre07, author = "Paul Hunter and Stephan Kreutzer", booktitle = "ACM-SIAM Symposium on Discrete Algorithms (SODA)", title = "Digraph Measures: Kelly Decompositions, Games, and Orderings", year = "2007", } @article{DawarKre04, author = "Anuj Dawar and Stephan Kreutzer", journal = "Theoretical Computer Science", number = "1-2", pages = "266 -- 285", title = "Generalising Automaticity to Model Properties of Finite Structures", volume = "379", year = "2007", } @inproceedings{DawarGroKreSch07, author = "Anuj Dawar and Martin Grohe and Stephan Kreutzer and Nicole Schweikardt", booktitle = "International Colloquium on Automata, Languages and Programming (ICALP)", pages = "913-924", series = "Lecture Notes in Computer Science", title = "Model theory makes formulas large", volume = "4596", year = "2007", } @inproceedings{DawarGroKre07, author = "Anuj Dawar and Martin Grohe and Stephan Kreutzer", booktitle = "Logic in Computer Science (LICS)", pages = "270-279", title = "Locally Excluding a Minor", url = "http://web.comlab.ox.ac.uk/oucl/work/stephan.kreutzer/Publications/lics07.pdf", year = "2007", } @inproceedings{BradfieldKre07, author = "Julian Bradfield and Stephan Kreutzer", booktitle = "Foundations of the Formal Sciences V - Infinite Games (FotFS V)", publisher = "College Publications, London, 2007", series = "Studies in Logic", title = "The Complexity of Independence-Friendly Fixpoint Logic", volume = "11", year = "2007", } @article{DawarGraKre06, author = "Anuj Dawar and Erich Gr{\"a}del and Stephan Kreutzer", journal = "Theoretical Computer Science", note = "ICALP 2004 Selected Paper issue", number = "2-3", pages = "171 -- 187", title = "Backtracking Games and Inflationary Fixed Points", volume = "350", year = "2006", } @inproceedings{BerwangerDawHunKre06, author = "Dietmar Berwanger and Anuj Dawar and Paul Hunter and Stephan Kreutzer", booktitle = "Symposium on Theoretical Aspects of Computer Science (STACS)", title = "DAG-Width and Parity Games", url = "http://web.comlab.ox.ac.uk/oucl/work/paul.hunter/papers/dagwidth_stacs06.pdf", year = "2006", } @inproceedings{DawarGroKreSch07, author = "Stephan Kreutzer Nicole Schweikardt Anuj Dawar, Martin Grohe", booktitle = "Logic in Computer Science (LICS)", pages = "411-420", title = "Approximation Schemes for First-Order Definable Optimisation Problems", year = "2006", } @inproceedings{GroheKreSch05, abstract = "The present paper gives a classification of the expressive power of two-variable least fixed-point logics. The main results are:
  1. The two-variable fragment of monadic least fixed-point logic with parameters is as expressive as full monadic least fixed-point logic (on binary structures).
  2. The two-variable fragment of monadic least fixed-point logic without parameters is as expressive as the two-variable fragment of binary least fixed-point logic without parameters.
  3. The two-variable fragment of binary least fixed-point logic with parameters is strictly more expressive than the two-variable fragment of monadic least fixed-point logic with parameters (even on finite strings).
", author = "M. Grohe and S. Kreutzer and N. Schweikardt", booktitle = "Symposium on Mathematical Foundations of Computer Science (MFCS)", pages = "422 -- 434", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "The Expressive Power of Two-Variable Least Fixed-Point Logics", url = "http://web.comlab.ox.ac.uk/oucl/work/stephan.kreutzer/Publications/05-mfcs.pdf", year = "2005", } @inproceedings{BradfieldKre05, author = "Julian Bradfield and Stephan Kreutzer", booktitle = "Proceedings of the 14th Annual Conference of the European Association for Computer Science Logic (CSL)", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "The Complexity of Independence-Friendly Fixpoint Logic", volume = "3634", year = "2005", } @article{Kreutzer05, author = "Achim Blumensath and Stephan Kreutzer", journal = "Journal of Logic and Computation", number = "1", pages = "59 -- 74", title = "An Extension of Muchnik's Theorem", volume = "15", year = "2005", } @article{KreutzerSch04, author = "Stephan Kreutzer and Nicole Schweikardt", journal = "it - {I}nformation {T}echnology", note = "in german", number = "3", pages = "162--166", title = "Logik und {I}nformatik", volume = "46", year = "2004", } @article{Kreutzer04, author = "Stephan Kreutzer", journal = "Annals of Pure and Applied Logic", note = "LICS 2002 Selected Paper Issue", number = "1-3", pages = "61--78", title = "Expressive Equivalence of Least and Inflationary Fixed-Point Logic", volume = "130", year = "2004", } @article{DawarGraKre04, author = "Anuj Dawar and Erich Gr{\"a}del and Stephan Kreutzer", journal = "ACM Transactions on Computational Logic (TOCL", number = "2", pages = "282 - 315", title = "Inflationary Fixed Points in Modal Logics", volume = "5", year = "2004", } @inproceedings{DawarGraKre04, author = "Anuj Dawar and Erich Gr{\"a}del and Stephan Kreutzer", booktitle = "31st International Colloquium on Automata, Languages and Programming (ICALP)", title = "Backtracking games and inflationary fixed points", year = "2004", } Warning - the bibtex entry below may be invalid: Missing 'chapter' or 'pages' field @inbook{Kreutzer03, author = "Stephan Kreutzer", booktitle = "{A}usgezeichnete {I}nformatik {D}issertationen 2003", editor = "D. Wagner et al.", note = "in german", publisher = "German Informatics Society (GI)", series = "Lecture Notes in Informatics - Dissertations", title = "Pure and Applied Fixed-Point Logics", volume = "D-3", year = "2003", } @inproceedings{GraedelKre03, author = "E. Gr{\"a}del and S. Kreutzer", booktitle = "IEEE Symp. of Logic in Computer Science (LICS)", title = "Will Deflation Lead to Depletion? On Non-Monotone Fixed-Point Inductions", year = "2003", } @inproceedings{BerwangerGraKre03, author = "D. Berwanger and E. Gr\"adel and S. Kreutzer", booktitle = "Proceedings of the 10th International Conference on Logic for Programming and Automated Reasoning", editor = "M. Vardi and A. Voronkov", pages = "226 -- 240", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "Once upon a time in the west -- Determinacy, definability and complexity of path games", volume = "2850", year = "2003", } @phdthesis{Kreutzer02c, author = "S. Kreutzer", school = "Dissertation thesis, RWTH Aachen", title = "Pure and Applied Fixed-Point Logics", year = "2002", } @inproceedings{Kreutzer02b, author = "S. Kreutzer", booktitle = "Annual Conference of the European Association for Computer Science Logic (CSL)", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "Partial Fixed-Point Logic on Infinite Structures", volume = "2471", year = "2002", } @inproceedings{Kreutzer02, author = "S. Kreutzer", booktitle = "Proc. of the 17th Symp. on Logic in Computer Science (LICS)", pages = "403 -- 413", title = "Expressive Equivalence of Least and Inflationary Fixed-Point Logic", year = "2002", } @inproceedings{DawarKre02, author = "A. Dawar and S. Kreutzer", booktitle = "Proc. 22nd Conf. on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)", pages = "109--120", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "Generalising Automaticity to Modal Properties of Finite Structures", volume = "2556", year = "2002", } @inproceedings{Kreutzer01c, author = "S. Kreutzer", booktitle = "Proceedings of the 8th International Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR)", pages = "470 -- 484", publisher = "Springer", series = "Lecture Notes in Artificial Intelligence (LNAI)", title = "Operational Semantics for Fixed-Point Logics on Constraint Databases", volume = "2250", year = "2001", } @inproceedings{Kreutzer01, author = "S. Kreutzer", booktitle = "Proceedings of the 8th International Conference on Database Theory (ICDT)", number = "1973", pages = "248--262", publisher = "Springer", series = "#lncs#", title = "Query Languages for Constraint Databases: First-Order Logic, Fixed-Points, and Convex Hulls", year = "2001", } @inproceedings{DawarGraKre01, author = "A. Dawar and E. Gr{\"a}del and S. Kreutzer", booktitle = "Proc. of the 10th Conf. on Computer Science Logic (CSL)", pages = "277--291", publisher = "#springer#", series = "Lecture Notes in Computer Science", title = "Inflationary Fixed Points in Modal Logics", volume = "2142", year = "2001", } @inproceedings{Kreutzer00, author = "S. Kreutzer", booktitle = "Proceedings of the 19th ACM Symp. on Principles of Database Systems (PODS), 2000", pages = "116--125", publisher = "ACM press", title = "Fixed-point Query Languages for Linear Constraint Databases", year = "2000", } Warning - the bibtex entry below may be invalid: Missing 'school' field @mastersthesis{Kreutzer99eng, author = "S. Kreutzer", publisher = "Diploma thesis, RWTH Aachen", title = "Descriptive Complexity Theory for Constraint Databases", year = "1999", } @inproceedings{GraedelKre99, author = "E. Gr{\"a}del and S. Kreutzer", booktitle = "Computer Science Logic (CSL)", number = "1683", pages = "67 -- 82", publisher = "Springer", series = "LNCS", title = "Descriptive Complexity Theory for Constraint Databases", year = "1999", } Warning - the bibtex entry below may be invalid: Missing 'author' field Missing 'title' field Missing 'note' field @unpublished{, }