Stephan Kreutzer : Publications

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

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)

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

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‚

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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