Publikationen

See the individual homepages of the members of this group.

Below, only publications since 2004 are listed.

Books and special volumes

M. Droste, W. Kuich, H. Vogler (eds.): Handbook of Weighted Automata, EATCS Monographs in Theoretical Computer Science, Springer-Verlag, 2009.
M. Droste, Z. Esik, H. Vogler (eds.): Special issue of Theoretical Computer Science on "Weighted Automata", approved.
M. Droste, L. Fuchs, L. Strüngmann, K. Tent (eds.): Groups and Model Theory: A Conference in Honor of Rüdiger Göbel's 70th Birthday, Contemporary Mathematics, American Mathematical Society, in print.
M. Droste, H. Vogler (eds.): Special issue of Acta Cybernetica, Workshop on "Weighted Automata: Theory and Applications" (Leipzig, May 2010), vol. 20, no. 2, 2011.
M. Droste, H. Vogler (eds.): Special issue of Acta Cybernetica, Workshop on "Weighted Automata: Theory and Applications" (Dresden, May 2008), vol. 19, no. 2, 2009.
M. Droste, H. Vogler (eds.): Special issue of Journal of Automata, Languages and Combinatorics, Workshop on "Weighted Automata: Theory and Applications" (Leipzig, March 2006), vol. 12, no. 4, 2007.
M. Droste, H. Vogler (eds.): Special issue of Journal of Automata, Languages and Combinatorics, Workshop on "Weighted Automata: Theory and Applications" (Dresden, June 2004), vol. 10, no. 2 & 3, 2005.

2012

G. Braun, S. Pokutta: Rigid abelian groups and the probabilistic method, Contemporary Mathematics (2011) accepted.
G. Braun, S. Pokutta: An algebraic approach to symmetric extended formulations, Proc ISCO 2012 accepted.
M. Droste, D. Kuske: Weighted automata, chapter 4 (invited) in Handbook: "Automata: from Mathematics to Applications" (J.-E. Pin, ed.), European Mathematical Society, to appear.
M. Droste, I. Meinecke, B. Seselja, A. Tepavcevic: Coverings and decompositions of semiring-weighted finite transition systems, in: Fuzzy Semirings with Applications to Automata Theory (by J. Ahsan, J. Mordeson, M. Shabir), chapter 11 (invited), Springer, 2012.
M. Droste, B. Pibaljommee: Weighted nested word automata and logics over strong bimonoids, in 17th International Conference on Implementation and Application of Automata (CIAA 2012), Lecture Notes in Computer Science, Springer, 2012, to appear.
M. Droste, H. Vogler: Weighted automata and multi-valued logics over arbitrary bounded lattices, Theoret. Comp. Science 418 (2012), 14-36.

2011

