2018

Journal Articles

  1. Lukas Fleischer and Manfred Kufleitner
    The complexity of weakly recognizing morphisms
    RAIRO-Theor. Inf. Appl.. 2018.
    DOI
  2. Lukas Fleischer and Manfred Kufleitner
    Green’s Relations in Deterministic Finite Automata
    Theory Comput. Syst.. Springer, 2018.
    DOI
  3. Stefan Edelkamp and Armin Weiß
    QuickMergesort: Practically Efficient Constant-Factor Optimal Sorting
    arXiv eprints. abs/1804.10062 2018.
  4. Manfred Kufleitner and Jan Philipp Wächter
    The Word Problem for Omega-Terms over the Trotter-Weil Hierarchy
    Theory of Computing Systems. 62:682–738. Springer, 2018.
    DOI
  5. Manfred Kufleitner and Tobias Walter
    Level two of the quantifier alternation hierarchy over infinite words
    Theory of Computing Systems. 62:467–480. Springer, 2018.
  6. Daniele D’Angeli , Emanuele Rodaro and Jan Philipp Wächter
    On the Structure Theory of Partial Automaton Semigroups
    ArXiv e-prints. abs/1811.09420 2018.
    PDF
  7. Daniele D’Angeli , Emanuele Rodaro and Jan Philipp Wächter
    Orbit Expandability of Automaton Semigroups and Groups
    ArXiv e-prints. abs/1812.07359 2018.
    PDF
  8. Géraud Sénizergues and Armin Weiß
    The isomorphism problem for finite extensions of free groups is in PSPACE
    ArXiv e-prints. 2018.
  9. Stefan Edelkamp , Armin Weiß and Sebastian Wild
    QuickXsort - A Fast Sorting Scheme in Theory and Practice
    arXiv eprints. abs/1811.01259 2018.

Conference Articles

  1. Lukas Fleischer
    The Intersection Problem for Finite Semigroups
    DLT 2018, Proceedings, volume 11088 of LNCS, pages 318–329. Springer, 2018.
  2. Lukas Fleischer and Manfred Kufleitner
    Testing Simon’s congruence
    MFCS 2018, Proceedings, volume 117 of LIPIcs, pages 62:1–62:13. Dagstuhl Publishing, 2018.
    DOI
  3. Lukas Fleischer
    On the Complexity of the Cayley Semigroup Membership Problem
    CCC 2018, Proceedings, volume 102 of LIPIcs, pages 25:1–25:12. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018.
    DOI
  4. Lukas Fleischer and Manfred Kufleitner
    The Intersection Problem for Finite Monoids
    STACS 2018, Proceedings, volume 96 of LIPIcs, pages 30:1–30:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018.
    DOI
  5. Géraud Sénizergues and Armin Weiß
    The Isomorphism Problem for Finite Extensions of Free Groups Is In PSPACE
    45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 139:1–139:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018.
    DOI

Book Chapters

  1. Alexei Myasnikov , Svetla Vassileva and Armin Weiß
    Log-Space Complexity of the Conjugacy Problem in Wreath Products
    Infinite Group Theory, Chapter 12, pages 215-236. World Scientific, 2018.
    DOI

2017

Journal Articles

  1. Funda Gul and Armin Weiß
    On the dimension of matrix embeddings of torsion-free nilpotent groups
    J. Algebra. 477:516–539. 2017.
    DOI
  2. Lukas Fleischer , Manfred Kufleitner and Alexander Lauser
    The Half-Levels of the FO2 Alternation Hierarchy
    Theory Comput. Syst.. 61(2):352–370. Springer, 2017.
    DOI
  3. Volker Diekert , Florent Martin , Géraud Sénizergues and Pedro V. Silva
    Equations Over Free Inverse Monoids with Idempotent Variables
    Theory Comput. Syst.. 61:494–520. 2017.
    DOI
  4. Volker Diekert and Tobias Walter
    Characterizing classes of regular languages using prefix codes of bounded synchronization delay
    International Journal of Algebra and Computation. 27:561–590. 2017.
    DOI
  5. Alexei G. Myasnikov and Armin Weiß
    \text{TC}^0 \text{TC}^0 circuits for algorithmic problems in nilpotent groups
    ArXiv e-prints. abs/1702.06616 2017.
    PDF
  6. Daniele D’Angeli , Emanuele Rodaro and Jan Philipp Wächter
    On the complexity of the word problem for automaton semigroups and automaton groups
    Advances in Applied Mathematics. 90():160 - 187. 2017.
    DOI
    AAM
  7. Daniele D’Angeli , Emanuele Rodaro and Jan Philipp Wächter
    Automaton Semigroups and Groups: on the Undecidability of Problems Related to Freeness and Finiteness
    ArXiv e-prints. abs/1712.07408 2017.
    PDF
  8. Tobias Walter
    Parikh-reducing Church–Rosser representations for some classes of regular languages
    Theoretical Computer Science. 702:34 - 47. 2017.
    DOI
  9. Volker Diekert , Alexei G. Myasnikov and Armin Weiß
    Amenability of Schreier graphs and strongly generic algorithms for the conjugacy problem
    J. Symb. Comput.. 83:147–165. 2017.
    DOI

Conference Articles

  1. Volker Diekert and Lukas Fleischer
    Church-Rosser Systems, Codes with Bounded Synchronization Delay and Local Rees Extensions
    WORDS 2017, Proceedings, volume 10432 of LNCS, pages 6–16. Springer, 2017.
    DOI
  2. Lukas Fleischer and Manfred Kufleitner
    Green’s Relations in Finite Transformation Semigroups
    CSR 2017, Proceedings, volume 10304 of LNCS, pages 112–125. Springer, 2017.
    DOI
  3. Alexei Miasnikov , Svetla Vassileva and Armin Weiß
    The conjugacy problem in free solvable groups and wreath product of abelian groups is in \text{TC}^0 \text{TC}^0
    Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Kazan, Russia, June 8-12, 2017, Proceedings, pages 217–231. 2017.
    PDF
    DOI
  4. Volker Diekert and Murray Elder
    Solutions of Twisted Word Equations, EDT0L Languages, and Context-Free Groups
    44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), pages 96:1–96:14. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2017.
    DOI
  5. Alexei G. Myasnikov and Armin Weiß
    TC^0 ^0 Circuits for Algorithmic Problems in Nilpotent Groups
    42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, Proceedings, volume 83 of LIPIcs, pages 23:1–23:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017.
    DOI

Theses

  1. Jonathan Kausch
    The parallel complexity of certain algorithmic problems in group theory
    Dissertation, Institut für Formale Methoden der Informatik, Universität Stuttgart, 2017.

Book Chapters

  1. Volker Diekert and Armin Weiß
    Context-Free Groups and Bass-Serre Theory
    Algorithmic and Geometric Topics Around Free Groups and Automorphisms, Advanced Courses in Mathematics - CRM Barcelona, Birkhäuser, 2017.
    DOI

2016

Journal Articles

  1. Volker Diekert and Jonathan Kausch
    Logspace Computations in Graph Products
    Journal of Symbolic Computation. 75(C):94–109. Academic Press, Inc., July 2016.
    DOI
  2. Stefan Edelkamp and Armin Weiß
    BlockQuicksort: How Branch Mispredictions don’t affect Quicksort
    ArXiv e-prints. abs/1604.06697 2016.
    PDF
  3. Volker Diekert , Artur Jeż and Wojciech Plandowski
    Finding all solutions of equations in free groups and monoids with involution
    Information and Computation. 251:263–286. 2016.
    DOI
  4. Volker Diekert and Manfred Kufleitner
    A Survey on the Local Divisor Technique
    Theoretical Computer Science. 610:13–23. 2016.
    DOI
  5. Volker Diekert , Alexei G. Myasnikov and Armin Weiß
    Conjugacy in Baumslag’s group, generic case complexity, and division in power circuits
    Algorithmica. 74:961-988. 2016.
    PDF
    DOI
  6. Laura Ciobanu , Volker Diekert and Murray Elder
    Solution sets for equations over free groups are EDT0L languages
    International Journal of Algebra and Computation. 26:843–886. 2016.
    DOI
  7. Volker Diekert and Armin Weiß
    QuickHeapsort: Modifications and Improved Analysis
    Theory Comput. Syst.. 59(2):209–230. 2016.
    PDF
    DOI

Conference Articles

  1. Lukas Fleischer and Manfred Kufleitner
    Operations on Weakly Recognizing Morphisms
    DCFS 2016, Proceedings, volume 9777 of LNCS, pages 126–137. Springer, 2016.
    DOI
  2. Stefan Edelkamp and Armin Weiß
    BlockQuicksort: Avoiding Branch Mispredictions in Quicksort
    24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, volume 57 of LIPIcs, pages 38:1–38:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.
    PDF
    DOI
  3. Manfred Kufleitner and Tobias Walter
    Level Two of the Quantifier Alternation Hierarchy over Infinite Words
    CSR, volume 9691 of Lecture Notes in Computer Science, pages 223–236. Springer, 2016.
    DOI
  4. Volker Diekert , Artur Jeż and Manfred Kufleitner
    Solutions of Word Equations Over Partially Commutative Structures
    43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 127:1–127:14. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2016.
    DOI
  5. Volker Diekert and Tobias Walter
    Characterizing classes of regular languages using prefix codes of bounded synchronization delay
    43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume of Leibniz International Proceedings in Informatics (LIPIcs), pages 129:1–129:13. 2016.
    DOI
  6. Manfred Kufleitner and Jan Philipp Wächter
    The Word Problem for Omega-Terms over the Trotter-Weil Hierarchy
    CSR 2016, Proceedings, pages 237–250. Springer, 2016.
    DOI

Book Chapters

  1. Armin Weiß
    A Logspace Solution to the Word and Conjugacy problem of Generalized Baumslag-Solitar Groups
    Algebra and Computer Science, volume 677 of Contemporary Mathematics, pages 185–212. American Mathematical Society, 2016.
    PDF

Theses

  1. Tobias Walter
    Local Divisors in Formal Languages
    Dissertation, Institut für Formale Methoden der Informatik, Universität Stuttgart , 2016.
    PDF

2015

Journal Articles

  1. Manfred Kufleitner and Tobias Walter
    One quantifier alternation in first-order logic with modular predicates
    RAIRO-Theor. Inf. Appl.. 49(1):1–22. 2015.
    DOI
  2. Volker Diekert and Manfred Kufleitner
    Omega-rational expressions with Bounded Synchronization Delay
    Theory of Computing Systems. 56:686–696. Springer-Verlag, 2015.
    DOI
  3. Volker Diekert , Manfred Kufleitner , Klaus Reinhardt and Tobias Walter
    Regular Languages Are Church-Rosser Congruential
    Journal of the ACM. 62:39:1–39:20. ACM, 2015.
    DOI
  4. Volker Diekert and Tobias Walter
    Asymptotic Approximation for the Quotient Complexities of Atoms
    Acta Cybernetica. 22:349–357. 2015.
    PDF
  5. Volker Diekert , Olga Kharlampovich and Atefeh Mohajeri Moghaddam
    SLP compression for solutions of equations with constraints in free and hyperbolic groups
    International Journal of Algebra and Computation. 25:81–112. 2015.
    DOI

