2020

Refereed conference papers

  • Dietrich KuskeThe subtrace order and counting first-order logic.
    CSR 2020, 289-302, Springer Lecture Notes in Computer Science vol. 15129 (2020). (PDF)
  • Dietrich Kuske und Christian SchwarzComplexity of counting first-order logic for the subword order.
    MFCS 2020, 56:1-13, Leibniz International Proceedings in Informatics (2020). (PDF)

2019

Refereed conference papers

  • Dietrich Kuske and Georg Zetzsche: Languages ordered by the subword order.
    FoSSaCS 2019, 348-364, Springer Lecture Notes in Computer Science vol. 11425 (2019). (PDF)
  • Chris KöcherReachability Problems on Partially Lossy Queue Automata.
    RP 2019, 149-163, Springer Lecture Notes in Computer Science vol. 11674 (2019). (PDF)

2018

Fully refereed papers

  • Milka Hutagalung, Norbert Hundeshagen, Dietrich Kuske, Martin Lange, and Etienne Lozes: Multi-buffer simulations: decidability and complexity. (PDF)
    Information and Computation 262(2), 280-310.
  • Chris KöcherDietrich Kuske, and Elena PrianychnykovaThe inclusion structure of partially lossy queue monoids and their trace submonoids(PDF)
    RAIRO - Theoretical Informatics and Applications 52(1), 55-86.
  • Dietrich Kuske, Jiamou Liu, and Anastasia Moskvina: Infinite and bi-infinite words with decidable monadic theories. (PDF)
    Logical Methods in Computer Science 14(3).

Refereed conference papers

  • Chris KöcherRational, Recognizable, and Aperiodic Sets in the Partially Lossy Queue Monoid.
    STACS 2018, 45:1-45:14, Leibniz International Proceedings in Informatics vol. 96 (2018). (PDF)
  • Dietrich Kuske and Nicole Schweikardt: Gaifman normal forms for counting extensions of first-order logic.
    ICALP 2018, 133:1-14, Leibniz International Proceedings in Informatics (2018). (PDF)
  • Faried Abu ZaidDietrich Kuske, and Peter Lindner: Climbing up the elementary complexity classes with theories of automatic structures.
    CSL 2018, 3:1-16, Leibniz International Proceedings in Informatics (2018). (PDF)
  • Faried Abu ZaidChris KöcherThe Cayley-Graph of the Queue Monoid: Logic and Decidability.
    FSTTCS 2018, 9:1-9:17 Leibniz International Proceedings in Informatics vol. 122 (2018). (PDF)
  • Faried Abu ZaidUniformly Automatic Classes of Finite Structures.
    FSTTCS 2018, 10:1-10:21 Leibniz International Proceedings in Informatics vol. 122 (2018). (PDF)

2017

Fully refereed papers

  • Georg Zetzsche, Dietrich Kuske, and Markus Lohrey: On Boolean closed full trios and rational Kripke frames.  (PDF)
    Theory of Computing Systems 60(3), 438-472.
  • Benedikt Bollig, Dietrich Kuske, and Roy MennickeThe Complexity of Model Checking Multi-Stack Systems. Theory of Computing Systems 60(4), 695-736. (PDF)
  • Martin HuschenbettDietrich Kuske, and Georg Zetzsche: The monoid of queue actions. Semigroup Forum 95(3), 475-508. (PDF)

Refereed conference papers

  • Chris Köcher and Dietrich KuskeThe transformation monoid of a partially lossy queue. Computer Science in Russia 2017, 191-205, Springer Lecture Notes in Computer Science vol. 10304 (2017). (PDF)
  • Dietrich Kuske and Nicole Schweikardt: First-order logic with counting: At least, weak Hanf normal forms always exist and can be computed!. LICS 2017. (PDF)
  • Faried Abu Zaid, Anuj Dawar, Erich Grädel, and Wied Pakusa: Definability of Summation Problems for Abelian Groups and Semigroups. LICS 2017. (PDF)
  • Faried Abu Zaid, Erich Grädel, and Frederic Reinhardt: Advice Automatic Structures and Uniformly Automatic Classes. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017), 2017. (PDF)

2016