G. Braun, L. Strüngmann, Breaking up finite automata presentable torsion-free abelian groups, IJAC (2011) no 8, 1463-1472.
G. Braun, S. Pokutta, Random half-integer polytopes, Operations Research Letters 39 (2011) no 3, 204-207.
G. Braun, J. Trlifaj: Strong submodules of almost projective modules, Pacific Journal of Mathematics 254 (2011) no. 1, 73-87.
M. Droste, V.V. Bludov, A.M.W. Glass: Automorphism groups of totally ordered sets: a retrospective survey, Mathematica Slovaca 61 (2011), 373-388.
M. Droste, R. Göbel: Countable random p-groups with prescribed Ulm-invariants, Proc. Amer. Math. Soc. 139 (2011), 3203-3216.
M. Droste, D. Götze, S. Märcker, I. Meinecke: Weighted tree automata over valuation monoids and their characterizations by weighted logics, in: Algebraic Foundations in Computer Science (eds. W. Kuich, G. Rahonis), Lecture Notes in Computer Sciences, vol. 7020, Springer, 2011, pp. 30-55.
M. Droste, I. Meinecke: Regular expressions on average and in the long run, in 15th International Conference on Implementation and Application of Automata (CIAA 2010), Lecture Notes in Computer Science vol.6482, Springer, 2011, pp. 211-221.
M. Droste, I. Meinecke: Weighted automata and regular expressions over valuation monoid, selected papers of CIAA 2010, Intern. J. of Foundations of Comp. Science 22 (2011), 1829-1844.
M. Droste, I. Meinecke, B. Seselja, A. Tepavcevic: A cascade decomposition of weighted finite transition systems, in: Non-Classical Models of Automata and Applications (NCMA 2011), Österreichische Computer Gesellschaft, 2011, pp. 137-152.
M. Droste, K. Quaas: A Kleene-Schützenberger theorem for weighted timed automata, Theoret. Comp. Science 412 (2011), 1140-1153.
M. Droste, J.K. Truss: The uncountable cofinality of the automorphism group of the countable universal distributive lattice, Demonstratio Mathematica 44 (2011), 473-479.
M. Droste, H. Vogler: Weighted logics for unranked tree automata, Theory of Computing Systems 48 (2011), 23-47.
I. Fichtner: Weighted picture automata and weighted logics, Theory of Computing Systems 48 (2011), 48-78.
M. Huschenbett: Models for quantitative distributed systems and multi-valued logics, in: Language and Automata Theory and Applications (LATA), Lecture Notes in Computer Science vol. 6638, Springer, 2011, pp. 310-322.
H. Jänicke, T. Weidner, D. Chung, R.S. Laramee, P. Townsend, and M. Chen: Visual Reconstructability as a Quality Metric for Flow Visualization, Computer Graphics Forum (CGF), Vol. 30, No. 3, 2011, 781-790 (Proc. EuroVis 2011).
D. Kuske and I. Meinecke: Construction of Tree Automata from Regular Expressions, RAIRO-Theor. Inf. Appl. 45(3): 347-370, 2011.
D. Kuske, T. Weidner: Size and Computation of Injective Tree Automatic Presentations, Mathematical Foundations of Computer Science (MFCS) 2011, 424-435, Springer Lecture Notes in Computer Science vol. 6907.
I. Meinecke: Valuations of weighted automata: Doing it in a rational way, In: W. Kuich, G. Rahonis (eds.). "Algebraic Foundations in Computer Science", Lecture Notes in Computer Sciences, vol. 7020, Springer, 2011, pp. 309-346.
K. Quaas, D. Kirsten: Recognizability of the Support of Recognizable Series over the Semiring of the Integers is Undecidable, in Information Processing Letters, 111(10), 2011, pp. 500-502.
K. Quaas: MSO Logics for Weighted Timed Automata. In Formal Methods in System Design, 38(3), 2011, pp. 193-222.
K. Quaas: On the Interval-Bound Problem for Weighted Timed Automata. In Language and Automata Theory and Applications (LATA 2011), Springer LNCS, Volume 6638 (2011), pp. 452-464.

2010

B. Bollig, D. Kuske, and I. Meinecke: Propositional Dynamic Logic for Message-Passing Systems. Logical Methods in Computer Science, 6(3): 1-31, 2010.
G. Braun, S. Pokutta, Rank of random half-integral polytopes (extended abstract), Electronic Notes in Discrete Mathematics 36 (2010), 415-422.
M. Droste, M. Ciric, J. Ignjatovic, H. Vogler: Determinization of weighted finite automata over strong bimonoids, Information Sciences 180 (2010), 3497-3520.
M. Droste, I. Meinecke: Describing average- and longtime-behavior by weighted MSO logics, in: "Mathematical Foundations of Computer Science (MFCS)", Lecture Notes in Computer Science vol. 6281, Springer, 2010, pp. 537-548.
M. Droste, G. Rahonis: Weighted automata and weighted logics on infinite words, Izvestiya VUZ. Matematika 54 (2010), 26-45.
M. Droste, I. Rivin: On extension of coverings , Bull. London Math. Soc. 42 (2010), 1044-1054.
M. Droste, T. Stüber, H. Vogler: Weighted finite automata over strong bimonoids, Information Sciences 180 (2010), 156-166.
M. Droste, H. Vogler: Kleene and Büchi theorems for weighted automata and multi-valued logics over arbitrary bounded lattices, in 14th Int. Conf. on Developments in Language Theory (DLT), Lecture Notes in Computer Science vol. 6224, Springer, 2010, pp. 160-172.
M. Droste, G.-Q. Zhang: Bifinite Chu spaces, Logical Methods in Computer Science vol.6, no.1, 2010, 1-20.
M. Huschenbett: A Kleene-Schützenberger theorem for trace series over bounded lattices, in: Non-Classical Models of Automata and Applications (NCMA), Österreichische Computer Gesellschaft, 2010, pp. 99-111.
D. Kirsten: On the Complexity of the Relative Inclusion Star Height Problem,
Advances in Computer Science and Engineering 5 (2010), 173-211.
D. Kuske, M. Lohrey: Some natural problems in automatic graphs. Journal of Symbolic Logic 75(2) 678-710 (2010).
Ch. Mathissen: Transductions and Weighted Logics for Texts, Theoretical Computer Science , 411, issue 3 (2010), pp. 631-659.
K. Quaas: Kleene-Schützenberger and Büchi Theorems for Weighted Timed Automata, Dissertation, Universität Leipzig, 2010.