Conference Articles

  1. Lukas Fleischer and Manfred Kufleitner
    Efficient Algorithms for Morphisms over Omega-Regular Languages
    FSTTCS 2015, Proceedings, volume 45 of LIPIcs, pages 112–124. Dagstuhl Publishing, 2015.
    DOI
  2. Volker Diekert , Alexei G. Myasnikov and Armin Weiß
    Amenability of Schreier Graphs and Strongly Generic Algorithms for the Conjugacy Problem
    Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC 2015, Bath, United Kingdom, July 06 - 09, 2015, pages 141–148. 2015.
    PDF
    DOI
  3. Laura Ciobanu , Volker Diekert and Murray Elder
    Solution sets for equations over free groups are EDT0L languages
    Proc. 42nd International Colloquium Automata, Languages and Programming (ICALP 2015), Part II, Kyoto, Japan, July 6-10, 2015, volume 9135 of Lecture Notes in Computer Science, pages 134-145. Springer, 2015.
  4. Volker Diekert , Florent Martin , Géraud Sénizergues and Pedro V. Silva
    Equations over free inverse monoids with idempotent variables
    Proc. 10th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russia, July 13-17, 2015, volume 9139 of Lecture Notes in Computer Science, pages 173-188. Springer, 2015.
  5. Volker Diekert , Anca Muscholl and Igor Walukiewicz
    A Note on Monitors and Büchi Automata
    Theoretical Aspects of Computing - ICTAC 2015 - 12th International Colloquium Cali, Colombia, October 29-31, 2015, Proceedings, pages 39–57. 2015.
    DOI
  6. Volker Diekert
    More Than 1700 1700 Years of Word Equations
    Algebraic Informatics - 6th International Conference, CAI 2015, Stuttgart, Germany, September 1-4, 2015. Proceedings, pages 22–28. 2015.
    DOI

Theses

  1. Armin Weiß
    On the Complexity of Conjugacy in Amalgamated Products and HNN Extensions
    Dissertation, Institut für Formale Methoden der Informatik, Universität Stuttgart, 2015.
    PDF

2014

Journal Articles

  1. Volker Diekert and Martin Leucker
    Topology, monitorable properties and runtime verification
    Theoretical Computer Science. 537:29–41. 2014.
    DOI
  2. Manfred Kufleitner and Jan Philipp Wächter
    Two-Variable Ehrenfeucht-Fraisse Games over Omega-Terms
    ArXiv e-prints. abs/1411.0593 2014.
    PDF

Conference Articles

  1. Manfred Kufleitner
    Star-Free Languages and Local Divisors
    DCFS 2014, Proceedings, volume 8614 of Lecture Notes in Computer Science, pages 23–28. Springer, 2014.
  2. Volker Diekert , Artur Jeż and Wojciech Plandowski
    Finding All Solutions of Equations in Free Groups and Monoids with Involution
    Computer Science Symposium in Russia 2014, CSR 2014, Moscow, Russia, June 7-11, 2014. Proceedings, volume 8476 of Lecture Notes in Computer Science, pages 1–15. Springer, 2014.
    DOI
  3. Lukas Fleischer , Manfred Kufleitner and Alexander Lauser
    Block Products and Nesting Negations in \text{FO}^2 \text{FO}^2
    CSR 2014, Proceedings, volume 8476 of LNCS, pages 176–189. Springer, 2014.
    DOI
  4. Volker Diekert , Alexei G. Myasnikov and Armin Weiß
    Conjugacy in Baumslag’s Group, Generic Case Complexity, and Division in Power Circuits
    Latin American Theoretical Informatics Symposium, pages 1-12. 2014.
    DOI
  5. Stefan Edelkamp and Armin Weiß
    QuickXsort: Efficient Sorting with n \log n -
		  1.399n + o(n) n \log n - 1.399n + o(n) Comparisons on Average
    CSR, pages 139-152. 2014.
    DOI
  6. Volker Diekert and Jonathan Kausch
    Logspace computations in graph products
    Proc. International Symposium on Symbolic and Algebraic Computation, ISSAC ’14, Kobe, Japan, July 23-25, 2014, pages 138-145. 2014.

2013

Journal Articles

  1. Volker Diekert , Jürn Laun and Alexander Ushakov
    Efficient algorithms for highly compressed data: The word problem in Higman’s group is in P
    International Journal of Algebra and Computation. 22(8) 2013.
    DOI
  2. Jürn Laun
    Efficient algorithms for highly compressed data: The word problem in Higman’s group is in P
    Theory of Computing Systems. :1-29. Springer US, 2013.
    DOI
  3. Stefan Edelkamp and Armin Weiß
    QuickXsort: Efficient Sorting with n \log n -
		  1.399n + o(n) n \log n - 1.399n + o(n) Comparisons on Average
    ArXiv e-prints. abs/1307.3033 2013.
    PDF
  4. Volker Diekert and Armin Weiß
    Context-Free Groups and Their Structure Trees
    International Journal of Algebra and Computation. 23:611–642. 2013.
    DOI
  5. Volker Diekert and Armin Weiß
    Context-Free Groups and Bass-Serre Theory
    ArXiv e-prints. 2013.
    PDF
  6. Volker Diekert and Jonathan Kausch
    Logspace computations in graph products
    arXiv eprints. 2013.
    PDF

Conference Articles

  1. Manfred Kufleitner and Alexander Lauser
    Quantifier Alternation in Two-Variable First-Order Logic with Successor Is Decidable
    30th International Symposium on Theoretical Aspects of Computer Science (STACS) 2013, Conference Proceedings, volume 20 of Leibniz International Proceedings in Informatics (LIPIcs), pages 305–316. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2013.
    PDF
    DOI
  2. Volker Diekert and Armin Weiß
    QuickHeapsort: Modifications and Improved Analysis
    Computer Science Symposium in Russia (CSR) 2013, Conference Proceedings, pages 24-35. 2013.
    PDF
    DOI
  3. Stefan Edelkamp , Amr Elmasry , Jyrki Katajainen and Armin Weiß
    Weak Heaps and Friends: Recent Developments
    Combinatorial Algorithms - 24th International Workshop, IWOCA 2013, Rouen, France, July 10-12, 2013, Revised Selected Papers, pages 1–6. 2013.
    DOI

Technical Reports

  1. Manfred Kufleitner and Alexander Lauser
    Nesting Negations in \text{FO}^2 \text{FO}^2 over Finite Words
    Technical Report Computer Science, Document number: 2013/07. University of Stuttgart, September 2013.
    PDF
    WWW

Books

  1. Volker Diekert , Manfred Kufleitner and Gerhard Rosenberger
    Elemente der Diskreten Mathematik
    De Gruyter, 2013.
  2. Volker Diekert , Manfred Kufleitner and Gerhard Rosenberger
    Diskrete algebraische Methoden
    De Gruyter, 2013.

2012

Journal Articles

  1. Volker Diekert , Manfred Kufleitner and Benjamin Steinberg
    The Krohn-Rhodes Theorem and Local Divisors
    Fundamenta Informaticae. 116:65–77. 2012.
    PDF
    DOI
  2. Manfred Kufleitner and Alexander Lauser
    The Join of the Varieties of R-trivial and L-trivial Monoids via Combinatorics on Words
    Discrete Mathematics & Theoretical Computer Science. 14(1):141–146. 2012.
    PDF
  3. Manfred Kufleitner and Alexander Lauser
    Around Dot-Depth One
    International Journal of Foundations of Computer Science. 23(6):1323–1339. World Scientific, 2012.
    PDF
    DOI
  4. Volker Diekert , Manfred Kufleitner and Pascal Weil
    Star-Free Languages are Church-Rosser Congruential
    Theoretical Computer Science. 454:129–135. 2012.
    PDF
    DOI
  5. Volker Diekert , Steffen Kopecki and Victor Mitrana
    Deciding regularity of hairpin completions of regular languages in polynomial time
    Information and Computation. 217:12–30. 2012.
    PDF
    DOI
  6. Volker Diekert and Steffen Kopecki
    Language theoretical properties of hairpin formations
    Theoretical Computer Science. 429:65–73. 2012.
    DOI
  7. Volker Diekert , Andrew J. Duncan and Alexei G. Myasnikov
    Cyclic rewriting and conjugacy problems
    Groups Complexity Cryptology. 4(2):321–355. 2012.
    PDF
    DOI
  8. Volker Diekert and Alexei G. Myasnikov
    Group Extensions over Infinite Words
    International Journal of Foundations of Computer Science. 23:1001-1019. 2012.
    DOI
  9. Volker Diekert , Jürn Laun and Alexander Ushakov
    Efficient algorithms for highly compressed data: The Word Problem in Higman’s group is in P
    International Journal of Algebra and Computation. 22(8):1–19. 2012.
    PDF
    DOI
  10. Lila Kari and Steffen Kopecki
    Deciding Whether a Regular Language is Generated by a Splicing System
    ArXiv e-prints. abs/1112.4897 2012.
    PDF

Conference Articles

  1. Volker Diekert and Manfred Kufleitner
    Bounded synchronization delay in omega-rational expressions
    Computer Science Symposium in Russia (CSR) 2012, Conference Proceedings, volume 7353 of Lecture Notes in Computer Science, pages 89–98. Springer-Verlag, 2012.
    DOI
  2. Manfred Kufleitner and Alexander Lauser
    Lattices of Logical Fragments over Words
    Automata, Languages and Programming, International Colloquium (ICALP) 2012, Conference Proceedings Part II, volume 7392 of Lecture Notes in Computer Science, pages 275–286. Springer-Verlag, 2012.
    PDF
    DOI
  3. Manfred Kufleitner and Pascal Weil
    The \text{FO}^2 \text{FO}^2 alternation hierarchy is decidable
    Computer Science Logic (CSL) 2012 - 26th International Workshop/21st Annual Conference of the EACSL, Conference Proceedings, volume 16 of Leibniz International Proceedings in Informatics (LIPIcs), pages 426–439. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2012.
    PDF
    DOI
    URN
  4. Franz Jahn , Manfred Kufleitner and Alexander Lauser
    Regular Ideal Languages and Their Boolean Combinations
    Implementation and Application of Automata (CIAA) 2012, Conference Proceedings, volume 7381 of Lecture Notes in Computer Science, pages 205–216. Springer, 2012.
    PDF
    DOI
  5. Manfred Kufleitner and Alexander Lauser
    The join levels of the Trotter-Weil hierarchy are decidable
    Mathematical Foundations of Computer Science, International Symposium (MFCS) 2012, Conference Proceedings, volume 7464 of Lecture Notes in Computer Science, pages 603–614. Springer, 2012.
    PDF
    DOI
  6. Volker Diekert , Manfred Kufleitner , Klaus Reinhardt and Tobias Walter
    Regular Languages are Church-Rosser Congruential
    International Colloquium Automata, Languages and Programming (ICALP) 2012, Conference Proceedings, Part II, volume 7392 of Lecture Notes in Computer Science, pages 177–188. Springer-Verlag, 2012.
    PDF
    DOI
  7. Volker Diekert and Anca Muscholl
    On Distributed Monitoring of Asynchronous Systems
    WoLLIC, pages 70-84. 2012.
  8. Volker Diekert , Jonathan Kausch and Markus Lohrey
    Logspace Computations in Graph Groups and Coxeter Groups
    Proceedings of LATIN 2012, volume 7256 of Lecture Notes in Computer Science, pages 243–254. 2012.
    PDF
    DOI
  9. Volker Diekert , Jonathan Kausch and Markus Lohrey
    Logspace computations in Coxeter groups and graph groups
    Computational and Combinatorial Group Theory and Cryptography, volume 582 of Contemporary Mathematics, pages 77–94. Amer. Math. Soc., 2012.
    PDF
  10. Lila Kari , Steffen Kopecki and Shinnosuke Seki
    Iterated Hairpin Completions of Non-crossing Words
    38th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), 2011, volume 7147 of Lecture Notes in Computer Science, pages 337–348. Springer, 2012.
    PDF
    DOI
  11. Volker Diekert , Jürn Laun and Alexander Ushakov
    Efficient algorithms for highly compressed data: The Word Problem in Higman’s group is in P
    Proc. 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, Paris, France, volume 14 of Leibniz International Proceedings in Informatics (LIPIcs), pages 218–229. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012.
    PDF
    DOI
  12. Volker Diekert , Jürn Laun and Alexander Ushakov
    Efficient algorithms for highly compressed data: The Word Problem in Higman’s group is in P
    Proc. 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, Paris, France, volume 14 of LIPIcs, pages 218–229. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012.
    DOI