Refereed conference papers

  • Milka Hutagalung, Norbert Hundeshagen, Dietrich Kuske, Martin Lange, and Etienne Lozes: Two-buffer simulation games. (PDF)
    CASSTING 2016, Electronic Proceedings in Theoretical Computer Science vol. 220, 27-38.
  • Milka Hutagalung, Norbert Hundeshagen, Dietrich Kuske, Martin Lange, and Etienne Lozes: Multi-buffer simulations for trace language inclusion. (PDF)
    GandALF 2016, Electronic Proceedings in Theoretical Computer Science vol. 226, 213-227.
  • Dietrich Kuske, and Olena Prianychnykova: The trace monoids in the queue monoid and in the direct product of two free monoids. (PDF)
    DLT 2016, 256--267, LNCS vol. 9840.
  • Lucas Heimberg, Dietrich Kuske, and Nicole Schweikardt: Hanf normal form for first-order logic with unary counting quantifiers. (PDF)
    LICS 2016, 277-286, ACM.
  • Igor Potapov, Olena Prianychnykova, and Sergey Verlan:
    Insertion-Deletion Systems over Relational Words. RP 2016, 177-191, LNCS vol. 9899.

2015

Refereed conference papers

  • Dietrich Kuske, Peter Habermehl: On Presburger arithmetic extended with modulo counting quantifiers. (PDF).
    Foundations of Software Science and Computation Structures (FoSSaCS) 2015, 375-389, LNCS vol. 9034.
  • Dietrich Kuske, Jiamou Liu, and Anastasia Moskvina: Infinite and bi-infinite words with decidable monadic theories. (PDF)
    Computer Science Logic (CSL), 472-486, 2015.
 

2014

Fully refereed papers

  • Dietrich KuskeIsomorphisms of scattered automatic linear orders. (PDF)
    Theoretical Computer Science.

Refereed conference papers 

  • Martin Huschenbett, Manfred Kufleitner: Ehrenfeucht-Fraïssé Games on Omega-Terms. (<media>PDF</media>, arXiv)
    Symposium on Theoretical Aspects of Computer Science (STACS) 2014, 374–385, LIPIcs vol. 25.
  • Martin HuschenbettDietrich Kuske, Georg Zetzsche: The monoid of queue actions. (<media>PDF</media>, arXiv)
    Mathematical Foundations of Computer Science (MFCS) 2014, 340–351, LNCS vol. 8634.
  • Roy MennickeModel Checking Concurrent Recursive Programs using Local Temporal Logics. (<media>PDF</media>)
    Mathematical Foundations of Computer Science (MFCS) 2014, 438–450, LNCS vol. 8634.
 

2013

Fully refereed papers

  • Dietrich Kuske, Jiamou Liu, Markus Lohrey: The isomorphism problem for ω-automatic trees. (PDF)
    Journal of Pure and Applied Logic 164, 30–48.
  • Dietrich Kuske, Jiamou Liu, Markus Lohrey: The isomorphism problem on classes of automatic structures with transitive relations. (PDF)
    Transactions of the AMS 365, 5103–5151.
  • Ruth Corran, Michael Hoffmann, Dietrich Kuske, Rick Thomas: On the automaticity of singular Artin monoids of finite type. (PDF)
    International Journal of Computer Mathematics 90(6), 1197–1222.
  • Martin HuschenbettModels for Quantitative Distributed Systems and Multi-valued Logics. (<media>PDF</media>)
    International Journal of Computer Mathematics 90(6), 1223–1246.
  • Martin Huschenbett, Alexander Kartzow, Jiamou Liu, Markus Lohrey: Tree-Automatic Well-Founded Trees. (<media>PDF</media>)
    Logical Methods in Computer Science 9(2:10), 1–44.
  • Roy MennickePropositional Dynamic Logic with Converse and Repeat for Message-Passing Systems. (PDF)
    Logical Methods in Computer Science 9(2:12), 1–35.
  • Markus Lohrey, Sebastian Maneth, Roy MennickeXML Tree Structure Compression with RePair. (PDF)
    Information Systems 38(8), 1150–1167.

Refereed conference papers 

  • Benedikt Bollig, Dietrich KuskeRoy MennickeThe Complexity of Model Checking Multi-Stack Systems. (PDF)
  • Logic in Computer Science (LICS) 2013, 163–172.
  • Lucas Heimberg, Dietrich Kuske, Nicole Schweikardt: An optimal Gaifman normal form construction for structures of bounded degree. (PDF)
    Logic in Computer Science (LICS) 2013, 63-72.
  • Martin Huschenbett, Jiamou Liu: A Polychromatic Ramsey Theory for Ordinals. (<media>PDF</media>)
    Mathematical Foundations of Computer Science (MFCS) 2013, 559–570, LNCS vol. 8087.
  • Martin HuschenbettThe Rank of Tree-Automatic Linear Orderings. (<media>PDF</media>)
    Symposium on Theoretical Aspects of Computer Science (STACS) 2013, 586–597, LIPIcs vol. 20.
  • Dietrich KuskeLogical aspects of the lexicographic order on 1-counter languages. (PDF)
    Mathematical Foundations of Computer Science (MFCS) 2013, 619–630, LNCS vol. 8087.
 

