Publications of Christof Löding
All Publications
| [CKLV13] |
T. Colcombet, D. Kuperberg, C. Löding, and M. Vanden Boom.
Deciding the weak definability of Büchi definable tree
languages.
In Proceedings of the 22nd Annual Conference of the European
Association for Computer Science Logic, CSL 2013, Leibniz International
Proceedings in Informatics (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2013.
to appear.
(c) Springer. [ pdf | Abstract ] |
| [GLMN13b] |
Pranav Garg, Christof Löding, P. Madhusudan, and Daniel Neider.
Learning universally quantified invariants of linear data
structures.
In Computer Aided Verification - 25th International Conference,
CAV 2013, Saint Petersburg, Russia, July 13-19, 2013. Proceedings, volume
8044 of Lecture Notes in Computer Science, pages 813-829. Springer,
2013. [ pdf | Abstract ] |
| [GLMN13a] |
Pranav Garg, Christof Löding, P. Madhusudan, and Daniel Neider.
ICE: A Robust Learning Framework for Synthesizing Invariants.
Technical report, RWTH Aachen University and University of Illinois
at Urbana-Champaign, 2013. [ pdf | Abstract ] |
| [LL13] |
Martin Lang and Christof Löding.
Modeling and verification of infinite systems with resources.
Logical Methods in Computer Science, 9(4), 2013. [ pdf | Abstract ] |
| [LR13] |
Christof Löding and Stefan Repke.
Decidability Results on the Existence of Lookahead Delegators
for NFA.
In Anil Seth and Nisheeth K. Vishnoi, editors, IARCS Annual
Conference on Foundations of Software Technology and Theoretical Computer
Science (FSTTCS 2013), volume 24 of Leibniz International Proceedings
in Informatics (LIPIcs), pages 327-338, Dagstuhl, Germany, 2013. Schloss
Dagstuhl-Leibniz-Zentrum fuer Informatik. [ pdf | http | Abstract ] |
| [BLO12] |
Stefan Breuers, Christof Löding, and Jörg Olschewski.
Improved Ramsey-based Büchi complementation.
In FoSSaCS 2012, volume 7213 of Lecture Notes in Computer
Science, pages 150-164. Springer, 2012.
(c) Springer. [ Abstract ] |
| [IL12] |
Dimitri Isaak and Christof Löding.
Efficient inclusion testing for simple classes of unambiguous
omega-automata.
Information Processing Letters, 112(14-15):578-582, 2012. [ pdf | http | Abstract ] |
| [Löd12] |
C. Löding.
Basics on tree automata.
In Deepak D'Souza and Priti Shankar, editors, Modern
Applications of Automata Theory. World Scientific, 2012. |
| [LR12] |
Christof Löding and Stefan Repke.
Regularity Problems for Weak Pushdown omega-Automata and
Games.
In Branislav Rovan, Vladimiro Sassone, and Peter Widmayer, editors,
Mathematical Foundations of Computer Science 2012, volume 7464 of
Lecture Notes in Computer Science, pages 764-776. Springer Berlin /
Heidelberg, 2012.
10.1007/978-3-642-32589-2_66. [ pdf | http | Abstract ] |
| [FLZ11] |
W. Fridman, C. Löding, and M. Zimmermann.
Degrees of Lookahead in Context-free Infinite Games.
In Marc Bezem, editor, Computer Science Logic (CSL'11) - 25th
International Workshop/20th Annual Conference of the EACSL, volume 12 of
Leibniz International Proceedings in Informatics (LIPIcs), pages
264-276, Dagstuhl, Germany, 2011. Schloss Dagstuhl-Leibniz-Zentrum fuer
Informatik. [ pdf | ps | http | Abstract ] |
| [Löd11] |
C. Löding.
Infinite games and automata theory.
In Krzysztof R. Apt and Erich Grädel, editors, Lectures in
Game Theory for Computer Scientists. Cambridge University Press, 2011. |
| [BL10] |
Nicolas Bousquet and Christof Löding.
Equivalence and inclusion problem for strongly unambiguous
Büchi automata.
In 4th International Conference on Language and Automata Theory
and Applications, LATA 2010, volume 6031 of Lecture Notes in Computer
Science, pages 118-129. Springer, 2010.
(c) Springer. [ pdf | Abstract ] |
| [CLNW10] |
A. Carayol, C. Löding, D. Niwinski, and I. Walukiewicz.
Choice functions and well-orderings over the infinite binary
tree.
Central European Journal of Mathematics, 8(4):662-682, 2010.
Extended version of [CL07a]. [ pdf | Abstract ] |
| [CHL10] |
K. Chatterjee, F. Horn, and C. Löding.
Obliging games.
In 21st International Conference on Concurrency Theory,
CONCUR 2010, volume 6269 of Lecture Notes in Computer Science, pages
284-296. Springer, 2010. [ pdf | Abstract ] |
| [CL10] |
T. Colcombet and C. Löding.
Regular cost functions over finite trees.
In Twenty-Fifth Annual IEEE Symposium on Logic in Computer
Science, LICS 2010, pages 70-79. IEEE Computer Society, 2010. [ pdf | Abstract ] |
| [FLZ10] |
W. Fridman, C. Löding, and M. Zimmermann.
Degrees of Lookahead in Context-free Infinite Games.
Technical Report AIB-2010-20, RWTH Aachen, December 2010. [ pdf | ps | Abstract ] |
| [NL10] |
Daniel Neider and Christof Löding.
Learning Visibly One-Counter Automata in Polynomial Time.
Technical Report AIB-2010-02, RWTH Aachen, January 2010. [ pdf | ps | Abstract ] |
| [Löd09] |
Christof Löding.
Logic and automata over infinite trees.
Habilitation Thesis, RWTH Aachen, Germany, 2009. [ pdf ] |
| [LW09] |
Christof Löding and Karianto Wong.
On nondeterministic unranked tree automata with sibling
constraints.
In Ravi Kannan and K. Narayan Kumar, editors, IARCS Annual
Conference on Foundations of Software Technology and Theoretical Computer
Science (FSTTCS 2009), volume 4 of Leibniz International Proceedings
in Informatics (LIPIcs), pages 311-322, Dagstuhl, Germany, 2009. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik. [ pdf | http | Abstract ] |
| [CL08b] |
T. Colcombet and C. Löding.
The non-deterministic Mostowski hierarchy and distance-parity
automata.
In Proceedings of the 35th International Colloquium on Automata,
Languages and Programming, ICALP 2008, volume 5126 of Lecture Notes
in Computer Science, pages 398-409. Springer, 2008.
(c) Springer. [ pdf | Abstract ] |
| [CL08a] |
T. Colcombet and C. Löding.
The nesting-depth of disjunctive mu-calculus for tree languages
and the limitedness problem.
In Proceedings of the 17th EACSL Annual Conference on Computer
Science Logic CSL 2008, volume 5213 of Lecture Notes in Computer
Science. Springer, 2008.
(c) Springer. [ pdf | Abstract ] |
| [BCL07] |
A. Blumensath, T. Colcombet, and C. Löding.
Logical theories and compatible operations.
In J. Flum, E. Grädel, and T. Wilke, editors, Logic and
automata: History and Perspectives, pages 72-106. Amsterdam University
Press, 2007.
Note: This version slightly differs from the printed version because
an error in Theorem 3.19 has been corrected. [ pdf ] |
| [CL07a] |
Arnaud Carayol and Christof Löding.
MSO on the infinite binary tree: Choice and order.
In Proceedings of the 16th Annual Conference of the European
Association for Computer Science Logic, CSL 2007, volume 4646 of
Lecture Notes in Computer Science, pages 161-176. Springer, 2007.
(c) Springer. [ pdf | Abstract ] |
| [CL07b] |
T. Colcombet and C. Löding.
Transforming structures by set interpretations.
Logical Methods in Computer Science, 3(2), 2007. [ pdf | Abstract ] |
| [HL07] |
Michael Holtmann and Christof Löding.
Memory Reduction for Strategies in Infinite Games.
In Jan Holub and Jan Zdárek, editors, Implementation and
Application of Automata, 12th International Conference, CIAA 2007, Prague,
Czech Republic, July 16-18, 2007, Revised Selected Papers, volume 4783 of
Lecture Notes in Computer Science, pages 253-264. Springer, 2007. [ pdf | ps | Abstract ] |
| [KL07] |
Wong Karianto and Christof Löding.
Unranked tree automata with sibling equalities and
disequalities.
In Proceedings of the 34th International Colloquium on Automata,
Languages and Programming, ICALP 2007, volume 4596 of Lecture Notes
in Computer Science, pages 875-887. Springer, 2007.
(c)
Springer. [ pdf | Abstract ] |
| [LLS07] |
Christof Löding, Carsten Lutz, and Olivier Serre.
Propositional dynamic logic with recursive programs.
Journal of Logic and Algebraic Programming, 73:51-69, 2007.
Full version of [LS06]. [ pdf | Abstract ] |
| [LS07] |
Christof Löding and Alex Spelten.
Transition Graphs of Rewriting Systems over Unranked
Trees.
In Proceedings of the 32nd International Symposium on
Mathematical Foundations of Computer Science, MFCS 2007, volume 4708 of
Lecture Notes in Computer Science, pages 67-77. Springer, 2007.
Full version (with appendix). A
preliminary
version is accepted at the international conference AutoMathA 2007,
Automata: from Mathematics to Applications, Palermo, Italy.
(c) Springer. [ pdf | ps | Abstract ] |
| [BLS06] |
Vince Bárány, Christof Löding, and Olivier Serre.
Regularity problems for visibly pushdown languages.
In Proceedings of the 23rd Annual Symposioum on Theoretical
Aspects of Computer Science, STACS 2006, volume 3884 of Lecture Notes
in Computer Science, pages 420-431. Springer, 2006.
(c) Springer. [ pdf | ps | Abstract ] |
| [BKL+06] |
M. Benedikt, B. Kuijpers, C. Löding, J. Van den Bussche, and Th. Wilke.
A characterization of first-order topological properties of
planar spatial data.
Journal of the ACM, 53(2):273-305, 2006.
Full version of [BLVdBW04]. [ pdf | Abstract ] |
| [KL06] |
Wong Karianto and Christof Löding.
Unranked tree automata with sibling equalities and
disequalities.
Technical Report AIB-2006-13, RWTH Aachen, October 2006. [ pdf | ps | Abstract ] |
| [Löd06] |
Christof Löding.
Reachability problems on regular ground tree rewriting graphs.
Theory of Computing Systems, 39(2):347-383, 2006. [ pdf | Abstract ] |
| [LS06] |
Christof Löding and Olivier Serre.
Propositional dynamic logic with recursive programs.
volume 3921 of Lecture Notes in Computer Science, pages
292-306. Springer, 2006.
(c) Springer. [ pdf | Abstract ] |
| [CLT05] |
Julien Cristau, Christof Löding, and Wolfgang Thomas.
Deterministic automata on unranked trees.
In Proceedings of the 15th International Symposium on
Fundamentals of Computation Theory, FCT 2005, Lecture Notes in Computer
Science. Springer, 2005.
(c) Springer. [ pdf | Abstract ] |
| [BLVdBW04] |
M. Benedikt, C. Löding, J. Van den Bussche, and Th. Wilke.
A characterization of first-order topological properties of
planar spatial data.
In Proceedings of the 23rd ACM SIGMOD-SIGACT-SIGART Symposium on
Principles of Database Systems, PODS 2004, pages 107-114. ACM Press, 2004. [ pdf | Abstract ] |
| [BSL04] |
Yves Bontemps, Pierre Yves Schobbens, and Christof Löding.
Synthesis of open reactive systems from scenario-based
specifications.
Fundamenta Informaticae, 62(2):139-169, 2004. [ ps | Abstract ] |
| [CL04] |
Th. Colcombet and C. Löding.
On the expressiveness of deterministic transducers over infinite
trees.
In Proceedings of the 21st Annual Symposioum on Theoretical
Aspects of Computer Science, STACS 2004, volume 2996 of Lecture Notes
in Computer Science, pages 428-439. Springer, 2004.
(c) Springer. [ pdf | ps | Abstract ] |
| [LMS04] |
Christof Löding, P. Madhusudan, and Olivier Serre.
Visibly pushdown games.
In Proceedings of the 24th Conference on Foundations of Software
Technology and Theoretical Computer Science, FST TCS 2004, volume 3328 of
Lecture Notes in Computer Science, pages 408-420. Springer, 2004.
(c) Springer. [ pdf | Abstract ] |
| [Löd03] |
Christof Löding.
Infinite graphs generated by tree rewriting.
PhD thesis, RWTH Aachen, Germany, 2003. [ pdf ] |
| [LR03b] |
Christof Löding and Philipp Rohde.
Solving the sabotage game is PSPACE-hard.
Technical Report AIB-05-2003, RWTH Aachen, 2003. [ pdf | Abstract ] |
| [LR03c] |
Christof Löding and Philipp Rohde.
Solving the sabotage game is PSPACE-hard.
In Proceedings of the 28th International Symposium on
Mathematical Foundations of Computer Science, MFCS 2003, volume 2747 of
Lecture Notes in Computer Science, pages 531-540. Springer, 2003.
(c) Springer. [ pdf | ps | Abstract ] |
| [LR03a] |
Christof Löding and Philipp Rohde.
Model checking and satisfiability for sabotage modal logic.
In Proceedings of the 23rd Conference on Foundations of Software
Technology and Theoretical Computer Science, FSTTCS 2003, volume 2914 of
Lecture Notes in Computer Science, pages 302-313. Springer, 2003.
(c) Springer. [ pdf | ps | Abstract ] |
| [Löd02a] |
C. Löding.
Ground tree rewriting graphs of bounded tree width.
In Proceedings of the 19th International Symposium on
Theoretical Aspects of Computer Science, STACS 2002, volume 2285 of
Lecture Notes in Computer Science, pages 559-570. Springer, 2002.
(c) Springer. [ ps | Abstract ] |
| [Löd02b] |
C. Löding.
Model-checking infinite systems generated by ground tree
rewriting.
In Proceedings of the 5th International Conference on
Foundations of Software Science and Computation Structures, FoSSaCS 2002,
volume 2303 of Lecture Notes in Computer Science, pages 280-294.
Springer, 2002.
(c) Springer. [ ps | Abstract ] |
| [Löd01] |
C. Löding.
Efficient minimization of deterministic weak omega-automata.
Information Processing Letters, 79(3):105-109, 2001. [ pdf | Abstract ] |
| [LT00] |
C. Löding and W. Thomas.
Alternating automata and logics over infinite words.
In Proceedings of the IFIP International Conference on
Theoretical Computer Science, IFIP TCS2000, volume 1872 of Lecture
Notes in Computer Science, pages 521-535. Springer, 2000.
(c) Springer. [ ps | Abstract ] |
| [Löd99] |
C. Löding.
Optimal bounds for the transformation of omega-automata.
In Proceedings of the 19th Conference on Foundations of Software
Technology and Theoretical Computer Science, volume 1738 of Lecture
Notes in Computer Science, pages 97-109. Springer, 1999.
(c) Springer. [ ps | Abstract ] |
| [Löd98] |
C. Löding.
Methods for the transformation of omega-automata: Complexity and
connection to second order logic.
Diplomarbeit, Christian-Albrechts-Universität of Kiel, 1998. [ ps ] |