2011

Journal Articles

  1. Manfred Kufleitner and Alexander Lauser
    Partially Ordered Two-way Büchi Automata
    International Journal of Foundations of Computer Science. 22(8):1861–1876. World Scientific, 2011.
    PDF
    DOI
  2. Volker Diekert and Manfred Kufleitner
    Fragments of First-Order Logic over Infinite Words
    Theory of Computing Systems. 48(3):486–516. Springer New York, 2011.
    FMI, Universität Stuttgart, Universitätsstraße 38, 70569 Stuttgart, Germany
    PDF
    DOI
  3. Volker Diekert and Steffen Kopecki
    It is NL-Complete to Decide Whether a Hairpin Completion of Regular Languages is Regular
    International Journal of Foundations of Computer Science (IJFCS). 22(8):1813–1828. 2011.
    PDF
    DOI
  4. Steffen Kopecki
    On iterated hairpin completion
    Theoretical Computer Science. 412(29):3629–3638. 2011.
    PDF
    DOI
  5. Lila Kari , Shinnosuke Seki and Steffen Kopecki
    On the Regularity of Iterated Hairpin Completion of a Single Word
    Fundamenta Informaticae. 110(1-4):201–215. 2011.
    PDF
    DOI
  6. Volker Diekert and Jürn Laun
    On Computing Geodesics in Baumslag-Solitar Groups
    International Journal of Algebra and Computation. 21(1-2):119–145. 2011.
    PDF

Conference Articles

  1. Manfred Kufleitner and Alexander Lauser
    Languages of Dot-Depth One over Infinite Words
    IEEE Symposium on Logic in Computer Science (LICS) 2011, Conference Proceedings, pages 23–32. IEEE Computer Society, 2011.
    PDF
    DOI
  2. Jakub Kallas , Manfred Kufleitner and Alexander Lauser
    First-order Fragments with Successor over Infinite Words
    28th International Symposium on Theoretical Aspects of Computer Science (STACS) 2011, volume 9 of Leibniz International Proceedings in Informatics (LIPIcs), pages 356–367. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2011.
    PDF
    DOI
  3. Volker Diekert and Alexei G. Myasnikov
    Solving Word Problems in Group Extensions over Infinite Words
    Developments in Language Theory, pages 192-203. 2011.
    PDF
    DOI
  4. V. Diekert and A. Myasnikov
    Group extensions over infinite words
    Developments in Language Theory, 15th International Conference, DLT 2011, Milan, Italy, July 19-22, 2011. Proceedings, volume 6795 of Lecture Notes in Computer Science, pages 192–203. Springer, 2011.

Technical Reports

  1. Manfred Kufleitner and Alexander Lauser
    Cantor Topologies for Finite Words
    Technical Report Computer Science, Document number: 2011/02. University of Stuttgart, Febuary 2011.
    PDF

Book Chapters

  1. Volker Diekert and Anca Muscholl
    Trace Theory
    Encyclopedia of Parallel Computing, pages 2071–2079. Springer, 2011.
    PDF
    DOI
  2. Volker Claus , Volker Diekert and Holger Petersen
    Marriage Broker
    Algorithms Unplugged, Chapter 35, pages 345–355. Springer, 2011.
    1st edition
    DOI

Theses

  1. Steffen Kopecki
    Formal language theory of hairpin formations
    Dissertation, University of Stuttgart, 2011.
    PDF
  2. Armin Weiß
    Eine kombinatorische Charakterisierung kontextfreier Gruppen
    Diplomarbeit Nr. 3075, Fakultät Informatik, 2011.

2010

Journal Articles

  1. Manfred Kufleitner and Pascal Weil
    On the lattice of sub-pseudovarieties of DA
    Semigroup Forum. 81:243–254. 2010.
    DOI
  2. Volker Diekert , Tero Harju and Dirk Nowotka
    Weinbaum Factorizations of Primitive Words
    Russian Mathematics. 54(1):16–25. 2010.
    PDF
    DOI
  3. Ulrich Hertrampf and Christoph Minnameier
    Resource bounded frequency computations with three errors
    Algorithmica. 56(3):342–363. 2010.
    DOI
  4. Tero Harju and Dirk Nowotka
    Cyclically repetition-free words on small alphabets
    Information Processing Letters. 110(14-15):591–595. Elsevier Science Publishers Ltd., 2010.
    PDF
    DOI

Conference Articles

  1. Luc Dartois , Manfred Kufleitner and Alexander Lauser
    Rankers over Infinite Words (Extended Abstract)
    Developments in Language Theory, 14th International Conference (DLT) 2010, Conference Proceedings, volume 6224 of Lecture Notes in Computer Science, pages 148–159. Springer, 2010.
    PDF
    DOI
  2. Volker Diekert and Steffen Kopecki
    Complexity Results and the Growths of Hairpin Completions of Regular Languages (Extended Abstract)
    Implementation and Application of Automata - 15th International Conference (CIAA) 2010, volume 6482 of Lecture Notes in Computer Science, pages 105–114. Springer-Verlag, 2010.
    PDF
    DOI
  3. Volker Diekert , Andrew J. Duncan and Alexei G. Myasnikov
    Geodesic rewriting systems and pregroups
    Combinatorial and Geometric Group Theory, Trends in Mathematics, pages 55–91. Birkhäuser, 2010.
    PDF
    DOI

Book Chapters

  1. Steffen Kopecki
    On the Iterated Hairpin Completion
    Developments in Language Theory, volume 6224 of Lecture Notes in Computer Science, pages 438–439. Springer Berlin / Heidelberg, 2010.
    Universität Stuttgart, FMI
    PDF
    DOI

proceedings

  1. Theory of Computing Systems: Special Issue of the 3rd International Symposium on Computer Science in Russia, Moscow 2008, Proceedings
    Springer, 2010.
    DOI

2009

Journal Articles

  1. Volker Diekert and Dalia Krieger
    Some remarks about stabilizers
    Theoretical Computer Science. 410(30-32):2935–2946. 2009.
    PDF
    DOI
  2. Štěpán Holub and Dirk Nowotka
    The Ehrenfeucht-Silberger Problem
    5555:537–548. Springer, 2009.
    PDF
    DOI

Conference Articles

  1. Volker Diekert and Manfred Kufleitner
    Fragments of First-Order Logic over Infinite Words
    26th International Symposium on Theoretical Aspects of Computer Science (STACS) 2009, Leibniz International Proceedings in Informatics (LIPIcs), pages 325–336. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2009.
    PDF
    DOI
  2. Manfred Kufleitner and Pascal Weil
    On \text{FO}^2 \text{FO}^2 Quantifier Alternation over Words
    Mathematical Foundations of Computer Science 2009, 34th International Symposium, MFCS 2009, Nový Smokovec, Slovakia, August 24-28, 2009, Proceedings, volume 5734 of Lecture Notes in Computer Science, pages 513–524. Springer-Verlag, 2009.
    PDF
    DOI
  3. Volker Diekert and Paul Gastin
    Local safety and local liveness for distributed systems
    Perspectives in Concurrency Theory, pages 86–106. Universities Press, IARCS-Universities, 2009.
    PDF
  4. Volker Diekert , Steffen Kopecki and Victor Mitrana
    On the Hairpin Completion of Regular Languages
    Theoretical Aspects of Computing - ICTAC 2009, volume 5684 of Lecture Notes in Computer Science, pages 170–184. Springer, 2009.
    DOI
  5. Edgar Binder and Manfred Kufleitner
    Classification tree sources
    Information Theory Workshop, 2009. ITW 2009. IEEE, pages 218–222. 2009.
    DOI
  6. Mahmoud Fouz , Manfred Kufleitner , Bodo Manthey and Nima Zeini Jahromi
    On Smoothed Analysis of Quicksort and Hoare’s Find
    COCOON, volume 5609 of Lecture Notes in Computer Science, pages 158–167. Springer, 2009.
    PDF
    DOI
  7. Manfred Kufleitner
    On Bijective Variants of the Burrows-Wheeler Transform
    Stringology, pages 65-79. Prague Stringology Club, Department of Computer Science and Engineering, Faculty of Electrical Engineering, Czech Technical University in Prague, 2009.
    PDF
    WWW
  8. Manfred Kufleitner , Edgar Binder and Alexander Fries
    Combining models in data compression
    Proceedings of the 30th Symposium on Information Theory in the Benelux, Eindhoven, The Netherlands, pages 135–142. 2009.
  9. Benjamin Hoffmann , Mikhail Lifshits , Yury Lifshits and Dirk Nowotka
    Maximal Intersection Queries in Randomized Input Models
    Theory of Computing Systems: Special Issue: Symposium on Computer Science 2007, Proceedings, pages 104–119. Springer, 2009.
    PDF
    DOI
  10. Juraj Hromkovic̆ , Holger Petersen and Georg Schnitger
    On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA’s
    pages 2972–2981. 2009.
    DOI
  11. Holger Petersen
    Simulations by Time-Bounded Counter Machines
    13th International Conference, DLT 2009, Stuttgart, Germany, June 30–July 3, 2009, Proceedings, volume 5583 of Lecture Notes in Computer Science, pages 410–418. Springer-Verlag, 2009.
    DOI
  12. Holger Petersen and Szymon Grabowski
    Range mode and range median queries in constant time and sub-quadratic space
    pages 225–228. 2009.
    DOI

proceedings

  1. Developments in Language Theory, 13th International Conference, DLT 2009, Stuttgart, Germany, June 30 - July 3, 2009. Proceedings
    volume 5583 of Lecture Notes in Computer Science. Springer, 2009.
    DOI

Books

  1. Informatik als Dialog zwischen Theorie und Anwendung: Festschrift für Volker Claus zum 65. Geburtstag
    Vieweg+Teubner, 2009.
    DOI

Book Chapters

  1. Volker Diekert and Ulrich Hertrampf
    Komplexität der Geographie
    Informatik als Dialog zwischen Theorie und Anwendung: Festschrift für Volker Claus zum 65. Geburtstag, Chapter 11, pages 119–132. Vieweg+Teubner, 2009.
    PDF
    DOI
  2. Volker Diekert and Klaus-Jörn Lange
    Variationen über Walther von Dyck und Dyck-Sprachen
    Informatik als Dialog zwischen Theorie und Anwendung: Festschrift für Volker Claus zum 65. Geburtstag, Chapter 13, pages 147–154. Vieweg+Teubner, 2009.
    PDF
    DOI

2008

