Publications by Dietrich Kuske

Fully refereed papers

1. Schützenberger's theorem on formal power series follows from Kleene's theorem.
   Theoretical Computer Science 401 (2008) 243-248.
2. Distributed Muller automata and logics. (with )
   Information and Computation 206 (2008) 1084-1094.
3. First-order and counting theories of omega-automatic structures. (with )
   Journal of Symbolic Logic 73 (2008) 129-150.
   AMS-Review
4. Uniform satisfiability in PSPACE for local temporal logics over Mazurkiewicz traces. (with )
   Fundamenta Informaticae 80 (2007), 169-197.
5. On communicating automata with bounded channels. (with and )
   Fundamenta Informaticae 80 (2007), 147-167.
6. Weighted asynchronous cellular automata.
   Theoretical Computer Science 374 (2007), 127-148.
   AMS-Review
7. A Kleene theorem and model checking algorithms for existentially bounded communicating automata. (with and )
   Information and Computation 204 (2006), 920-956.
   AMS-Review
8. Skew and infinitary formal power series. (with )
   Theoretical Computer Science 366 (2006), 199-227.
   AMS-Review
9. On graph products of automatic and biautomatic monoids. (with )
   Semigroup forum 72 (2006), 337-352.
   AMS-Review
10. Logical aspects of Cayley graphs: the monoid case. (with )
    International Journal of Algebra and Computation 16 (2006), 307-340.
    AMS-Review
11. Theories of orders on the set of words.
    Theoretical Informatics and Applications 40 (2006), 53-74.
    AMS-Review
12. Logical aspects of Cayley graphs: the group case. (with )
    Annals of Pure and Applied Logic 131 (2005), 263-286.
    AMS-Review
13. Branching automata with costs - a way of reflecting parallelism in costs. (with )
    Theoretical Computer Science 328 (2004), 53-75.
    AMS-Review
14. Regular sets of infinite message sequence charts.
    Information and Computation 187 (2003), 80-109.
    AMS-Review
15. Decidable first-order theories of one-step rewriting in trace monoids. (with )
    Theory of Computing Systems 38 (2005), 39-81.
    AMS-Review
16. On random relational structures. (with )
    Journal of Combinatorial Theory - Series A 102/2 (2003), 241-254.
    AMS-Review
17. Distributive lattices with a decidable monadic second order theory.
    Algebra Universalis 48 (2002), 183-207.
    AMS-Review
18. Towards a language theory for infinite N-free pomsets.
    Theoretical Computer Science 299 (2003), 347-386.
    AMS-Review
19. The topology of Mazurkiewicz traces. (with )
    Theoretical Computer Science 305 (2003), 237-258.
    AMS-Review
20. Pomsets for local trace languages. (with )
    Journal of Automata, Languages, and Combinatorics 7 (2002), 187-224.
    AMS-Review
21. Recognizable languages in divisibility monoids. (with )
    Mathematical Structures in Computer Science 11 (2001), 743-770.
    AMS-Review
22. Generic automorphisms of the universal partial order. (with )
    Proceedings of the AMS 129 (2001), 1939-1948.
    AMS-Review
23. Complementary closed relational clones are not always Krasner clones. (with , , and )
    Algebra Universalis 45 (2001), 155-160.
    AMS-Review
24. Asynchronous cellular automata for pomsets. (with and )
    Theoretical Computer Science 247 (2000), 1-38.
    AMS-Review
25. Symmetries of the partial order of traces.
    Order 16 (1999), 133-148.
    AMS-Review
26. On homogeneous semilattices and their automorphism groups. (with and )
    Order 16 (1999), 31-56.
    AMS-Review
27. On existentially first order definable languages and their relation to NP. (with )
    Theoretical Informatics and Applications 33 (1999), 259-270.
    AMS-Review
28. Recognizable and logically definable languages of infinite computations in concurrent automata. (with )
    International Journal of Foundations of Computer Science 9 (1998), 295-314.