2009

M. Droste, W. Kuich, H. Vogler (eds.): Handbook of Weighted Automata, EATCS Monographs in Theoretical Computer Science, Springer-Verlag, 2009.
M. Droste, H. Vogler (eds.): Special issue of Acta Cybernetica, Workshop on "Weighted Automata: Theory and Applications" (Dresden, May 2008), vol. 19, no. 2, 2009.
M. Droste, P. Gastin: Weighted automata and weighted logics, in: Handbook of Weighted Automata (M. Droste, W. Kuich, H. Vogler, eds.), EATCS Monographs in Theoretical Computer Science, chapter 5, Springer-Verlag, 2009.
M. Droste, R. Göbel: Stabilizers of direct composition series, Algebra Universalis 62 (2009), 209-237.
M. Droste, W. Kuich: Semirings and formal power series, in: Handbook of Weighted Automata (M. Droste, W. Kuich, H. Vogler, eds.), EATCS Monographs in Theoretical Computer Science, chapter 1, Springer-Verlag, 2009.
M. Droste, G. Rahonis: Weighted automata and weighted logics with discounting, Theoretical Computer Science 410 (2009), 3481-3494.
M. Droste, J.K. Truss: Uncountable cofinalities of automorphism groups of linear and partial orders, Algebra Universalis 62 (2009), 75-90.
D. Kirsten and S. Lombardy: Deciding Unambiguity and Sequentiality of Polynomially Ambiguous min-plus Automata, In S. Albers and J.-Y. Marion, editors, STACS'09 proceedings, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany, 2009.
D. Kirsten: The Support of a Recognizable Series Over a Zero-sum Free, Commutative Semiring is Recognizable, In V. Diekert and D. Nowotka, editors, DLT'09, Proceedings, volume 5583 of Lecture Notes in Computer Science, Springer-Verlag, Berlin, 2009.
D. Kirsten: An Algebraic Characterization of Semirings for which the Support of Every Recognizable Series is Recognizable, in R. Kralovic and D. Niwinski (eds.), MFCS'09, Proceedings, to appear in Lecture Notes in Computer Science, Springer-Verlag, Berlin, 2009.
D. Kuske: Weighted and unweighted trace automata. Acta Cybernetica 19 (2009) 393-410.
D. Kuske: Theories of automatic structures and their complexity, CAI 2009. 81-98, (c) Springer Lecture Notes in Computer Science vol. 5725 (2009).
D. Kuske, M. Lohrey: Automatic structures of bounded degree revisited. Computer Science Logic 2009, 364-378, Springer Lecture Notes in Computer Science vol. 5771 (2009)
D. Kuske, M.Lohrey: Hamiltonicity of automatic graphs, IFIP TCS 2008, 445-459, Springer (2009).
D. Kuske, I. Fichtner, I. Meinecke: Traces, series-parallel posets, and pictures: a weighted study. in: Handbook of Weighted Automata, 2009
Ch. Mathissen: Weighted Automata and Weighted Logics over tree-like Structures, Dissertation, Universität Leipzig, 2009
Ch. Mathissen: Existential MSO over Two Successors Is Strictly Weaker than over Linear Orders, Theoretical Computer Science, 410 (2009), pp. 3982-3987.
I. Meinecke: A weighted mu-calculus on words. In: "Developments in Language Theory (DLT 2009)", Lecture Notes in Computer Science, vol. 5583, Springer, 2009, pp. 384-395.
K. Quaas: Weighted Timed MSO Logics, in: Developments in Language Theory (DLT), Lecture Notes in Comp. Science vol. 5583, Springer 2009, pp. 419-430.
K. Quaas: On the Supports of Recognizable Timed Series, Formal Modelling and Analysis of Timed Systems (FORMATS 2009), 243-257, Springer LNCS, Volume 5813.