Journal Articles

  1. Stefan Göller and Dirk Nowotka
    A note on an extension of PDL
    Journal of Applied Logic. 6(4):606–608. December 2008.
    PDF
  2. Volker Diekert , Paul Gastin and Manfred Kufleitner
    A Survey on Small Fragments of First-Order Logic over Finite Words
    International Journal of Foundations of Computer Science. 19:513–548. 2008.
    PDF
    DOI
  3. Volker Diekert and Markus Lohrey
    Word equations over graph products
    International Journal of Algebra and Computation. 18:493–533. 2008.
    PDF
    DOI
  4. Volker Diekert and Markus Lohrey
    Word Equations over Graph Products
    International Journal of Algebra and Computation. 18(3):493-533. 2008.
  5. Volker Diekert , Markus Lohrey and Alexander Miller
    Partially commutative inverse monoids
    Semigroup Forum. 77(2):196–226. 2008.
    DOI
  6. Volker Diekert , Nicole Ondrusch and Markus Lohrey
    Algorithmic Problems on Inverse Monoids over Virtually Free Groups
    International Journal of Algebra and Computation. 18(1):181–208. 2008.
    PDF
    DOI
  7. Jean-Pierre Duval , Tero Harju and Dirk Nowotka
    Unbordered factors and Lyndon words.
    Discrete Mathematics. 308(11):2261–2264. 2008.
    PDF
    DOI
  8. Javier Esparza , Petr Jančar and Alexander Miller
    On the Complexity of Consistency and Complete State Coding for Signal Transition Graphs
    Fundamenta Informaticae. 86(3):227–253. IOS Press, 2008.
    PDF
  9. Tero Harju and Dirk Nowotka
    Bordered Conjugates of Words over Large Alphabets
    Electronic Journal of Combinatorics. 15(1) 2008.
    PDF
  10. Štěpán Holub and Dirk Nowotka
    On the Relation between Periodicity and Unbordered Factors of Finite Words
    5257:408–418. Springer, 2008.
    PDF
    DOI

Conference Articles

  1. V. Claus , V. Diekert and H. Petersen
    Partnerschaftsvermittlung
    Taschenbuch der Algorithmen, pages 373-384. Springer-Verlag, 2008.
  2. Manfred Kufleitner
    The Height of Factorization Forests
    Mathematical Foundations of Computer Science 2008, 33rd International Symposium, MFCS 2008, Toruń, Poland, August 25-29, 2008, Proceedings, volume 5162 of Lecture Notes in Computer Science, pages 443–454. Springer-Verlag, 2008.
    DOI
  3. Holger Petersen
    Element distinctness and sorting on one-tape off-line Turing machines
    Proc. 34th International Conference on Current Trends in Theory and Practice in Computer Science, Nový Smokovec, Slovakia, January 19-25, 2008, Proceedings, volume 4910 of Lecture Notes in Computer Science, pages 406–417. Springer-Verlag, 2008.
    DOI
  4. Holger Petersen
    Improved bounds for range mode and range median queries
    Proc. 34th International Conference on Current Trends in Theory and Practice in Computer Science, Nový Smokovec, Slovakia, January 19-25, 2008, Proceedings, volume 4910 of Lecture Notes in Computer Science, pages 418–423. Springer-Verlag, 2008.
    DOI

proceedings

  1. Theory of Computing Systems: Special Issue of the 1st International Symposium on Computer Science in Russia, St. Petersburg 2006, Proceedings
    Springer, 2008.
    DOI

Book Chapters

  1. Volker Diekert and Paul Gastin
    First-order definable languages
    Logic and Automata: History and Perspectives, Texts in Logic and Games, pages 261–306. Amsterdam University Press, 2008.
    PDF
  2. Volker Claus , Volker Diekert and Holger Petersen
    Partnerschaftsvermittlung
    Taschenbuch der Algorithmen, pages 373–384. Springer, 2008.
    PDF
    DOI
  3. Ulrich Hertrampf and Christoph Minnameier
    Resource bounded frequency computations with three errors
    Computing and combinatorics, volume 5092 of Lecture Notes in Computer Science, pages 72–81. Springer, 2008.
    DOI

2007

Journal Articles

  1. Manfred Kufleitner
    Polynomials, Fragments of Temporal Logic and the Variety \text{DA} \text{DA} over Traces
    Theoretical Computer Science. 376:89–100. 2007.
    DOI
  2. Volker Diekert , Martin Horsch and Manfred Kufleitner
    On First-Order Fragments for Mazurkiewicz Traces
    Fundamenta Informaticae. 80(1-3):1–29. 2007.
    PDF
    WWW
  3. Štěpán Holub and Dirk Nowotka
    Periodicity and Unbordered Words: A Proof of the Extended Duval Conjecture
    Journal of the ACM. 54 ACM, 2007.
    PDF
    DOI
  4. Markus Lohrey and Nicole Ondrusch
    Inverse monoids: decidability and complexity of algebraic questions
    Information and Computation . 205(8):1212–1234. 2007.
    PDF
    DOI

Conference Articles

  1. Volker Diekert and Manfred Kufleitner
    On First-Order Fragments for Words and Mazurkiewicz Traces: A Survey
    Developments in Language Theory, 11th International Conference, DLT 2007, Turku, Finland, July 3-6, 2007, Proceedings, volume 4588 of Lecture Notes in Computer Science, pages 1–19. Springer-Verlag, 2007.
    PDF
    DOI
  2. Stefan Göller
    On the Complexity of Reasoning about Dynamic Policies
    Proc. of Computer Science Logic 2007, volume 4646 of Lecture Notes in Computer Science, pages 358–373. Springer, 2007.
    PDF
    DOI
  3. Stefan Göller , Markus Lohrey and Carsten Lutz
    PDL with Intersection and Converse is 2EXP-complete
    Proceedings of FoSSaCS 2007, volume 4423 of Lecture Notes in Computer Science, pages 198–212. Springer, 2007.
    PDF
    DOI
  4. Benjamin Hoffmann , Yury Lifshits and Dirk Nowotka
    Maximal Intersection Queries in Randomized Input Models
    Second International Symposium on Computer Science in Russia, CSR 2007, Ekaterinburg, Russia, September 3-7, 2007, Proceedings, volume 4649 of Lecture Notes in Computer Science, pages 227–236. Springer, 2007.
    PDF
    DOI
  5. Yury Lifshits and Dirk Nowotka
    Estimation of the Click Volume by Large Scale Regression Analysis
    Second International Symposium on Computer Science in Russia, CSR 2007, Ekaterinburg, Russia, September 3-7, 2007, Proceedings, volume 4649 of Lecture Notes in Computer Science, pages 216–226. Springer, 2007.
    PDF
    DOI
  6. Dirk Nowotka and Jiri Srba
    Height-Deterministic Pushdown Automata
    Mathematical Foundations of Computer Science 2007, 32nd International Symposium, MFCS 2007, Český Krumlov, Czech Republic, August 26-31, 2007, Proceedings, volume 4708 of Lecture Notes in Computer Science, pages 125–134. Springer-Verlag, 2007.
    PDF
    DOI
  7. Holger Petersen
    String Matching with Simple Devices
    pages 32–34. 2007.
    DOI

Technical Reports

  1. Manfred Kufleitner
    A Proof of the Factorization Forest Theorem
    Technical report, Document number: 2007/05. Formale Methoden der Informatik, Universität Stuttgart, October 2007.
    PDF

proceedings

  1. Computer Science - Theory and Applications, Second International Symposium on Computer Science in Russia, CSR 2007, Ekaterinburg, Russia, September 3-7, 2007, Proceedings
    volume 4649 of Lecture Notes in Computer Science. Springer, 2007.

2006

Journal Articles

  1. Volker Diekert and Paul Gastin
    Pure future local temporal logics are expressively complete for Mazurkiewicz traces
    Information and Computation. 204:1597–1619. 2006.
    PDF
    DOI
  2. Volker Diekert and Anca Muscholl
    Solvability of Equations in Free Partially Commutative Groups is Decidable
    International Journal of Algebra and Computation. 16:1047–1070. 2006.
    PDF
    DOI
  3. Markus Lohrey
    Word Problems and Membership Problems on Compressed Words
    SIAM J. Comput.. 35(5):1210-1240. 2006.
    PDF
    DOI
  4. Volker Diekert and Paul Gastin
    From local to global temporal logics over Mazurkiewicz traces
    Theoretical Computer Science. 356(1–2):125–135. 2006.
    PDF
    DOI
  5. Markus Lohrey and Sebastian Maneth
    The complexity of tree automata and XPath on grammar-compressed trees
    Theoretical Computer Science. 363(2):196–210. Elsevier Science Publishers Ltd., 2006.
    PDF
    DOI
  6. Dietrich Kuske and Markus Lohrey
    Logical Aspects of Cayley-Graphs: The Monoid Case
    International Journal of Algebra and Computation. 16:307–340. 2006.
    PDF
    DOI
  7. Amir M. Ben-Amram and Holger Petersen
    Backing Up in Singly Linked Lists
    Journal of the ACM. 53 ACM, 2006.
    DOI

Conference Articles

  1. Manfred Kufleitner
    Polynomials, Fragments of Temporal Logic and the Variety \text{DA} \text{DA} over Traces
    Proc. of the 10th Int. Conf. on Developments in Language Theory (DLT’06), volume 4036 of Lecture Notes in Computer Science, pages 37–48. Springer-Verlag, 2006.
    DOI
  2. Volker Diekert , Markus Lohrey and Alexander Miller
    Partially commutative inverse monoids
    Proceedings of the 31th International Symposium on Mathematical Foundations of Computer Science (MFCS 2006), Bratislave (Slovakia), volume 4162 of Lecture Notes in Computer Science, pages 292–304. Springer-Verlag, 2006.
    PDF
    DOI
  3. Markus Lohrey and Géraud Sénizergues
    Theories of HNN-Extensions and Amalgamated Products
    ICALP, pages 504–515. 2006.
    PDF
    DOI
  4. Javier Esparza , Petr Jančar and Alexander Miller
    On the Complexity of Consistency and Complete State Coding for Signal Transition Graphs
    2010 10th International Conference on Application of Concurrency to System Designi (ACSD’06), pages 47–56. IEEE Computer Society, 2006.
    PDF
    DOI
  5. Stefan Göller and Markus Lohrey
    Infinite-state model-checking of Propositional Dynamic Logics
    Proc. of Computer Science Logic 2006, volume 4207 of Lecture Notes in Computer Science, pages 349–364. Springer, 2006.
    PDF
    DOI
  6. Yury Lifshits and Markus Lohrey
    Querying and Embedding Compressed Texts
    Proceedings of the 31th International Symposium on Mathematical Foundations of Computer Science (MFCS 2006), Bratislave (Slovakia), volume 4162 of Lecture Notes in Computer Science, pages 681–692. Springer-Verlag, 2006.
    PDF
    DOI
  7. Dietrich Kuske and Markus Lohrey
    Monadic chain logic over iterations and applications to pushdown systems
    Proceedings of the 21st Annual IEEE Symposium on Logic in Computer Science (LICS’10), pages 91–100. IEEE Computer Society Press, 2006.
    PDF
    DOI
  8. Markus Lohrey
    First-order and counting theories of ω ω -automatic structures
    Proceedings of FoSSaCS 2006, volume 3921 of Lecture Notes in Computer Science, pages 322–336. Springer, 2006.
    PDF
    DOI

Theses

  1. Manfred Kufleitner
    Logical Fragments for Mazurkiewicz Traces: Expressive Power and Algebraic Characterizations
    Dissertation, Institut für Formale Methoden der Informatik, Universität Stuttgart, 2006.
    PDF