2012

Fully refereed papers

  • Benedikt Bollig, Dietrich Kuske: An optimal construction of Hanf sentences. (PDF)
    Journal of Applied Logic 10, 179–186.

Refereed conference papers

  • Martin HuschenbettWord Automaticity of Tree Automatic Scattered Linear Orderings Is Decidable. (<media>PDF</media>, arXiv)
    Computability in Europe (CiE) 2012, 314–323, Springer Lecture Notes in Computer Science vol 7318.
  • Roy MennickePropositional Dynamic Logic with Converse and Repeat for Message-Passing Systems. (PDF)
    CONCUR 2012, 531–546, Springer Lecture Notes in Computer Science vol. 7454.
  • Dietrich KuskeIsomorphisms of scattered automatic linear orders. (PDF)
    Computer Science Logic (CSL) 2012, 455–469, LIPIcs vol. 16.
 

2011

Fully refereed papers

  • Martin HuschenbettA Kleene-Schützenberger Theorem for Trace Series over Bounded Lattices. (<media>PDF</media>)
    Fundamenta Informaticae 112(2–3), 171–191.
  • Dietrich Kuske(Un)countable and (non)effective versions of Ramsey's theorem. (PDF)
    In: Martin Grohe, Johann A. Makowsky (eds.): Model Theoretic Methods in Finite Combinatorics. Contemporary Mathematics 558, 467–487.
  • Dietrich Kuske, Ingmar Meinecke: Construction of tree automata from regular expressions. (PDF)
    RAIRO 45(3), 437–470.
  • Dietrich Kuske, Markus Lohrey: Automatic structures of bounded degree revisited. (PDF)
    Journal of Symbolic Logic 76(4), 1352–1380.

Refereed conference papers

  • Ruth Corran, Michael Hoffmann, Dietrich Kuske, Rick Thomas: Singular Artin monoids of finite type are automatic. (PDF)
    Language and Automata Theory and Applications (LATA) 2011, 310–322, 249-260, Springer Lecture Notes in Computer Science vol. 6638.
  • Martin HuschenbettModels for Quantitative Distributed Systems and Multi-valued Logics. (<media>PDF</media>)
    Language and Automata Theory and Applications (LATA) 2011, 310–322, Springer Lecture Notes in Computer Science vol. 6638.
  • Dietrich Kuske, Thomas Weidner: Size and computation of injective tree automatic presentations. (PDF)
    Mathematical Foundations of Computer Science (MFCS) 2011, 424–435, Springer Lecture Notes in Computer Science vol. 6907.
  • Markus Lohrey, Sebastian Maneth, Roy MennickeTree Structure Compression with RePair. (PDF)
    Data Compression Conference (DCC) 2011, 353–362, © IEEE Computer Society.

Other publications

  • Dietrich KuskeWhere automatic structures benefit from weighted automata. (PDF)
    Algebraic Foundations of Computer Science (Bozapalidis Festschrift), 257–271, Lecture Notes in Computer Science vol. 7020.
 

2010

Fully refereed papers

  • Benedikt Bollig, Dietrich Kuske, Ingmar Meinecke: Propositional Dynamic Logic for Message-Passing Systems. (PDF)
    Logical Methods in Computer Science 6(3:16), 1–31.
  • Paul Gastin, Dietrich KuskeUniform satisfiability problem for local temporal logics over Mazurkiewicz traces. (PDF)
    Information and Computation 208, 797–816.
  • Dietrich Kuske, Markus Lohrey: Some natural decision problems in automatic graphs. (PDF)
    Journal of Symbolic Logic 75(2), 678–710.

Refereed conference papers

  • Martin Huschenbett: A Kleene-Schützenberger Theorem for Trace Series over Bounded Lattices. (<media>PDF</media>)
    Non-Classical Models of Automata and Applications (NCMA) 2010, 99–111, books@ocg.at vol. 263.
  • Dietrich KuskeIs Ramsey's theorem ω-automatic? (PDF)
    Symposium on Theoretical Aspects of Computer Science (STACS) 2010, 537–548.
  • Dietrich Kuske, Jiamou Liu, Markus Lohrey: The Isomorphism Problem for ω-Automatic Trees. (PDF)
    Computer Science Logic (CSL) 2010, 396–410, Springer Lecture Notes in Computer Science vol. 6247.
  • Dietrich Kuske, Jiamou Liu, Markus Lohrey: The Isomorphism Problem on Classes of Automatic Structures.
    Logic in Computer Science (LICS) 2010, 160–169, © IEEE Computer Society.