29. Topology for computations of concurrent automata. (with )
    International Journal of Algebra and Computation 8 (1998), 327-362.
    AMS-Review
30. Representation of computations of concurrent automata by dependence orders. (with )
    Theoretical Computer Science 174 (1997), 67-96.
    AMS-Review
31. Trace languages definable with modular quantifiers. (with )
    Developments in Language Theory 1995, 386-395. World Scientific (1996).
    AMS-Review
32. Languages and Logical Definability in Concurrency Monoids . (with )
    Computer Science Logic 1995, 233-251. © Springer Lecture Notes in Computer Science vol. 1092 (1996).
    AMS-Review

Refereed conference papers

1. Construction of tree automata from regular expressions. (with )
   Developments in language theory 2008, 491-503, Springer Lecture Notes in Computer Science vol. 5257 (2008).
2. Euler paths and ends in automatic and recursive graphs. (with )
   Automata and Formal Languages 2008, 245-256, Hungarian Academy of Sciences (2008).
3. Hamiltonicity of automatic graphs. (with )
   IFIP TCS 2008, 445-459, Springer (2008).
4. Compatibility of Shelah and Stupp's and of Muchnik's iteration with fragments of monadic second order logic.
   STACS 2008, 467-478, IFIB Schloss Dagstuhl (2008).
   
5. Propositional Dynamic Logic for Message-Passing Systems. (with )
   FSTTCS 2007, 303-315, © Springer Lecture Notes in Computer Science vol. 4855 (2007).
   
6. Almost every domain is universal. (with )
   MFPS 2007, Electronic Notes in Theoretical Computer Science vol. 173, 103-119 (2007).
7. Monadic chain logic over iterations and applications to push-down systems. (with )
   LICS 2006, 91-100, © IEEE Computer Society (2006).
8. First-order and counting theories of omega-automatic structures. (with )
   FoSSaCS 2006, 322-336, © Springer Lecture Notes in Computer Science vol. 3921 (2006).
   AMS-Review
9. Weighted asynchronous cellular automata
   STACS 2006, 685-696, © Springer Lecture Notes in Computer Science vol. 3884 (2006).
   AMS-Review
10. Uniform satisfiability problem for local temporal logics over Mazurkiewicz traces (with )
    CONCUR 2005, 533-547, © Springer Lecture Notes in Computer Science vol. 3653 (2005).
    AMS-Review
11. Snapshot Verification (with )
    TACAS 2005, 510-525, © Springer Lecture Notes in Computer Science vol. 3440 (2005).
12. The rôle of the complementarity relation in Watson-Crick automata and sticker systems. (with )
    DLT 2004, 272-283, © Springer Lecture Notes in Computer Science vol. 3340 (2004).
    AMS-Review
13. Is Cantor's theorem automatic?
    LPAR 2003, 332-343, © Springer Lecture Notes in Computer Science vol. 2850 (2003).
14. Satisfiability and model checking for MSO-definable temporal logics are in PSPACE. (with )
    CONCUR 2003, 222-236. © Springer Lecture Notes in Computer Science vol. 2761 (2003).
    AMS-Review
15. Branching automata with costs - a way of reflecting parallelism in costs. (with )
    CIAA 2003 150-162. © Springer Lecture Notes in Computer Science vol. 2759 (2003).
    AMS-Review
16. Skew and infinitary formal power series. (with )
    ICALP 2003 426-438. © Springer Lecture Notes in Computer Science vol. 2719 (2003).
    AMS-Review
17. Decidable Theories of Cayley-graphs. (with )
    STACS 2003, 463-474. © Springer Lecture Notes in Computer Science vol. 2607 (2003).
    AMS-Review
18. On the theory of one-step rewriting in trace monoids. (with )
    ICALP 2002, 752-763. © Springer Lecture Notes in Computer Science vol. 2380 (2002).
    AMS-Review
19. Some relatives of automatic and hyperbolic groups. (with ).
    Proceedings of the Thematic Term on Semigroups, Algorithms, Automata and Languages, 379--406. World Scientific. (2002).
    AMS-Review