proceedings

  1. Volker Diekert and Michel Habib
    Theory of Computing Systems: Special Issue of the 21st International Symposium on Theoretical Aspects of Computer Science (STACS’04), Montpellier 2004, Proceedings
    Springer, 2006.
    DOI

Book Chapters

  1. Holger Petersen
    Computable Lower Bounds for Busy Beaver Turing Machines
    Recent Advances in Formal Languages and Applications, volume 25 of Studies in Computational Intelligence, pages 305–319. Springer-Verlag, 2006.
    DOI

2005

Journal Articles

  1. Holger Austinat , Volker Diekert , Ulrich Hertrampf and Holger Petersen
    Regular Frequency Computations
    Theoretical Computer Science. 330(1):15–21. 2005.
    PDF
    DOI
  2. Volker Diekert , Claudio Gutiérrez and Hagenah
    The existential theory of equations with rational constraints in free groups is PSPACE-complete
    Information and Computation. 202:105–140. 2005.
    PDF
    DOI
  3. Dietrich Kuske and Markus Lohrey
    Logical aspects of Cayley-graphs: the group case
    Ann. Pure Appl. Logic. 131(1-3):263–286. 2005.
    PDF
    DOI
  4. Markus Lohrey and Holger Petersen
    Complexity Results for Prefix Grammars
    RAIRO. Informatique Théorique et Applications. 39(3):391–401. 2005.
    DOI

Conference Articles

  1. Markus Lohrey and Nicole Ondrusch
    Inverse monoids: decidability and complexity of algebraic questions
    Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS 2005), Gdansk (Poland), volume 3618 of Lecture Notes in Computer Science, pages 664–675. Springer-Verlag, 2005.
    DOI
  2. Stefan Göller and Markus Lohrey
    Fixpoint logics on hierarchical structures
    FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science, volume 3821 of Lecture Notes in Computer Science, pages 483–494. Springer, 2005.
    PDF
    DOI
  3. Dietrich Kuske and Markus Lohrey
    Decidable first-order theories of one-step rewriting in trace monoids
    Theory of Computing Systems, pages 39–81. Springer, 2005.
    PDF
    DOI

proceedings

  1. Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS’05), Stuttgart (Germany)
    volume 3404 of Lecture Notes in Computer Science. Springer-Verlag, 2005.
    DOI

2004

Journal Articles

  1. Volker Diekert and Markus Lohrey
    Existential and Positive Theories of Equations in Graph Products
    Theory of Computing Systems. 37:133–156. 2004.
    PDF
    DOI
  2. Volker Diekert and Paul Gastin
    Local temporal logic is expressively complete for cograph dependence alphabets
    Information and Computation. 195:30–52. 2004.
    PDF
  3. Markus Lohrey
    Decidability and complexity in automatic monoids
    3340:308–320. Springer, 2004.
    PDF
    DOI
  4. Markus Lohrey
    Word problems on compressed words
    3142:906–918. Springer, 2004.
    PDF
    DOI
  5. Markus Lohrey and Anca Muscholl
    Bounded MSC communication
    Information and Computation. 189(2):160–181. Elsevier Science Publishers Ltd., 2004.
    PDF
    DOI
  6. Katsushi Inoue , Akira Ito , Takashi Kamiura , Holger Petersen and Lan Zhang
    A Note on Rebound Turing Machines
    International Journal of Foundations of Computer Science. 15(05):791–807. 2004.
    DOI

Conference Articles

  1. Volker Diekert and Paul Gastin
    Pure future Local Temporal Logics are expressively complete for Mazurkiewicz Traces
    Proceedings of the 6th Latin American Theoretical Informatics Symposium (LATIN’04), Buenos Aires, volume 2976 of Lecture Notes in Computer Science, pages 232–241. Springer-Verlag, 2004.
    PDF
    DOI
  2. Klaus Wich
    Sublogarithmic Ambiguity
    29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004, Proceedings, volume 3153 of Lecture Notes in Computer Science, pages 794–806. Springer, 2004.
    PDF
    DOI

proceedings

  1. Proc. 21st Annual Symposium on Theoretical Aspects of Computer Science (STACS’04), Montpellier (France)
    volume 2996 of Lecture Notes in Computer Science. Springer-Verlag, 2004.
    DOI

2003

Journal Articles

  1. Holger Austinat , Volker Diekert and Ulrich Hertrampf
    A Structural Property of Regular Frequency Computations
    Theoretical Computer Science. 292(1):33–43. 2003.
    PS
    DOI
  2. Markus Lohrey
    Realizability of high-level message sequence charts: closing the gaps
    Theoretical Computer Science. 309(1-3):529–554. Elsevier Science Publishers Ltd., 2003.
    PDF
    DOI
  3. Markus Lohrey
    Automatic structures of bounded degree
    2850:344–358. Springer, 2003.
    PS
    DOI
  4. Amir M. Ben-Amram , Omar Berkmann and Holger Petersen
    Element distinctness and sorting on one-tape off-line Turing machines: a complete solution
    Acta Informatica. 40(2):81–94. Springer-Verlag, 2003.
    DOI

Conference Articles

  1. Volker Diekert and Manfred Kufleitner
    A Remark about Quadratic Trace Equations
    Developments in Language Theory: DLT 2002, Kyoto, Japan, volume 2450 of Lecture Notes in Computer Science, pages 59–66. Springer-Verlag, 2003.
    PS
    DOI
  2. Volker Diekert and Markus Lohrey
    Word equations over graph products
    Proceedings of the 23rd Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2003), Mumbai (India), volume 2914 of Lecture Notes in Computer Science, pages 156–167. Springer-Verlag, 2003.
    PS
    DOI
  3. Dietrich Kuske and Markus Lohrey
    Decidable theories of Cayley-Graphs
    20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27 - March 1, 2003, (STACS 2003). Proceedings, volume 2607 of Lecture Notes in Computer Science, pages 463–474. Springer, 2003.
    PS
    DOI

2002

Journal Articles

  1. Volker Diekert and Paul Gastin
    LTL is expressively complete for Mazurkiewicz traces
    Journal of Computer and System Sciences. 64:396–418. 2002.
    PDF
    DOI
  2. Volker Diekert and Markus Lohrey
    A note on the existential theory of equations in plain groups
    International Journal of Algebra and Computation. 12:1–7. 2002.
    PDF
    DOI
  3. Markus Lohrey
    Safe realizability of high-level message sequence charts
    2421:177–192. Springer, 2002.
    PS
    DOI
  4. Markus Lohrey
    Axiomatising Divergence
    2380:585–596. Springer, 2002.
    PS
    DOI
  5. Dietrich Kuske and Markus Lohrey
    On the theory of one-step rewriting in trace monoids
    2380:752–763. Springer, 2002.
    PS
    DOI
  6. Markus Lohrey and Anca Muscholl
    Bounded MSC communication
    2303:295–309. Springer, 2002.
    PS
    DOI
  7. Klaus Wich
    Universal Inherence of Cycle-Free Context-Free Ambiguity Functions
    2380:669–680. Springer, 2002.
    PDF
    DOI

Conference Articles

  1. Volker Diekert
    A Pure Future Local Temporal Logic Beyond Cograph-Monoids
    Proc. RIMS Symposium on Algebraic Systems, Formal Languages and Conventional and Unconventional Computation Theory, Kyoto, Japan 2002, pages . 2002.
    PS
  2. Volker Diekert and Markus Lohrey
    Existential and Positive Theories of Equations in Graph Products
    Proc. 19th Annual Symposium on Theoretical Aspects of Computer Science (STACS’02), Juan les Pin (France), 2002, volume 2285 of Lecture Notes in Computer Science, pages 501–512. Springer-Verlag, 2002.
    PS
    DOI
  3. Holger Petersen
    Survey of Decision Problems for Regular Expressions
    10th International Conference on Automata and Formal Languages (AFL’02), Debrecen, 2002. Proceedings, 2002.
  4. Holger Petersen
    The Membership Problem for Regular Expressions with Intersection is Complet e in LOGCFL
    19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes - Juan les Pins, France, March 14-16, 2002, Proceedings, volume 2285 of Lecture Notes in Computer Science, pages 513–522. Springer-Verlag, 2002.
    DOI

Book Chapters

  1. Volker Diekert and Paul Gastin
    Safety and Liveness Properties for Real Traces and a Direct Translation from LTL to Monoids
    Formal and Natural Computing — Essays Dedicated to Grzegorz Rozenberg, volume 2300 of Lecture Notes in Computer Science, pages 26–38. Springer-Verlag, 2002.
    PS
    DOI
  2. Volker Diekert
    Makanin’s Algorithm
    Algebraic Combinatorics on Words, volume 90 of Encyclopedia of Mathematics and Its Applications, Chapter 12, pages 387–442. Cambridge University Press, 2002.
    PS

2001

Journal Articles

  1. Volker Diekert , Claudio Gutiérrez and \relax Christian Hagenah
    The Existential Theory of Equations with Rational Constraints in Free Groups is PSPACE-Complete
    Computing Research Repository (arXiv eprints). cs.DS/0103018 2001.
    PDF
  2. Markus Lohrey
    Bounded MSC communication
    Information and Computation. 170(1):1–25. Elsevier Science Publishers Ltd., 2001.
    DOI
  3. Markus Lohrey
    Word Problems for 2-Homogeneous Monoids and Symmetric Logspace
    2136:500–511. Springer, 2001.
    PS
    DOI
  4. Klaus Wich
    Characterization of Context-Free Languages with Polynomially Bounded Ambiguity
    2136:703–714. Springer, 2001.
    PDF
    DOI

Conference Articles

  1. Volker Diekert and Paul Gastin
    Local Temporal Logic is Expressively Complete for Cograph Dependence Alphabets
    Proc. 8th International Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR’01), Havanna (Cuba), volume 2250 of Lecture Notes in Computer Science, pages 55–69. Springer-Verlag, 2001.
    DOI
  2. Volker Diekert , Claudio Gutiérrez and Hagenah
    The existential theory of equations with rational constraints in free groups is PSPACE-complete
    Proc. 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS’01), Dresden (Germany), 2001, volume 2010 of Lecture Notes in Computer Science, pages 170–182. Springer-Verlag, 2001.
    PS
    DOI
  3. Volker Diekert and Anca Muscholl
    Solvability of Equations in Free Partially Commutative Groups is Decidable
    Proc. 28th Internationaldl0 Colloquium Automata, Languages and Programming (ICALP’01), volume 2076 of Lecture Notes in Computer Science, pages 543–554. Springer-Verlag, 2001.
    PS
    DOI
  4. Markus Lohrey
    On the Parallel Complexity of Tree Automata
    Proceedings of the 12th International Conference on Rewrite Techniques and Applications (RTA 2001), Utrecht (The Netherlands), volume 2051 of Lecture Notes in Computer Science, pages 201–215. Springer-Verlag, 2001.
    PS
    DOI

Theses

  1. Manfred Kufleitner
    Wortgleichungen in hyperbolischen Gruppen
    Diplomarbeit Nr. 1922, Fakultät Informatik, 2001.

2000

