Stephan Kreutzer : Publications

Book chapters

• [1]

  Pure and Applied Fixed−Point Logics

  Stephan Kreutzer

  In D. Wagner et al., editor, Ausgezeichnete Informatik Dissertationen 2003. Vol. D−3 of Lecture Notes in Informatics − Dissertations. German Informatics Society (GI). 2003.

  in german

  Details about Pure and Applied Fixed−Point Logics | BibTeX data for Pure and Applied Fixed−Point Logics

Journal papers

• [1]

  Distance−d−Domination Games

  Stephan Kreutzer and Sebastian Ordyniak

  In 34th International Workshop on Graph−Theoretic Concepts in Computer Science (WG). 2009.

  Details about Distance−d−Domination Games | BibTeX data for Distance−d−Domination Games | Download (pdf) of Distance−d−Domination Games

• [2]

  Digraph Measures: Kelly Decompositions‚ Games‚ and Orderings

  Paul Hunter and Stephan Kreutzer

  In Theoretical Computer Science (TCS). Vol. 399. Pages 206−219. 2008.

  Details about Digraph Measures: Kelly Decompositions‚ Games‚ and Orderings | BibTeX data for Digraph Measures: Kelly Decompositions‚ Games‚ and Orderings | Download (pdf) of Digraph Measures: Kelly Decompositions‚ Games‚ and Orderings

• [3]

  Generalising Automaticity to Model Properties of Finite Structures

  Anuj Dawar and Stephan Kreutzer

  In Theoretical Computer Science. Vol. 379. No. 1−2. Pages 266 – 285. 2007.

  Details about Generalising Automaticity to Model Properties of Finite Structures | BibTeX data for Generalising Automaticity to Model Properties of Finite Structures

• [4]

  Backtracking Games and Inflationary Fixed Points

  Anuj Dawar‚ Erich Grädel and Stephan Kreutzer

  In Theoretical Computer Science. Vol. 350. No. 2−3. Pages 171 – 187. 2006.

  ICALP 2004 Selected Paper issue

  Details about Backtracking Games and Inflationary Fixed Points | BibTeX data for Backtracking Games and Inflationary Fixed Points

• [5]

  An Extension of Muchnik's Theorem

  Achim Blumensath and Stephan Kreutzer

  In Journal of Logic and Computation. Vol. 15. No. 1. Pages 59 – 74. 2005.

  Details about An Extension of Muchnik's Theorem | BibTeX data for An Extension of Muchnik's Theorem

• [6]

  Logik und Informatik

  Stephan Kreutzer and Nicole Schweikardt

  In it − Information Technology. Vol. 46. No. 3. Pages 162–166. 2004.

  in german

  Details about Logik und Informatik | BibTeX data for Logik und Informatik

• [7]

  Expressive Equivalence of Least and Inflationary Fixed−Point Logic

  Stephan Kreutzer

  In Annals of Pure and Applied Logic. Vol. 130. No. 1−3. Pages 61–78. 2004.

  LICS 2002 Selected Paper Issue

  Details about Expressive Equivalence of Least and Inflationary Fixed−Point Logic | BibTeX data for Expressive Equivalence of Least and Inflationary Fixed−Point Logic

