Logic and
Theory of
Discrete Systems

Informatik 7

Publications of Christof Löding

[LT16]
Christof Löding, Andreas Tollkötter: Transformation Between Regular Expressions and omega-Automata. MFCS 2016: 88:1-88:13
[url]
[LW16]
Christof Löding, Sarah Winter: Uniformization Problems for Tree-Automatic Relations and Top-Down Tree Transducers. MFCS 2016: 65:1-65:14
[url]
[FJLW16]
Emmanuel Filiot, Ismaël Jecker, Christof Löding, Sarah Winter: On Equivalence and Uniformisation Problems for Finite Transducers. ICALP 2016: 125:1-125:14.
[CLS16]
Arnaud Carayol, Christof Löding, Olivier Serre: Automata on Infinite Trees with Equality and Disequality Constraints Between Siblings. In Proceedings of the 31st Annual IEEE Symposium on Logic in Computer Science (LiCS 2016).
[LMN16]
Christof Löding, P. Madhusudan, Daniel Neider: Abstract Learning Frameworks for Synthesis. TACAS 2016: 167-185.
[Löd15]
Christof Löding. Simplification Problems for Deterministic Pushdown Automata on Infinite Words. Int. J. Found. Comput. Sci., 26(8). World Scientific. 2015. (Full version of [Löd14].)
[GLMN15]
Pranav Garg, Christof Löding, P. Madhusudan, Daniel Neider. Quantified data automata for linear data structures: a register automaton model with applications to learning invariants of programs manipulating arrays and lists. Formal Methods in System Design 47(1): 120-157 (2015)
[KLLL15]
Lukasz Kaiser, Martin Lang, Simon Leßenich and Christof Löding. A Unified Approach to Boundedness Properties in MSO. In Stephan Kreutzer (ed.). 24th EACSL Annual Conference on Computer Science Logic (CSL 2015) 41. 2015, 441–456.
[url]
[CL15]
Arnaud Carayol, Christof Löding. Uniformization in Automata Theory. In Logic, Methodology and Philosophy of Science - Proceedings of the 14th Internatinal Congress, Nancy, 2011. Peter Schroeder-Heister, Gerhard Heinzmann, Wilfrid Hodges, Pierre Edouard Bour, editors. College Publications, 2015.
[pdf]
[GLMN14]
Pranav Garg, Christof Löding, P. Madhusudan, Daniel Neider. ICE: A Robust Framework for Learning Invariants. CAV 2014: 69-87
[ pdf ]
[TGLR14]
Simon Tenbusch, James Gross, Christof Löding, Frank G. Radmacher. Guaranteeing Stability and Delay in Dynamic Networks Based on Infinite Games. MASS 2014: 461-469
[ pdf ]
[LLM14]
Martin Lang, Christof Löding, Amaldev Manuel. Definability and Transformations for Cost Logics and Automatic Structures. MFCS (1) 2014: 390-401
[ pdf ]
[Löd14]
Christof Löding. Decision Problems for Deterministic Pushdown Automata on Infinite Words. AFL 2014: 55-73
[LW14]
Christof Löding, Sarah Winter. Synthesis of Deterministic Top-down Tree Transducers from Automatic Tree Relations. GandALF 2014: 88-101
[CKLV13] Thomas Colcombet, Denis Kuperberg, Christof Löding, and Michael 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 ]
[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 ]
[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 ]
[LL13] Martin Lang and Christof Löding. Modeling and verification of infinite systems with resources. Logical Methods in Computer Science, 9(4), 2013.
[ pdf ]
[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 ]
[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.
[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 ]
[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 ]
[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 ]
[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 ]
[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 ]
[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 ]
[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 ]
[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 ]
[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 ]
[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 ]
[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 ]
[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 ]
[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 ]
[CL07b] T. Colcombet and C. Löding. Transforming structures by set interpretations. Logical Methods in Computer Science, 3(2), 2007.
[ pdf ]
[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 ]
[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 ]
[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 ]
[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 ]
[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 ]
[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 ]
[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 ]
[Löd06] Christof Löding. Reachability problems on regular ground tree rewriting graphs. Theory of Computing Systems, 39(2):347-383, 2006.
[ pdf ]
[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 ]
[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 ]
[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 ]
[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 ]
[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 ]
[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 ]
[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 ]
[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 ]
[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 ]
[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 ]
[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 ]
[Löd01] C. Löding. Efficient minimization of deterministic weak omega-automata. Information Processing Letters, 79(3):105-109, 2001.
[ pdf ]
[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 ]
[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 ]
[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 ]
FaLang translation system by Faboba