Journal Articles

  1. Ulrich Hertrampf
    Algebraic acceptance mechanisms for polynomial time machines
    SIGACT News. 31(2):22–33. 2000.
    DOI
  2. Ulrich Hertrampf
    Quantencomputer
    Informatik-Spektrum. 23(5):322–324. 2000.
    DOI
  3. Ulrich Hertrampf , Steffen Reith and Heribert Vollmer
    A note on closure properties of logspace MOD classes
    Information Processing Letters. 75(3):91–93. 2000.
    DOI
  4. Jürgen Gross and Markus Lohrey
    Implementing Luby’s Algorithm on the Cray T3E
    :467–477. Springer, 2000.
    PS
    DOI

Conference Articles

  1. Holger Austinat , Volker Diekert , Ulrich Hertrampf and Holger Petersen
    On Regular Frequency Computations
    Proc. RIMS Symposium on Algebraic Systems, Formal Languages and Computation, Kyoto, Japan, pages 35–42. 2000.
  2. Volker Diekert and Paul Gastin
    LTL is expressively complete for Mazurkiewicz traces
    Proc. 27th International Colloquium Automata, Languages and Programming (ICALP’2000), Geneva (Switzerland), volume 1853 of Lecture Notes in Computer Science, pages 211–222. Springer-Verlag, 2000.
    PS
    DOI
  3. Klaus Wich
    Sublinear Ambiguity
    Proc. 25th International Symposium on Mathematical Foundations of Computer Science (MFCS’2000), Bratislava (Slovakia), 2000, volume 1893 of Lecture Notes in Computer Science, pages 690–698. Springer Verlag, 2000.
    PDF
    DOI
  4. Klaus Wich
    Exponential Ambiguity of Context-free Grammars
    Proc. 4th International Conference on Developments in Language Theory, July 1999, pages 125–138. World Scientific, Singapore, 2000.
    PDF

1999

Journal Articles

  1. Volker Diekert , Matiyasevich and Anca Muscholl
    Solving word equations modulo partial commutations
    Theoretical Computer Science. 224:215–235. 1999.
    PS
    DOI
  2. Anca Muscholl
    Matching Specifications for Message Sequence Charts
    1578:273–287. Springer, 1999.
    PDF
    DOI

Conference Articles

  1. Volker Diekert and Paul Gastin
    An Expressively Complete Temporal Logic without Past Tense Operators for Mazurkiewicz Traces
    Proc. 13th Computer Science Logic (CSL’99), Madrid (Spain) 1999, volume 1683 of Lecture Notes in Computer Science, pages 188–203. Springer-Verlag, 1999.
    DOI
  2. Volker Diekert and Yuji Kobayashi
    Some Identities Related to Automata, Determinants, and Möbius Functions
    Algebraic Engineering, Proc. International Workshop on Formal Languages and Computer Systems, Kyoto, Japan, 18–21 March 1997, and the First International Conference on Semigroups and Algebraic Engineering, Aizu, Japan, 24–28 March 1997, pages 330–349. World Scientific, 1999.
  3. John Michael Robson and Volker Diekert
    On Quadratic Word Equations
    Proc. 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS’99), Trier (Germany), volume 1563 of Lecture Notes in Computer Science, pages 217–226. Springer-Verlag, 1999.
    DOI

Book Chapters

  1. Volker Diekert and John Michael Robson
    Quadratic word equations
    Jewels are forever – Contributions on Theoretical Computer Science in Honor of Arto Salomaa, pages 314–326. Springer-Verlag, 1999.
    DOI
  2. Ulrich Hertrampf
    Generalized Regular Counting Classes
    Mathematical foundations of computer science 1999 (Szklarska Poreba), volume 1672 of Lecture Notes in Computer Science, pages 419–429. Springer, 1999.
    DOI
  3. Markus Lohrey
    Complexity Results for Confluence Problems
    Mathematical foundations of computer science 1999 (Szklarska Poreba), volume 1672 of Lecture Notes in Computer Science, pages 114–124. Springer, 1999.
    DOI

Theses

  1. Anca Muscholl
    Decision and complexity issues on concurrent systems
    Habilitationsschrift (Postdoctoral thesis), Universität Stuttgart, 1999.

1998

Journal Articles

  1. Beatrice Bérard , Volker Diekert , Paul Gastin and Antoine Petit
    Characterization of the Expressive Power of Silent Transitions in Timed Automata
    Fundamenta Informaticae. 36:145–182. 1998.
    DOI
  2. K. Cronauer , U. Hertrampf , H. Vollmer and K. W. Wagner
    The Chain Method to Separate Counting Classes
    Theory Computing Systems. 31(1):93–108. 1998.
    DOI
  3. Volker Diekert and Paul Gastin
    Approximating Traces
    Acta Informatica. 35:567–593. 1998.
    DOI
  4. Zoltán Ésik and Michael Bertol
    Nonfinite axiomatizability of the equational theory of shuffle
    Acta Informatica. 35:505–539. 1998.
    PS
    DOI
  5. Markus Lohrey
    NP-Completeness Results Concerning the Transformation of Logic Programs into Attribute Grammars
    Acta Cybernetica. 13(3):209–224. 1998.
    PS
  6. Holger Hermanns and Markus Lohrey
    Priority and maximal progress are completely axiomatisable (extended abstract)
    1466:237–252. Springer, 1998.
    PS
    DOI
  7. Anca Muscholl , Doron Peled and Zhendong Su
    Deciding properties for message sequence charts
    1378:226–242. Springer, 1998.
    PDF
    DOI

Conference Articles

  1. Christian Hagenah and Anca Muscholl
    Computing ε ε -Free NFA from Regular Expressions in O(n \log^2(n)) O(n \log^2(n)) Time
    Mathematical Foundations of Computer Science 1998, 23rd International Symposium, MFCS’98, Brno, Czech Republic, August 24-28, 1998, Proceedings, volume 1450 of Lecture Notes in Computer Science, pages 277–285. Springer, 1998.
    PDF
    DOI
  2. Markus Lohrey
    On the Confluence of Trace Rewriting Systems
    FSTTCS 1998: Foundations of Software Technology and Theoretical Computer Science, volume 1530 of Lecture Notes in Computer Science, pages 319–330. Springer, 1998.
    DOI

Book Chapters

  1. Ulrich Hertrampf
    The Inherent Dimension of Bounded Counting Classes
    Computing and combinatorics (Taipei, 1998), volume 1449 of Lecture Notes in Computer Science, pages 157–166. Springer, 1998.
    DOI

1997

Journal Articles

  1. Hendrik Jan Hoogeboom and Anca Muscholl
    The code problem for traces – improving the boundaries
    Theoretical Computer Science. 172(1-2):309–321. 1997.
    PS
    DOI

Conference Articles

  1. Volker Diekert , Paul Gastin and Antoine Petit
    Removing \varepsilon \varepsilon -Transitions in Timed Automata
    Proc. 14th Annual Symposium on Theoretical Aspects of Computer Science (STACS’97), Lübeck (Germany), 1997, volume 1200 of Lecture Notes in Computer Science, pages 583–594. Springer-Verlag, 1997.
    DOI
  2. Volker Diekert , Matiyasevich and Anca Muscholl
    Solving trace equations using lexicographical normal forms
    Proc. 24th International Colloquium Automata, Languages and Programming (ICALP’97), Bologna, volume 1256 of Lecture Notes in Computer Science, pages 336–347. Springer-Verlag, 1997.
    PDF
    DOI
  3. Yves Métivier , Anca Muscholl and Pierre-André Wacrenier
    About the local detection of termination of local computations in graphs
    SIROCCO’97, 4th International Colloquium on Structural Information & Communication Complexity, Monte Verita, Ascona, Switzerland, July 24-26, 1997, pages 188–200. Carleton Scientific, 1997.
    PDF
  4. Holger Petersen
    The Equivalence of Pebbles and Sensing Heads for Finite Automata
    Fundamentals of computation theory (Kraków, 1997), volume 1279 of Lecture Notes in Computer Science, pages 400–410. Springer, 1997.
    DOI
  5. Holger Petersen
    Homomorphic Images of Sentential Forms and Terminating Grammars
    22nd International Symposium, MFCS’97, Bratislava, Slovakia, August 25-29, 1997, Proceedings, volume 1295 of Lecture Notes in Computer Science, pages 448–457. Springer, 1997.
    DOI

Book Chapters

  1. Volker Diekert
    A Remark on Trace Equations
    Foundations of Computer Science, volume 1337 of Lecture Notes in Computer Science, pages 251–260. Springer-Verlag, 1997.
    DOI
  2. Volker Diekert and Yves Métivier
    Partial Commutation and Traces
    Handbook of Formal Languages, Volume 3: Beyond Words., pages 457–533. 1997.
    DOI
  3. Ulrich Hertrampf
    Acceptance by Transformation Monoids (with an Application to Local Self Reductions)
    Twelfth Annual IEEE Conference on Computational Complexity (Ulm, 1997), pages 213–224. IEEE Computer Society, 1997.
    DOI
  4. Ulrich Hertrampf
    Polynomial Time Machines Equipped with Word Problems over Algebraic Structures as their Acceptance Criteria
    Fundamentals of computation theory (Kraków, 1997), volume 1279 of Lecture Notes in Computer Science, pages 233–244. Springer, 1997.
    DOI
  5. Ulrich Hertrampf
    The Shapes of Trees
    Computing and combinatorics (Shanghai, 1997), volume 1276 of Lecture Notes in Computer Science, pages 412–421. Springer, 1997.
    DOI

Technical Reports

  1. Holger Petersen
    A Census Technique for Simple Computing Devices
    Technical Report, Document number: 1997/07. Universität Stuttgart, Fakultät Informatik, 1997.

1996

Journal Articles

  1. Volker Diekert and Anca Muscholl
    A note on Métivier’s construction of asynchronous automata for triangulated graphs
    Fundamenta Informaticae. 25:241–246. 1996.
    PDF
    DOI
  2. Werner Ebinger and Anca Muscholl
    Logical definability on infinite traces
    Theoretical Computer Science. 154:67–84. 1996.
    PDF
  3. Anca Muscholl
    On the complementation of asynchronous cellular Büchi automata
    Theoretical Computer Science. 169(2):123–145. Elsevier Science Publishers Ltd., 1996.
    PDF
    DOI
  4. Anca Muscholl and Holger Petersen
    A Note on the Commutative Closure of Star-Free Languages
    Information Processing Letters. 57(2):71–74. 1996.
    PS
    DOI
  5. U. Hertrampf , H. Vollmer and K. W. Wagner
    On Balanced vs. Unbalanced Computation Trees
    Math. Systems Theory. 29(4):411–421. 1996.
    DOI

Conference Articles

  1. Michael Bertol and Volker Diekert
    Trace rewriting: Computing normal forms in time \cal
		  O(n \log n) \cal O(n \log n) .
    Proc. 13th Annual Symposium on Theoretical Aspects of Computer Science (STACS’96), Grenoble (France), volume 1046 of Lecture Notes in Computer Science, pages 269–280. Springer-Verlag, 1996.
    PS
    DOI
  2. Volker Diekert , Paul Gastin and Antoine Petit
    Recent developments in trace theory
    Developments in Language Theory II, pages 373–385. World Scientific, 1996.
  3. Volker Diekert and Anca Muscholl
    Code problems on traces
    Proc. 21st Symposium on Mathematical Foundations of Computer Science (MFCS’96), Cracow (Poland), volume 1113 of Lecture Notes in Computer Science, pages 2–17. Springer-Verlag, 1996.
    PDF
    DOI
  4. Holger Petersen
    The power of programs with restricted control structure
    Preproceedings of WCCL’96, volume 1 of Preprint-Reihe Mathematik, pages 56–58. Ernst-Moritz-Arndt-Universität, 1996.
    PS