• [8]

  Inflationary Fixed Points in Modal Logics

  Anuj Dawar‚ Erich Grädel and Stephan Kreutzer

  In ACM Transactions on Computational Logic (TOCL. Vol. 5. No. 2. Pages 282 − 315. 2004.

  Details about Inflationary Fixed Points in Modal Logics | BibTeX data for Inflationary Fixed Points in Modal Logics

Conference papers

• [1]

  On Brambles‚ Grid−Like Minors‚ and Parameterized Intractability of Monadic Second−Order Logic

  Stephan Kreutzer and Siamak Tazari

  In Symposium on Discrete Algorithms (SODA). 2010.

  Details about On Brambles‚ Grid−Like Minors‚ and Parameterized Intractability of Monadic Second−Order Logic | BibTeX data for On Brambles‚ Grid−Like Minors‚ and Parameterized Intractability of Monadic Second−Order Logic | Download (pdf) of On Brambles‚ Grid−Like Minors‚ and Parameterized Intractability of Monadic Second−Order Logic

• [2]

  Domination Problems in Nowhere−Dense Classes of Graphs‚

  Anuj Dawar and Stephan Kreutzer

  In Foundations of Software Technology and Theoretical Computer Science (FSTTCS). 2009.

  Details about Domination Problems in Nowhere−Dense Classes of Graphs‚ | BibTeX data for Domination Problems in Nowhere−Dense Classes of Graphs‚ | Download (pdf) of Domination Problems in Nowhere−Dense Classes of Graphs‚

• [3]

  On the Parameterised Intractability of Monadic Second−Order Logic

  Stephan Kreutzer

  In Computer Science Logic (CSL). 2009.

  Details about On the Parameterised Intractability of Monadic Second−Order Logic | BibTeX data for On the Parameterised Intractability of Monadic Second−Order Logic | Download (pdf) of On the Parameterised Intractability of Monadic Second−Order Logic

• [4]

  Reachability in Succinct and Parametric One−Counter Automata

  Christoph Haase‚ Stephan Kreutzer‚ Joel Ouaknine and James Worrell

  In M. Bravetti and G. Zavattaro, editors, Proceedings of the 20th International Conference on Concurrency Theory (CONCUR'09). Vol. 5710 of Lecture Notes in Computer Science. Pages 369–383. Springer. September, 2009.

  Details about Reachability in Succinct and Parametric One−Counter Automata | BibTeX data for Reachability in Succinct and Parametric One−Counter Automata | Download  (pdf) of Reachability in Succinct and Parametric One−Counter Automata | DOI (10.1007/978-3-642-04081-8_25)

• [5]

  Algorithmic Meta−Theorems

  Stephan Kreutzer

  In International Workshop on Exact and Parameterized Computation (IWPEC). 2008.

  Details about Algorithmic Meta−Theorems | BibTeX data for Algorithmic Meta−Theorems | Download (pdf) of Algorithmic Meta−Theorems

• [6]

  Digraph Decompositions and Monotonocity in Digraph Searching

  Stephan Kreutzer and Sebastian Ordyniak

  In 34th International Workshop on Graph−Theoretic Concepts in Computer Science (WG). 2008.

  Details about Digraph Decompositions and Monotonocity in Digraph Searching | BibTeX data for Digraph Decompositions and Monotonocity in Digraph Searching | Download (pdf) of Digraph Decompositions and Monotonocity in Digraph Searching

• [7]

  On Datalog vs. LFP

  Anuj Dawar and Stephan Kreutzer

  In 35th International Colloquium on Automata‚ Languages and Programming (ICALP). 2008.

  Details about On Datalog vs. LFP | BibTeX data for On Datalog vs. LFP | Download (pdf) of On Datalog vs. LFP

• [8]

  Computing Excluded Minors

  Isolde Adler‚ Martin Grohe and Stephan Kreutzer

  In ACM−SIAM Symposium on Discrete Algorithms (SODA). 2008.

  Details about Computing Excluded Minors | BibTeX data for Computing Excluded Minors | Download (pdf) of Computing Excluded Minors

• [9]

  Digraph Measures: Kelly Decompositions‚ Games‚ and Orderings

  Paul Hunter and Stephan Kreutzer

  In ACM−SIAM Symposium on Discrete Algorithms (SODA). 2007.

  Details about Digraph Measures: Kelly Decompositions‚ Games‚ and Orderings | BibTeX data for Digraph Measures: Kelly Decompositions‚ Games‚ and Orderings

• [10]

  Model theory makes formulas large

  Anuj Dawar‚ Martin Grohe‚ Stephan Kreutzer and Nicole Schweikardt

  In International Colloquium on Automata‚ Languages and Programming (ICALP). Vol. 4596 of Lecture Notes in Computer Science. Pages 913−924. 2007.

  Details about Model theory makes formulas large | BibTeX data for Model theory makes formulas large

• [11]

  Locally Excluding a Minor

  Anuj Dawar‚ Martin Grohe and Stephan Kreutzer

  In Logic in Computer Science (LICS). Pages 270−279. 2007.

  Details about Locally Excluding a Minor | BibTeX data for Locally Excluding a Minor | Download (pdf) of Locally Excluding a Minor

• [12]

  The Complexity of Independence−Friendly Fixpoint Logic

  Julian Bradfield and Stephan Kreutzer

  In Foundations of the Formal Sciences V − Infinite Games (FotFS V). Vol. 11 of Studies in Logic. College Publications‚ London‚ 2007. 2007.

  Details about The Complexity of Independence−Friendly Fixpoint Logic | BibTeX data for The Complexity of Independence−Friendly Fixpoint Logic

• [13]

  DAG−Width and Parity Games

  Dietmar Berwanger‚ Anuj Dawar‚ Paul Hunter and Stephan Kreutzer

  In Symposium on Theoretical Aspects of Computer Science (STACS). 2006.

  Details about DAG−Width and Parity Games | BibTeX data for DAG−Width and Parity Games | Download (pdf) of DAG−Width and Parity Games

• [14]

  Approximation Schemes for First−Order Definable Optimisation Problems

  Stephan Kreutzer Nicole Schweikardt Anuj Dawar and Martin Grohe

  In Logic in Computer Science (LICS). Pages 411−420. 2006.

  Details about Approximation Schemes for First−Order Definable Optimisation Problems | BibTeX data for Approximation Schemes for First−Order Definable Optimisation Problems

• [15]

  The Expressive Power of Two−Variable Least Fixed−Point Logics

  M. Grohe‚ S. Kreutzer and N. Schweikardt

  In Symposium on Mathematical Foundations of Computer Science (MFCS). Pages 422 – 434. Springer. 2005.

  Details about The Expressive Power of Two−Variable Least Fixed−Point Logics | BibTeX data for The Expressive Power of Two−Variable Least Fixed−Point Logics | Download (pdf) of The Expressive Power of Two−Variable Least Fixed−Point Logics

• [16]

  The Complexity of Independence−Friendly Fixpoint Logic

  Julian Bradfield and Stephan Kreutzer

  In Proceedings of the 14th Annual Conference of the European Association for Computer Science Logic (CSL). Vol. 3634 of Lecture Notes in Computer Science. Springer. 2005.

  Details about The Complexity of Independence−Friendly Fixpoint Logic | BibTeX data for The Complexity of Independence−Friendly Fixpoint Logic

• [17]

  Backtracking games and inflationary fixed points

  Anuj Dawar‚ Erich Grädel and Stephan Kreutzer

  In 31st International Colloquium on Automata‚ Languages and Programming (ICALP). 2004.

  Details about Backtracking games and inflationary fixed points | BibTeX data for Backtracking games and inflationary fixed points

• [18]

  Will Deflation Lead to Depletion? On Non−Monotone Fixed−Point Inductions

  E. Grädel and S. Kreutzer

  In IEEE Symp. of Logic in Computer Science (LICS). 2003.

  Details about Will Deflation Lead to Depletion? On Non−Monotone Fixed−Point Inductions | BibTeX data for Will Deflation Lead to Depletion? On Non−Monotone Fixed−Point Inductions

• [19]

  Once upon a time in the west – Determinacy‚ definability and complexity of path games

  D. Berwanger‚ E. Grädel and S. Kreutzer

  In M. Vardi and A. Voronkov, editors, Proceedings of the 10th International Conference on Logic for Programming and Automated Reasoning. Vol. 2850 of Lecture Notes in Computer Science. Pages 226 – 240. Springer. 2003.

  Details about Once upon a time in the west – Determinacy‚ definability and complexity of path games | BibTeX data for Once upon a time in the west – Determinacy‚ definability and complexity of path games

• [20]

  Partial Fixed−Point Logic on Infinite Structures

  S. Kreutzer

  In Annual Conference of the European Association for Computer Science Logic (CSL). Vol. 2471 of Lecture Notes in Computer Science. Springer. 2002.

  Details about Partial Fixed−Point Logic on Infinite Structures | BibTeX data for Partial Fixed−Point Logic on Infinite Structures

• [21]

  Expressive Equivalence of Least and Inflationary Fixed−Point Logic

  S. Kreutzer

  In Proc. of the 17th Symp. on Logic in Computer Science (LICS). Pages 403 – 413. 2002.

  Details about Expressive Equivalence of Least and Inflationary Fixed−Point Logic | BibTeX data for Expressive Equivalence of Least and Inflationary Fixed−Point Logic

• [22]

  Generalising Automaticity to Modal Properties of Finite Structures

  A. Dawar and S. Kreutzer

  In Proc. 22nd Conf. on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). Vol. 2556 of Lecture Notes in Computer Science. Pages 109–120. Springer. 2002.

  Details about Generalising Automaticity to Modal Properties of Finite Structures | BibTeX data for Generalising Automaticity to Modal Properties of Finite Structures

• [23]

  Operational Semantics for Fixed−Point Logics on Constraint Databases

  S. Kreutzer

  In Proceedings of the 8th International Conference on Logic for Programming‚ Artificial Intelligence and Reasoning (LPAR). Vol. 2250 of Lecture Notes in Artificial Intelligence (LNAI). Pages 470 – 484. Springer. 2001.

  Details about Operational Semantics for Fixed−Point Logics on Constraint Databases | BibTeX data for Operational Semantics for Fixed−Point Logics on Constraint Databases

• [24]

  Query Languages for Constraint Databases: First−Order Logic‚ Fixed−Points‚ and Convex Hulls

  S. Kreutzer

  In Proceedings of the 8th International Conference on Database Theory (ICDT). No. 1973. Pages 248–262. Springer. 2001.

  Details about Query Languages for Constraint Databases: First−Order Logic‚ Fixed−Points‚ and Convex Hulls | BibTeX data for Query Languages for Constraint Databases: First−Order Logic‚ Fixed−Points‚ and Convex Hulls

• [25]

  Inflationary Fixed Points in Modal Logics

  A. Dawar‚ E. Grädel and S. Kreutzer

  In Proc. of the 10th Conf. on Computer Science Logic (CSL). Vol. 2142 of Lecture Notes in Computer Science. Pages 277–291. #springer#. 2001.

  Details about Inflationary Fixed Points in Modal Logics | BibTeX data for Inflationary Fixed Points in Modal Logics

• [26]

  Fixed−point Query Languages for Linear Constraint Databases

  S. Kreutzer

  In Proceedings of the 19th ACM Symp. on Principles of Database Systems (PODS)‚ 2000. Pages 116–125. ACM press. 2000.

  Details about Fixed−point Query Languages for Linear Constraint Databases | BibTeX data for Fixed−point Query Languages for Linear Constraint Databases

• [27]

  Descriptive Complexity Theory for Constraint Databases

  E. Grädel and S. Kreutzer

  In Computer Science Logic (CSL). No. 1683. Pages 67 – 82. Springer. 1999.

  Details about Descriptive Complexity Theory for Constraint Databases | BibTeX data for Descriptive Complexity Theory for Constraint Databases

Theses

• [1]

  Pure and Applied Fixed−Point Logics

  S. Kreutzer

  PhD Thesis Dissertation thesis‚ RWTH Aachen. 2002.

  Details about Pure and Applied Fixed−Point Logics | BibTeX data for Pure and Applied Fixed−Point Logics

• [2]

  Descriptive Complexity Theory for Constraint Databases

  S. Kreutzer

  Master's Thesis 1999.

  Details about Descriptive Complexity Theory for Constraint Databases | BibTeX data for Descriptive Complexity Theory for Constraint Databases

Miscellaneous

• [1]

  Digraph Decompositions and Monotonocity in Digraph Searching

  Stephan Kreutzer and Sebastian Ordyniak

  2008.

  Preprint. Slightly revised version of arXiv.org (no arXiv:0802.2228v1)

  Details about Digraph Decompositions and Monotonocity in Digraph Searching | BibTeX data for Digraph Decompositions and Monotonocity in Digraph Searching | Download (pdf) of Digraph Decompositions and Monotonocity in Digraph Searching