2008

M. Droste, P. Gastin: On aperiodic and star-free formal power series in partially commuting variables, Theory of Computing Systems 42 (2008), 608-631.
M. Droste, R. Göbel, S. Pokutta: Absolute graphs with prescribed endomorphism monoids, Semigroup Forum 76 (2008), 256-267.
M. Droste, R. Gray, J.K. Truss Construction of some uncountable 2-arc-transitive bipartite graphs, Order 25 (2008), 349-357
M. Droste, W. Kuich, G. Rahonis Multi valued MSO logics over words and trees, Fundamenta Informaticae 84 (2008), 305-327.
M. Droste, C. Holland, G. Ulbrich On full groups of measure-preserving and ergodic transformations with uncountable cofinalities, Bulletin London Math. Soc. 40 (2008), 463-472.
M. Droste, F. Huang, G.-Q. Zhang: A monoidal category of bifinite Chu spaces, in: 1st Int. Conf. on Foundations of Informatics, Computing and Software (FICS), Electronic Notes in Theoretical Computer Science 212 (2008), 285-297.
M. Droste, K. Quaas: A Kleene-Schützenberger theorem for weighted timed automata, in: 11th Int. Conf. on Foundations of Software Science and Computation Structures (FoSSaCS), Lecture Notes in Comp. Science vol. 4962, Springer 2008, pp. 142-156.
M. Droste, J. Sakarovitch, H. Vogler: Weighted automata with discounting, Information Processing Letters 108 (2008), 23-28.
M. Droste, G. Zhang: Random event structures, International Journal of Software and Informatics 2 (2008), 77-88.
D. Kirsten: A burnside approach to the termination of Mohri's algorithm for polynomially ambiguous min-plus-automata, RAIRO - Theoretical Informatics and Applications, special issue on "Journées Montoises d'Informatique Théorique 2006 (JM'06)", 42(3):553-581, 2008.
D. Kuske: 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).
D. Kuske: Schützenberger's theorem on formal power series follows from Kleene's theorem, Theoretical Computer Science 401 (2008) 243-248.
D.Kuske, B.Bollig: Distributed Muller automata and logics, Information and Computation 206 (2008) 1084-1094.
D. Kuske, M.Lohrey: Euler paths and ends in automatic and recursive graphs, Automata and Formal Languages 2008, 245-256, Hungarian Academy of Sciences (2008).
D. Kuske, M.Lohrey: Hamiltonicity of automatic graphs, IFIP TCS 2008, 445-459, Springer (2009).
D.Kuske, M.Lohrey: First-order and counting theories of omega-automatic struct ures, Journal of Symbolic Logic 73 (2008), 129-150.
D. Kuske, I.Meinecke: Construction of tree automata from regular expressions, Developments in language theory 2008, 491-503, Springer Lecture Notes in Computer Science vol. 5257 (2008).
Ch. Mathissen: Weighted logics for nested words and algebraic formal power series (pdf), Proc. of the 35th International Colloquium on Automata, Languages and Programming (ICALP), Reykjavik. Part II.
Lecture Notes in Computer Science, vol. 5126, © Springer, 2008, pp. 221-232.
EATCS Award "Best student ICALP paper" (track B)

2007