1995

Journal Articles

  1. Volker Diekert , Paul Gastin and Antoine Petit
    Rational and recognizable complex trace languages
    Information and Computation. 116:134–153. 1995.
    DOI
  2. Celia Wrathall and Volker Diekert
    On Confluence of One-Rule Trace-Rewriting Systems
    Mathematical Systems Theory. 28:341–361. 1995.
    DOI
  3. Michael Bertol and Klaus Reinhardt
    The Tautologies over a Finite Set are Context-Free
    Bulletin of the European Association for Theoretical Computer Science. 57 1995.
    PS

Conference Articles

  1. Michael Bertol
    Efficient rewriting in cograph trace monoids
    Proc. 10th Fundamentals of Computation Theory (FCT ’95), Dresden (Germany) 1995, volume 965 of Lecture Notes in Computer Science, pages 146–155. Springer-Verlag, 1995.
    PS
    DOI
  2. Michael Bertol and Volker Diekert
    On efficient reduction-algorithms for some trace rewriting systems
    Term Rewriting, volume 909 of Lecture Notes in Computer Science, pages 114–126. Springer-Verlag, 1995.
    PS
    DOI
  3. Volker Diekert and Paul Gastin
    A Domain for Concurrent Termination: A Generalization of Mazurkiewicz traces
    Proc. 22nd International Colloquium Automata, Languages and Programming (ICALP’95), Szeged, volume 944 of Lecture Notes in Computer Science, pages 15–26. Springer-Verlag, 1995.
    DOI
  4. Volker Diekert , Anca Muscholl and Klaus Reinhardt
    On Codings of Traces
    Proc. 12th Annual Symposium on Theoretical Aspects of Computer Science (STACS’95), Munich (Germany), volume 900 of Lecture Notes in Computer Science, pages 385–396. Springer-Verlag, 1995.
    DOI
  5. Volker Diekert , Paul Gastin and Antoine Petit
    Recent Developments in Trace Theory
    Developments in Language Theory II, pages 373–385. World Scientific, 1995.
  6. Ulrich Hertrampf
    Classes of Bounded Counting Type and their Inclusion Relations
    STACS 95 (Munich, 1995), volume 900 of Lecture Notes in Computer Science, pages 60–70. Springer, 1995.
    DOI
  7. Ulrich Hertrampf , Heribert Vollmer and Klaus W. Wagner
    On the Power of Number-Theoretic Operations with Respect to Counting
    Structure in Complexity Theory Conference, pages 299–314. 1995.
    WWW
  8. Holger Petersen
    Some Results Concerning Two-Dimensional Turing Machines and Finite Automata
    Proc. 10th Fundamentals of Computation Theory (FCT ’95), Dresden (Germany) 1995, volume 965 of Lecture Notes in Computer Science, pages 374–382. Springer-Verlag, 1995.
    PDF
    DOI
  9. Holger Petersen
    Alternation in simple devices
    Proc. 22nd International Colloquium Automata, Languages and Programming (ICALP’95), Szeged, volume 944 of Lecture Notes in Computer Science, pages 315–323. Springer-Verlag, 1995.
    DOI
  10. Klaus Reinhardt
    Counting and empty alternating pushdown automata
    Proc. 7th International Meeting of Young Computer Scientists, Smolenice, Czechoslovakia, 16-20 November 1992 (IMYCS’92), 1995.

Book Chapters

  1. Volker Diekert
    Komplexitätstheorie
    Teubner Taschenbuch der Mathematik, Teil II, pages 65–79. Teubner, 1995.
  2. Volker Diekert and Anca Muscholl
    Construction of Asynchronous Automata
    The Book of Traces, Chapter 8, pages 249–267. World Scientific, 1995.

Books

  1. The Book of Traces
    World Scientific, 1995.
    JPG

1994

Journal Articles

  1. Volker Diekert
    A partial trace semantics for Petri nets
    Theoretical Computer Science. 134:87–105. 1994.
    DOI
  2. Volker Diekert and Anca Muscholl
    Deterministic asynchronous automata for infinite traces
    Acta Informatica. 31:379–397. 1994.
    DOI
  3. Volker Diekert , Edward Ochmański and Klaus Reinhardt
    On confluent semi-commutation systems — decidability and complexity results
    Information and Computation. 110:164–182. 1994.
    DOI
  4. Eric Allender and Ulrich Hertrampf
    Depth Reduction for Circuits of Unbounded Fan-In
    Information and Computation. 112(2):217–238. 1994.
    DOI

Conference Articles

  1. Volker Diekert
    Partial Traces
    Words, Languages and Combinatorics II (Kyoto, Japan 1992), pages 87–97. World Scientific, Singapore, 1994.
  2. Anca Muscholl
    On the complementation of Büchi asynchronous cellular automata
    Proc. 21st International Colloquium Automata, Languages and Programming (ICALP’94), Jerusalem, volume 820 of Lecture Notes in Computer Science, pages 142–153. Springer-Verlag, 1994.
    PDF
    DOI
  3. Ulrich Hertrampf
    Complexity Classes Defined via k-valued Functions
    Structure in Complexity Theory Conference, pages 224–234. 1994.
  4. Ulrich Hertrampf
    Complexity Classes with Finite Acceptance Type
    STACS 94 (Caen, 1994), volume 775 of Lecture Notes in Computer Science, pages 543–553. Springer, 1994.
    DOI

Theses

  1. Werner Ebinger
    Charakterisierung von Sprachklassen unendlicher Spuren durch Logiken
    Dissertation, Institut für Informatik, Universität Stuttgart, 1994.
  2. Anca Muscholl
    Über die Erkennbarkeit unendlicher Spuren
    PhD thesis, Institut für Informatik, Universität Stuttgart, 1994.
    PDF

1993

Journal Articles

  1. Volker Diekert
    On the concatenation of infinite traces
    Theoretical Computer Science. 113:35–54. 1993.
    DOI
  2. Volker Diekert
    Möbius functions and confluent semi-commutations
    Theoretical Computer Science. 108:25–43. 1993.
    DOI
  3. Eric Allender , Richard Beigel , Ulrich Hertrampf and Steven Homer
    Almost-everywhere Complexity Hierarchies for Nondeterministic Time
    Theoretical Computer Science. 115(2):225–241. 1993.
    DOI

Conference Articles

  1. Volker Diekert
    Rewriting, semi-commutations, and Möbius functions
    Proc. 9th Fundamentals of Computation Theory (FCT’93), Szeged (Hungary) 1993, volume 710 of Lecture Notes in Computer Science, pages 1–15. Springer-Verlag, 1993.
    DOI
  2. Volker Diekert
    Complex and complex-like traces
    Proc. 18th Symposium on Mathematical Foundations of Computer Science (MFCS’93), Gdansk (Poland), 1993, volume 711 of Lecture Notes in Computer Science, pages 68–82. Springer-Verlag, 1993.
    DOI
  3. Volker Diekert and Anca Muscholl
    Deterministic asynchronous automata for infinite traces
    Proc. 10th Annual Symposium on Theoretical Aspects of Computer Science (STACS’93), Würzburg (Germany), 1993, volume 665 of Lecture Notes in Computer Science, pages 617–628. Springer-Verlag, 1993.
    DOI
  4. Werner Ebinger and Anca Muscholl
    Logical definability on infinite traces
    Proc. 20th International Colloquium Automata, Languages and Programming (ICALP’93), Lund, volume 700 of Lecture Notes in Computer Science, pages 335–346. Springer-Verlag, 1993.
    DOI
  5. Ulrich Hertrampf , Clemens Lautemann , Thomas Schwentick , Heribert Vollmer and Klaus W. Wagner
    On the Power of Polynomial Time Bit-Reductions
    Proceedings of the Eighth Annual Structure in Complexity Theory Conference (San Diego, CA, 1993), pages 200–207. IEEE Comput. Soc. Press, 1993.
    DOI

1992

Journal Articles

  1. Volker Diekert
    Mathematical aspects of trace theory
    Mitt. Math. Ges. Hamburg. 12:1171–1181. 1992.
  2. Gerhard Buntrock , Carsten Damm , Ulrich Hertrampf and Christoph Meinel
    Structure and Importance of Logspace-MOD-Classes
    Math. Systems Theory. 25(3):223–237. 1992.
    DOI

Conference Articles

  1. Volker Diekert
    Möbius functions and confluent semi-commutation systems
    Words, Languages and Combinatorics (Kyoto, Japan 1990), pages 119–130. World Scientific, Singapore, 1992.
    DOI
  2. Werner Ebinger
    On logical definability of ω ω -trace languages
    Proceedings ASMICS Workshop Infinite Traces, Tübingen, Bericht 4/92, pages 106–122. Universität Stuttgart, Fakultät Informatik, 1992.
  3. Celia Wrathall , Volker Diekert and Friedrich Otto
    One-Rule Trace-Rewriting Systems and Confluence
    Proc. 17th Symposium on Mathematical Foundations of Computer Science (MFCS’92), Prague (Czechoslovakia), 1992, volume 629 of Lecture Notes in Computer Science, pages 511–521. Springer-Verlag, 1992.
    DOI
  4. Ulrich Hertrampf
    Locally Definable Acceptance Types for Polynomial Time Machines
    STACS 92 (Cachan, 1992), volume 577 of Lecture Notes in Computer Science, pages 199–207. Springer, 1992.
    DOI
  5. Ulrich Hertrampf
    Locally Definable Acceptance Types — The Three-Valued Case
    LATIN ’92 (São Paulo, 1992), volume 583 of Lecture Notes in Computer Science, pages 262–271. Springer, 1992.
    DOI
  6. Klaus Reinhardt
    Sorting in-place with a worst case complexity of n \log n
		  - 1.3 n + \cal O(\log n) n \log n - 1.3 n + \cal O(\log n) comparisons and εn
		  \log n + \cal O(1) εn \log n + \cal O(1) transports
    Third International Symposium, ISAAC ’92, Nagoya, Japan, December 16-18, 1992. Proceedings, volume 650 of Lecture Notes in Computer Science, pages 489–498. Springer-Verlag, 1992.
    DOI

1991

Journal Articles

  1. Volker Diekert and Ronald V. Book
    On “inherently context-sensitive” languages – An application of complexity cores
    Information Processing Letters. 40:21–23. 1991.
    DOI

Conference Articles

  1. Volker Diekert , Paul Gastin and Antoine Petit
    Recognizable complex trace languages
    Proc. 16th Symposium on Mathematical Foundations of Computer Science (MFCS’91), Kazimierz Dolny (Poland), 1991, volume 520 of Lecture Notes in Computer Science, pages 131–140. Springer-Verlag, 1991.
    DOI
  2. Volker Diekert
    On the concatenation of infinite traces
    Proc. 8th Annual Symposium on Theoretical Aspects of Computer Science (STACS’91), Hamburg (Germany), 1991, volume 480 of Lecture Notes in Computer Science, pages 105–117. Springer-Verlag, 1991.
    DOI
  3. Volker Diekert , Edward Ochmański and Klaus Reinhardt
    On confluent semi-commutation systems — decidability and complexity results
    Proc. 18th International Colloquium Automata, Languages and Programming (ICALP’91), Madrid, volume 510 of Lecture Notes in Computer Science, pages 229–241. Springer-Verlag, 1991.
    DOI
  4. Ulrich Hertrampf and Klaus Wagner
    Interactive Proof Systems: Provers, Rounds, and Error Bounds
    Computer science logic (Heidelberg, 1990), volume 533 of Lecture Notes in Computer Science, pages 261–273. Springer, 1991.
    DOI

