Stephan Kreutzer : Publications
Click here to download all publications in a single bibtex file
@inproceedings{KreutzerTaz10,
title = "On Brambles, Grid-Like Minors, and Parameterized Intractability of Monadic Second-Order Logic",
author = "Stephan Kreutzer and Siamak Tazari",
year = "2010",
booktitle = "Symposium on Discrete Algorithms (SODA)",
url = "http://web.comlab.ox.ac.uk/people/Stephan.Kreutzer/Publications/10-soda.pdf",
}
@inproceedings{HKOW-09concur,
title = "Reachability in Succinct and Parametric One-Counter Automata",
author = "Christoph Haase and Stephan Kreutzer and Joel Ouaknine and James Worrell",
year = "2009",
booktitle = "Proceedings of the 20th International Conference on Concurrency Theory ({CONCUR'09})",
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",
volume = "5710",
doi = "10.1007/978-3-642-04081-8_25",
}
@article{KreutzerOrd09,
title = "Distance-d-Domination Games",
author = "Stephan Kreutzer and Sebastian Ordyniak",
year = "2009",
journal = "34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)",
url = "http://web.comlab.ox.ac.uk/people/Stephan.Kreutzer/Publications/09-wg-final.pdf",
}
@inproceedings{DawarKre09,
title = "Domination Problems in Nowhere-Dense Classes of Graphs,",
author = "Anuj Dawar and Stephan Kreutzer",
year = "2009",
booktitle = "Foundations of Software Technology and Theoretical Computer Science (FSTTCS)",
url = "http://web.comlab.ox.ac.uk/people/Stephan.Kreutzer/Publications/09-fsttcs.pdf",
}
@inproceedings{Kreutzer09,
title = "On the Parameterised Intractability of Monadic Second-Order Logic",
author = "Stephan Kreutzer",
year = "2009",
booktitle = "Computer Science Logic (CSL)",
journal = "Computer Science Logic (CSL)",
url = "http://web.comlab.ox.ac.uk/people/Stephan.Kreutzer/Publications/csl09.pdf",
}
@article{HunterKre07,
title = "Digraph Measures: Kelly Decompositions, Games, and Orderings",
author = "Paul Hunter and Stephan Kreutzer",
year = "2008",
annote = "Special Issue for GRASTA'06",
journal = "Theoretical Computer Science (TCS)",
pages = "206-219",
url = "http://web.comlab.ox.ac.uk/oucl/work/stephan.kreutzer/Publications/07-tcs-kelly.pdf",
volume = "399",
}
@inproceedings{Kreutzer08,
title = "Algorithmic Meta-Theorems",
author = "Stephan Kreutzer",
year = "2008",
booktitle = "International Workshop on Exact and Parameterized Computation (IWPEC)",
url = "http://web.comlab.ox.ac.uk/people/Stephan.Kreutzer/Publications/amt-survey.pdf",
}
@inproceedings{KreutzerOrdyniak08,
title = "Digraph Decompositions and Monotonocity in Digraph Searching",
author = "Stephan Kreutzer and Sebastian Ordyniak",
year = "2008",
booktitle = "34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)",
journal = "34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)",
url = "http://web.comlab.ox.ac.uk/people/Stephan.Kreutzer/Publications/08-wg-final.pdf",
}
@inproceedings{DKreutzer08,
title = "On Datalog vs. LFP",
author = "Anuj Dawar and Stephan Kreutzer",
year = "2008",
booktitle = "35th International Colloquium on Automata, Languages and Programming (ICALP)",
journal = "35th International Colloquium on Automata, Languages and Programming (ICALP)",
url = "http://www.comlab.ox.ac.uk/people/stephan.kreutzer/Publications/08-icalp.pdf",
}
@inproceedings{AdlerGroKre08,
title = "Computing Excluded Minors",
author = "Isolde Adler and Martin Grohe and Stephan Kreutzer",
year = "2008",
booktitle = "ACM-SIAM Symposium on Discrete Algorithms (SODA)",
url = "http://web.comlab.ox.ac.uk/oucl/work/stephan.kreutzer/Publications/08-soda.pdf",
}
@unpublished{arXiv:0802.2228v1,
title = "Digraph Decompositions and Monotonocity in Digraph Searching",
author = "Stephan Kreutzer and Sebastian Ordyniak",
year = "2008",
note = "Preprint. Slightly revised version of arXiv.org (no arXiv:0802.2228v1)",
url = "http://web.comlab.ox.ac.uk/oucl/work/stephan.kreutzer/Publications/08-digraph-searching-preprint.pdf",
}
@article{DawarKre04,
title = "Generalising Automaticity to Model Properties of Finite Structures",
author = "Anuj Dawar and Stephan Kreutzer",
year = "2007",
journal = "Theoretical Computer Science",
number = "1-2",
pages = "266 -- 285",
volume = "379",
}
@inproceedings{HunterKre07,
title = "Digraph Measures: Kelly Decompositions, Games, and Orderings",
author = "Paul Hunter and Stephan Kreutzer",
year = "2007",
booktitle = "ACM-SIAM Symposium on Discrete Algorithms (SODA)",
}
@inproceedings{DawarGroKreSch07,
title = "Model theory makes formulas large",
author = "Anuj Dawar and Martin Grohe and Stephan Kreutzer and Nicole Schweikardt",
year = "2007",
booktitle = "International Colloquium on Automata, Languages and Programming (ICALP)",
pages = "913-924",
series = "Lecture Notes in Computer Science",
volume = "4596",
}
@inproceedings{DawarGroKre07,
title = "Locally Excluding a Minor",
author = "Anuj Dawar and Martin Grohe and Stephan Kreutzer",
year = "2007",
booktitle = "Logic in Computer Science (LICS)",
pages = "270-279",
url = "http://web.comlab.ox.ac.uk/oucl/work/stephan.kreutzer/Publications/lics07.pdf",
}
@inproceedings{BradfieldKre07,
title = "The Complexity of Independence-Friendly Fixpoint Logic",
author = "Julian Bradfield and Stephan Kreutzer",
year = "2007",
booktitle = "Foundations of the Formal Sciences V - Infinite Games (FotFS V)",
publisher = "College Publications, London, 2007",
series = "Studies in Logic",
volume = "11",
}
@article{DawarGraKre06,
title = "Backtracking Games and Inflationary Fixed Points",
author = "Anuj Dawar and Erich Gr{\"a}del and Stephan Kreutzer",
year = "2006",
journal = "Theoretical Computer Science",
note = "ICALP 2004 Selected Paper issue",
number = "2-3",
pages = "171 -- 187",
volume = "350",
}
@inproceedings{BerwangerDawHunKre06,
title = "DAG-Width and Parity Games",
author = "Dietmar Berwanger and Anuj Dawar and Paul Hunter and Stephan Kreutzer",
year = "2006",
booktitle = "Symposium on Theoretical Aspects of Computer Science (STACS)",
url = "http://web.comlab.ox.ac.uk/oucl/work/paul.hunter/papers/dagwidth_stacs06.pdf",
}
@inproceedings{DawarGroKreSch07,
title = "Approximation Schemes for First-Order Definable Optimisation Problems",
author = "Stephan Kreutzer Nicole Schweikardt Anuj Dawar and Martin Grohe",
year = "2006",
booktitle = "Logic in Computer Science (LICS)",
pages = "411-420",
}
@article{Kreutzer05,
title = "An Extension of Muchnik's Theorem",
author = "Achim Blumensath and Stephan Kreutzer",
year = "2005",
journal = "Journal of Logic and Computation",
number = "1",
pages = "59 -- 74",
volume = "15",
}
@inproceedings{GroheKreSch05,
title = "The Expressive Power of Two-Variable Least Fixed-Point Logics",
author = "M. Grohe and S. Kreutzer and N. Schweikardt",
year = "2005",
booktitle = "Symposium on Mathematical Foundations of Computer Science (MFCS)",
pages = "422 -- 434",
publisher = "Springer",
series = "Lecture Notes in Computer Science",
url = "http://web.comlab.ox.ac.uk/oucl/work/stephan.kreutzer/Publications/05-mfcs.pdf",
}
@inproceedings{BradfieldKre05,
title = "The Complexity of Independence-Friendly Fixpoint Logic",
author = "Julian Bradfield and Stephan Kreutzer",
year = "2005",
booktitle = "Proceedings of the 14th Annual Conference of the European Association for Computer Science Logic (CSL)",
publisher = "Springer",
series = "Lecture Notes in Computer Science",
volume = "3634",
}
@article{KreutzerSch04,
title = "Logik und {I}nformatik",
author = "Stephan Kreutzer and Nicole Schweikardt",
year = "2004",
journal = "it - {I}nformation {T}echnology",
note = "in german",
number = "3",
pages = "162--166",
volume = "46",
}
@article{Kreutzer04,
title = "Expressive Equivalence of Least and Inflationary Fixed-Point Logic",
author = "Stephan Kreutzer",
year = "2004",
journal = "Annals of Pure and Applied Logic",
note = "LICS 2002 Selected Paper Issue",
number = "1-3",
pages = "61--78",
volume = "130",
}
@article{DawarGraKre04,
title = "Inflationary Fixed Points in Modal Logics",
author = "Anuj Dawar and Erich Gr{\"a}del and Stephan Kreutzer",
year = "2004",
journal = "ACM Transactions on Computational Logic (TOCL",
number = "2",
pages = "282 - 315",
volume = "5",
}
@inproceedings{DawarGraKre04,
title = "Backtracking games and inflationary fixed points",
author = "Anuj Dawar and Erich Gr{\"a}del and Stephan Kreutzer",
year = "2004",
booktitle = "31st International Colloquium on Automata, Languages and Programming (ICALP)",
}
@inbook{Kreutzer03,
title = "Pure and Applied Fixed-Point Logics",
author = "Stephan Kreutzer",
year = "2003",
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",
volume = "D-3",
}
@inproceedings{GraedelKre03,
title = "Will Deflation Lead to Depletion? On Non-Monotone Fixed-Point Inductions",
author = "E. Gr{\"a}del and S. Kreutzer",
year = "2003",
booktitle = "IEEE Symp. of Logic in Computer Science (LICS)",
}
@inproceedings{BerwangerGraKre03,
title = "Once upon a time in the west -- Determinacy, definability and complexity of path games",
author = "D. Berwanger and E. Gr\"adel and S. Kreutzer",
year = "2003",
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",
volume = "2850",
}
@inproceedings{Kreutzer02b,
title = "Partial Fixed-Point Logic on Infinite Structures",
author = "S. Kreutzer",
year = "2002",
booktitle = "Annual Conference of the European Association for Computer Science Logic (CSL)",
publisher = "Springer",
series = "Lecture Notes in Computer Science",
volume = "2471",
}
@inproceedings{Kreutzer02,
title = "Expressive Equivalence of Least and Inflationary Fixed-Point Logic",
author = "S. Kreutzer",
year = "2002",
booktitle = "Proc. of the 17th Symp. on Logic in Computer Science (LICS)",
pages = "403 -- 413",
}
@inproceedings{DawarKre02,
title = "Generalising Automaticity to Modal Properties of Finite Structures",
author = "A. Dawar and S. Kreutzer",
year = "2002",
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",
volume = "2556",
}
@phdthesis{Kreutzer02c,
title = "Pure and Applied Fixed-Point Logics",
author = "S. Kreutzer",
year = "2002",
school = "Dissertation thesis, RWTH Aachen",
}
@inproceedings{Kreutzer01c,
title = "Operational Semantics for Fixed-Point Logics on Constraint Databases",
author = "S. Kreutzer",
year = "2001",
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)",
volume = "2250",
}
@inproceedings{Kreutzer01,
title = "Query Languages for Constraint Databases: First-Order Logic, Fixed-Points, and Convex Hulls",
author = "S. Kreutzer",
year = "2001",
booktitle = "Proceedings of the 8th International Conference on Database Theory (ICDT)",
number = "1973",
pages = "248--262",
publisher = "Springer",
series = "#lncs#",
}
@inproceedings{DawarGraKre01,
title = "Inflationary Fixed Points in Modal Logics",
author = "A. Dawar and E. Gr{\"a}del and S. Kreutzer",
year = "2001",
booktitle = "Proc. of the 10th Conf. on Computer Science Logic (CSL)",
pages = "277--291",
publisher = "#springer#",
series = "Lecture Notes in Computer Science",
volume = "2142",
}
@inproceedings{Kreutzer00,
title = "Fixed-point Query Languages for Linear Constraint Databases",
author = "S. Kreutzer",
year = "2000",
booktitle = "Proceedings of the 19th ACM Symp. on Principles of Database Systems (PODS), 2000",
pages = "116--125",
publisher = "ACM press",
}
@inproceedings{GraedelKre99,
title = "Descriptive Complexity Theory for Constraint Databases",
author = "E. Gr{\"a}del and S. Kreutzer",
year = "1999",
booktitle = "Computer Science Logic (CSL)",
number = "1683",
pages = "67 -- 82",
publisher = "Springer",
series = "LNCS",
}
@mastersthesis{Kreutzer99eng,
title = "Descriptive Complexity Theory for Constraint Databases",
author = "S. Kreutzer",
year = "1999",
publisher = "Diploma thesis, RWTH Aachen",
}