M. Droste, H. Vogler (eds.): Special issue of Journal of Automata, Languages and Combinatorics, Workshop on "Weighted Automata: Theory and Applications" (Leipzig, March 2006), vol. 12 no. 4, 2007.
M.Droste, P. Gastin: Weighted automata and weighted logics, Theoret. Comp. Science (special issue of ICALP '05), 380 (2007), 69-86. Full version: pdf
M. Droste, Ch. Holland: Normal Subgroups of B_uAut(Ω), Applied Categorical Structures 15 (2007), 153-162.
M. Droste, D. Kuske: Almost every domain is universal, 23rd Conf. on the Mathematical Foundations of Programming Semantics (MFPS), Electronic Notes in Theoretical Computer Science vol. 173, 103-119 (2007).
M. Droste, U. Püschmann: On weighted Büchi automata with order-complete weights, Intern. J. of Algebra and Computation, 17 (2007), 235-260.
M. Droste, G. Rahonis: Weighted automata and weighted logics with discounting, 12th Int. Conf. on Implementation and Application of Automata (CIAA), Lecture Notes in Comp. Science vol. 4783, Springer 2007, pp. 73-84.
M. Droste, H. Vogler: Weighted logics for XML Full version: ps
M. Droste, G. Zhang: Bifinite Chu spaces, in: 2nd Conf. on Algebra and Coalgebra in Computer Science (CALCO), Lecture Notes in Comp. Science vol. 4624, Springer, 2007, pp. 179-193.
D. Kirsten: Desert Automata V. On the Complexity of the Relative Inclusion Star Height Problem, Manuscript, 2007, accepted at Advances in Computer Science and Engineering in 2009, to appear in 2010.
D. Kuske: Weighted asynchronous cellular automata, Theoretical Computer Science, 374 (2007), 127-148
B. Bollig, D. Kuske, and Ingmar Meinecke: Propositional Dynamic Logic for Message-Passing Systems, FSTTCS 2007, 303-315, Springer Lecture Notes in Computer Science vol. 4855 (2007).
P. Gastin and D. Kuske: Uniform satisfiability in PSPACE for local temporal logics over Mazurkiewicz traces, Fundamenta Informaticae 80, 169-197, 2007.
B. Genest, D. Kuske, A. Muscholl: On communicating automata with bounded channels, Fundamenta Informaticae 80, 147-167, 2007.
Ch. Mathissen: Definable Transductions and Weighted Logics for Texts, Proc. of the 11th Int. Conf. on Developments in Language Theory (DLT), Turku. Lecture Notes in Computer Science, vol. 4588, Springer, 2007, pp. 324-336.
I. Mäurer: Characterizations of Recognizable Picture Series, Theoretical Computer Science 374, pp. 214-228, 2007
I. Meinecke, B. Bollig: Weighted Distributed Systems and Their Logics, In: "Symposium on Logical Foundations of Computer Science (LFCS 2007)", Lecture Notes in Computer Science, vol. 4514, Springer, 2007, pp. 54-68.

2006

M. Droste, J. Kari, P. Steinby: Observations on the smoothness properties of real functions computed by weighted finite automata, Fundamenta Informaticae, 73 (2006), 99-106.
M. Droste, D. Kuske: Skew and infinitary formal power series, Theoret. Comp. Science 366 (2006), 199-227
M. Droste, G. Rahonis: Weighted automata and weighted logics on infinite words, 10th Int. Conf. on Developments in Language Theory (DLT), Lecture Notes in Computer Science vol. 4036, Springer, 2006, pp. 49-58.
M. Droste, J. Truss: On representing words in the automorphism group of the random graph, Journal of Group Theory 9, (2006) 815-836.
M. Droste, H. Vogler: Weighted tree automata and weighted logics, Theoret. Comp.Science 366 (2006), 228-247.
D.Kirsten: Distance Desert Automata and Star Height Substitutions. Habilitationsschrift, Universität Leipzig, Fakultät für Mathematik und Informatik, 2006.
D.Kuske: Theories of orders an the set of words. Theoretical Informatics and Applications 40 (2006), 53-74.
D. Kuske: Weighted asynchronous cellular automata STACS 2006, 685-696, © Springer Lecture Notes in Computer Science vol. 3884 (2006).
D. Kuske, E. Fohry: On graph products of automatic and biautomatic monoids. Semigroup forum 72 (2006), 337-352.
D.Kuske, B.Genest, A.Muscholl: A Kleene theorem and model checking algorithms for existentially bounded communicating automata. Information and Computation 204 (2006), 920-956.
D. Kuske, M. Lohrey: Monadic chain logic over iterations and applications to push-down systems. LICS 2006, 91-100, IEEE Computer Society (2006)
D. Kuske, M. Lohrey: Logical aspects of Cayley graphs: the monoid case. International Journal of Algebra and Computation 16 (2006), 307-340.
D. Kuske, M. Lohrey: First-order and counting theories of omega-automatic structures FoSSaCS 2006, 322-336, © Springer Lecture Notes in Computer Science vol. 3921 (2006).
I. Mäurer: Weighted Picture Automata and Weighted Logics. STACS 2006, LNCS 3884, pp. 313-324, Springer Berlin, 2006.
I. Meinecke: Weighted Logics for Traces. In: "Computer Science - Theory and Applications: First International Computer Science Symposium in Russia, CSR 2006, St. Petersburg", LNCS 3976, Springer, 2006, pp. 235-246.

2005

M. Droste, H. Vogler (eds.): Special issue of Journal of Automata, Languages and Combinatorics, Workshop on "Weighted Automata - Theory and Applications" (Dresden, June 2004), vol. 10, no. 2 & 3, 2005.
M.Droste: Universal homogeneous causal sets, Journal of Mathematical Physics 46 (2005), 122503 1-10. Full version
M.Droste, P. Gastin: Weighted automata and weighted logics, Automata, Languages and Programming (32nd ICALP, Lissabon), Lecture Notes in Comp. Science, vol. 3580, Springer, 2005, pp. 513-525.
M. Droste, R. Göbel: Uncountable cofinalities of permutation groups, J. London Math. Soc. (2) 71 (2005), 335-344.
M. Droste, W.Ch. Holland: Generating automorphism groups of chains. Forum Mathematicum 17 (2005), 699-710.
M. Droste, C. Pech, H. Vogler: A Kleene theorem for weighted tree automata, Theory of Computing Systems, 38 (2005), 1-38.
D. Kuske, P. Gastin: Uniform satisfiability problem for local temporal logics over Mazurkiewicz traces. CONCUR 2005, 533-547, © Springer Lecture Notes in Computer Science vol. 3653 (2005).
D.Kuske, B.Genest, A.Muscholl, D.Peled: Snapshot Verification. TACAS 2005, 510-525, © Springer Lecture Notes in Computer Science vol. 3440 (2005).
D. Kuske, M. Lohrey: Decidable first-order theories of one-step rewriting in trace monoids, Theory of Computing Systems 38 (2005), 39-81.
D.Kuske, M.Lohrey: Logical aspects of Cayley graphs: the group case. Annals of Pure and Applied Logic 131 (2005), 263-286.
I. Mäurer: Recognizable and Rational Picture Series. Conference on Algebraic Informatics, Thessaloniki. 2005
I. Mäurer, D. Kirsten: On the Determinization of Weighted Automata Journal of Automata, Languages and Combinatorics, Special issue "Selected papers of the workshop Weighted Automata: Theory and Applications (Dresden, June 1-5 2004)"; Vol. 10 (2005) Number 2.
I. Meinecke: The Hadamard Product of Sequential-Parallel Series. Journal of Automata, Languages and Combinatorics, Special issue "Selected papers of the workshop Weighted Automata: Theory and Applications (Dresden, June 1-5 2004)"; Vol. 10 (2005) Number 2.

2004

D.Kuske, B. Genest, A. Muscholl: A Kleene Theorem for a Class of Communicating Automata with Effective Algorithms (invited talk by A. Muscholl). DLT 2004. 30-48, © Springer Lecture Notes in Computer Science vol. 3340 (2004).
D.Kuske, I.Meinecke: Branching automata with costs - a way of reflecting parallelism in costs. Theoretical Computer Science 328 (2004), 53-75.
D.Kuske, P.Weigelt: The rôle of the complementarity relation in Watson-Crick automata and sticker systems. DLT 2004, 272-283, © Springer Lecture Notes in Computer Science vol. 3340 (2004).
I.Meinecke: Weighted Branching Automata - Combining Concurrency and Weights. Dissertation, TU Dresden.