Book Chapters

  1. Gerhard Buntrock , Carsten Damm , Ulrich Hertrampf and Christoph Meinel
    Structure and importance of logspace-mod-classes
    STACS 91 (Hamburg, 1991), volume 480 of Lecture Notes in Computer Science, pages 360–371. Springer, 1991.
    DOI

1990

Journal Articles

  1. Volker Diekert
    Research topics in the theory of free partially commutative monoids
    Bulletin of the European Association for Theoretical Computer Science (EATCS). 40:479–491. Febuary 1990.
  2. Volker Diekert
    Word problems over traces which are solvable in linear time
    Theoretical Computer Science. 74:3–18. 1990.
    DOI
  3. Ulrich Hertrampf
    Relations among MOD-classes
    Theoretical Computer Science. 74(3):325–328. Elsevier Science Publishers Ltd., 1990.
    DOI

Conference Articles

  1. Volker Diekert
    Combinatorial rewriting on traces
    Proc. 7th Annual Symposium on Theoretical Aspects of Computer Science (STACS’90), Rouen (France), 1990, volume 415 of Lecture Notes in Computer Science, pages 138–151. Springer-Verlag, 1990.
    DOI
  2. Eric Allender , Richard Beigel , Ulrich Hertrampf and Steven Homer
    A Note on the Almost-Everywhere Hierarchy for Nondeterministic Time
    STACS 90 (Rouen, 1990), volume 415 of Lecture Notes in Computer Science, pages 1–11. Springer, 1990.
    DOI
  3. Richard Beigel , John Gill and Ulrich Hertrampf
    Counting Classes: Thresholds, Parity, Mods, and Fewness
    STACS 90 (Rouen, 1990), volume 415 of Lecture Notes in Computer Science, pages 49–57. Springer, 1990.
    DOI

Books

  1. Volker Diekert
    Combinatorics on Traces
    In volume 454 of Lecture Notes in Computer Science. Springer-Verlag, 1990.
    DOI

Book Chapters

  1. Eric Allender and Ulrich Hertrampf
    On the Power of Uniform Families of Constant Depth Threshold Circuits
    Mathematical foundations of computer science (Banská Bystrica, 1990), volume 452 of Lecture Notes in Computer Science, pages 158–164. Springer, 1990.
    DOI

1989

Journal Articles

  1. Volker Diekert
    On the Knuth-Bendix completion for concurrent processes
    Theoretical Computer Science. 66:117–136. 1989.
    DOI
  2. Volker Diekert and Axel Möbus
    Hotz-isomorphism theorems in Formal Language Theory
    R.A.I.R.O. — Informatique Théorique et Applications. 23:29–43. 1989.
  3. Volker Diekert and Walter Vogler
    On the synchronization of traces
    Mathematical Systems Theory. 22:161–175. 1989.
    DOI

Conference Articles

  1. Volker Diekert
    Word problems over traces which are solvable in linear time
    Proc. 6th Annual Symposium on Theoretical Aspects of Computer Science (STACS 1989), Paderborn (Germany), volume 349 of Lecture Notes in Computer Science, pages 168–180. Springer-Verlag, 1989.
    DOI

1988

Conference Articles

  1. Volker Diekert
    Transitive orientations, Möbius functions and complete semi-Thue systems for free partially commutative monoids
    Proc. 15th International Colloquium Automata, Languages and Programming (ICALP’88), Tampere, volume 317 of Lecture Notes in Computer Science, pages 176–187. Springer-Verlag, 1988.
    DOI
  2. Volker Diekert and Manfred Kudlek
    Small deterministic Turing machines
    Proc. 2nd Conference on Automata, Languages and Programming Systems, Salgótarján (Hungary) 1988, pages 77–87. Department of Mathematics, Karl Marx University of Economics, 1988.
  3. Volker Diekert and Axel Möbus
    Hotz-isomorphism theorems in Formal Language Theory
    Proc. 5th Annual Symposium on Theoretical Aspects of Computer Science (STACS’88), Bordeaux (France), 1988, volume 294 of Lecture Notes in Computer Science, pages 126–135. Springer-Verlag, 1988.
    DOI
  4. Volker Diekert and Walter Vogler
    Local checking of trace synchronizability
    Proc. 13th Symposium on Mathematical Foundations of Computer Science (MFCS’88), Carlsbad (Czechoslovakia), 1988, volume 324 of Lecture Notes in Computer Science, pages 271–279. Springer-Verlag, 1988.
    DOI

1987

Journal Articles

  1. Volker Diekert
    On some variants of the Ehrenfeucht conjecture
    Theoretical Computer Science. 46:313–318. 1987.
    DOI

Conference Articles

  1. Volker Diekert
    On the Knuth-Bendix completion for concurrent processes
    Proc. 14th International Colloquium Automata, Languages and Programming (ICALP’87), Karlsruhe, volume 267 of Lecture Notes in Computer Science, pages 42–53. Springer-Verlag, 1987.
    DOI
  2. Volker Diekert
    Some remarks on presentations by finite Church-Rosser Thue systems
    Proc. 4th Annual Symposium on Theoretical Aspects of Computer Science (STACS’87), Passau (Germany), volume 247 of Lecture Notes in Computer Science, pages 272–285. Springer-Verlag, 1987.
    DOI

Technical Reports

  1. Volker Diekert
    Two contributions to the theory of finite replacement systems
    Report, Document number: TUM-I8710. Institut für Informatik der Technischen Universität München, 1987.

1986

Journal Articles

  1. Volker Diekert
    Eine Bemerkung zu freien Moduln über regulären lokalen Ringen
    Journal of Algebra. 101:188–189. 1986.
  2. Volker Diekert
    Investigations of Hotz groups for arbitrary grammars
    Acta Informatica. 22(6):679–698. 1986.
    DOI
  3. Volker Diekert
    Complete semi-Thue systems for abelian groups
    Theoretical Computer Science. 44:199–208. 1986.
    DOI
  4. Volker Diekert
    Commutative monoids have complete presentations by free (non-commutative) monoids
    Theoretical Computer Science. 46:319–327. 1986.
    DOI

1985

Conference Articles

  1. Volker Diekert
    A complete non-preperfect presentation of a context-free monoid
    Combinatorial Algorithms in Algebraic Structures, pages 60–66. Fachbereich Informatik der Universität Kaiserslautern, 1985.
  2. Volker Diekert
    On Hotz groups and homomorphic images of sentential form languages
    Proc. 2nd Annual Symposium on Theoretical Aspects of Computer Science (STACS’85), Saarbrücken (Germany), 1985, volume 182 of Lecture Notes in Computer Science, pages 87–97. Springer-Verlag, 1985.
    DOI

1984

Journal Articles

  1. Volker Diekert
    Über die absolute Galoisgruppe dyadischer Zahlkörper
    Journal für die reine und angewandte Mathematik. 350:152–172. 1984.

1983

Journal Articles

  1. Volker Diekert
    Demuškin-Erzeugende und Einbettungsprobleme elementar abelscher 2 2 -Erweiterungen zwei-adischer Zahlkörper
    Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. 53:28–38. Springer, 1983.
    DOI

1981

Journal Articles

  1. Volker Diekert
    Abelsche p-Erweiterungen \wp \wp -adischer Zahlkörper, über denen jedes Einbettungsproblem lösbar ist
    Journal für die reine und angewandte Mathematik. 323:101–104. 1981.

News

[Jun’23] The paper “Parallel algorithms for power circuits and the word problem of the Baumslag group” by Caroline Mattes and Armin Weiß has been accepted at Computational Complexity.

[Oct’22] The paper “Lower Bounds for Sorting 16, 17, and 18 Elements” by Florian Stober and Armin Weiß has been accepted at ALENEX 2023.

[Sep’22] The paper “Conelikes and Ranker Comparisons” by Viktor Henriksson and Manfred Kufleitner has been accepted at LATIN 2022.

[Sep’22] The paper “Improved Parallel Algorithms for Generalized Baumslag Groups” by Caroline Mattes and Armin Weiß has been accepted at LATIN 2022.

[Apr’22] The paper “Reachability Games and Parity Games” by Volker Diekert and Manfred Kufleitner has been accepted at ICTAC 2022.

[Apr’22] The paper “Satisfiability Problems for Finite Groups” by Pawel M. Idziak, Piotr Kawalek, Jacek Krzaczkowski and Armin Weiß has been accepted at ICALP 2022.

[Mar’22] The paper “The Power Word Problem in Graph Products” by Florian Stober and Armin Weiß was accepted at DLT 2022.

[Nov’20] Volker Diekert is Partner Investigator in the Australian ARC grant “Geodetic groups: foundational problems in algebra and computer science” at University of Technology Sydney.

[Apr’20] The paper “Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems” by Laurent Bartholdi, Michael Figelius, Markus Lohrey and Armin Weiß has been accepted at CCC 2020.

[Apr’20] The paper “Hardness of equations over finite solvable groups under the exponential time hypothesis” by Armin Weiß has been accepted at ICALP 2020.

[Dec’19] The paper “An Automaton Group with PSPACE-Complete Word Problem” by Jan Philipp Wächter and Armin Weiß has been accepted at STACS 2020.

[Nov’19] Carlos Camino was awarded the stuvus Special Prize for exceptional commitment in teaching.

[Jun’19] The paper “The power word problem” by Markus Lohrey and Armin Weiß has been accepted at MFCS 2019.

[May’19] The paper “On the Average Case of MergeInsertion” by Florian Stober and Armin Weiß has been accepted at IWOCA 2019.

[Oct’18] The paper “Worst-Case Efficient Sorting with QuickMergesort” by Stefan Edelkamp and Armin Weiß has been accepted at ALENEX 2019.

[Jun’18] At CCC 2018, Lukas Fleischer received a Best Student Paper Award for his submission “On the Complexity of the Cayley Semigroup Membership Problem”.

[Jun’18] The paper “Testing Simon’s congruence” by Lukas Fleischer and Manfred Kufleitner was accepted at MFCS 2018.

[Jun’18] The paper “The Intersection Problem for Finite Semigroups” by Lukas Fleischer was accepted at DLT 2018.

[Apr’18] The paper “The isomorphism problem for finite extensions of free groups is in PSPACE” by Géraud Sénizergues and Armin Weiß was accepted at ICALP 2018.

[Apr’18] The paper “On the Complexity of the Cayley Semigroup Membership Problem” by Lukas Fleischer was accepted at CCC 2018.

[Jan’18] On March 24-29, 2019 Volker Diekert, Markus Lohrey, Olga Kharlampovich and Alexei Miasnikov will organize the Schloss Dagstuhl Seminar “Algorithmic Problems in Group Theory”.

[Dec’17] The paper “The Intersection Problem for Finite Monoids” by Lukas Fleischer and Manfred Kufleitner was accepted at STACS 2018.

[Jun’17] At the 12th International Computer Science Symposium in Russia (CSR), Lukas Fleischer and Manfred Kufleitner received a Best Paper Award for their publication “Green’s Relations in Finite Transformation Semigroups”, and Armin Weiss received a Best Paper Award for “The conjugacy problem in free solvable groups and wreath product of abelian groups is in $\text{TC}^0$ \text{TC}^0 “ which is joint work with Alexei Miasnikov and Svetla Vassileva.