20. A further step towards a theory of regular MSC languages.
    STACS 2002, 489-500. © Springer Lecture Notes in Computer Science vol. 2285 (2002).
    AMS-Review
21. Recognizable sets of N-free pomsets are monadically axiomatizable.
    DLT 2001, 206-216. © Springer Lecture Notes in Computer Science vol. 2295 (2001).
    AMS-Review
22. Divisibility monoids: presentation, word problem, and rational languages.
    FCT 2001, 227-239. © Springer Lecture Notes in Computer Science vol. 2138 (2001).
    AMS-Review
23. A model theoretic proof of Büchi-type theorems and first order logic for N-free pomsets.
    STACS 2001, 443-454. © Springer Lecture Notes in Computer Science vol. 2010 (2001).
    AMS-Review
24. The boundary between decidable and undecidable fragments of the fluent calculus. (with )
    LPAR 2000, 436-450. © Springer Lecture Notes in Computer Science vol. 1955 (2000).
    AMS-Review
25. Emptiness is decidable for asynchronous cellular machines.
    CONCUR 2000, 536-551. © Springer Lecture Notes in Computer Science vol. 1877 (2000).
    AMS-Review
26. Pomsets for local trace languages: Recognizability, logic, and Petri nets. (with )
    CONCUR 2000, 426-441. © Springer Lecture Notes in Computer Science vol. 1877 (2000).
    AMS-Review
27. Infinite series-parallel pomsets: logic and languages.
    ICALP 2000, 648-662. © Springer Lecture Notes in Computer Science vol. 1853 (2000).
    AMS-Review
28. On recognizable languages in left divisibility monoids. (with )
    FCT 1999, 246-257. © Springer Lecture Notes in Computer Science vol. 1684 (1999).
    AMS-Review
29. Asynchronous cellular and asynchronous automata for pomsets.
    CONCUR 1998, 517-532. © Springer Lecture Notes in Computer Science vol. 1466 (1998).
    AMS-Review
30. On existentially first order definable languages and their relation to NP. (with )
    ICALP 1998, 17-28. © Springer Lecture Notes in Computer Science vol. 1443 (1998).
    AMS-Review
31. Dependence orders for computations of concurrent automata. (with )
    STACS 1995, 467-478. © Springer Lecture Notes in Computer Science vol. 900 (1995).
    AMS-Review
32. Nondeterministic automata with concurrency relations and domains.
    CAAP 1994, 202-217. © Springer Lecture Notes in Computer Science vol. 787 (1998).
    AMS-Review
33. Representation of domains by residuum systems.
    Workshop domains. Techn. Report TH Darmstadt (1994).

Invited contributions

1. Traces, series-parallel posets, and pictures: a weighted study (with )
   Handbook of Weighted Automata. To appear, 2008.
   
2. A Kleene Theorem for a Class of Communicating Automata with Effective Algorithms (invited talk by ). (with )
   DLT 2004. 30-48, © Springer Lecture Notes in Computer Science vol. 3340 (2004).
   AMS-Review
3. Automata with concurrency relations - a survey. (with )
   In: J.M. Abe, J.I. da Silva Filho (eds.) Logic applied to Technology, 152-172. IOS Press (2002).
   updated version of an article with the same title that appeared in P.Gastin, A. Petit (editors), Workshop on algebraic and syntactic aspects of concurrency, 119-140. LITP 95/48 (1995).
   AMS-Review

Thesis

1. Modelle nebenläufiger Prozesse - Monoide, Residuensysteme und Automaten.
   Dissertation, Universität Essen (1994).
2. Contributions to a Trace Theory beyond Mazurkiewicz Traces.
   Habilitationsschrift, TU Dresden (2000).

Unpublished papers

1. Automatic structures of bounded degree revisited. (with )
   (2008).
   
2. Weighted and unweighted trace automata.
3. Singular Artin monoids of finite type are automatic. (with ).

List of coauthors