■
Team
■
Teaching
■
Research
■
Publications
Recent (2023 - 2019)
Former (2018 - 1981)
 

Former Publications (2018 - 1981)

2018

Journal Articles

  1. Lukas Fleischer and Manfred Kufleitner
    The complexity of weakly recognizing morphisms
    RAIRO-Theor. Inf. Appl.. 2018.
    DOI
    BibTeX
  2. Lukas Fleischer and Manfred Kufleitner
    Green’s Relations in Deterministic Finite Automata
    Theory Comput. Syst.. Springer, 2018.
    DOI
    BibTeX
  3. Stefan Edelkamp and Armin Weiß
    QuickMergesort: Practically Efficient Constant-Factor Optimal Sorting
    arXiv eprints. abs/1804.10062 2018.
    BibTeX
  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
    BibTeX
  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.
    BibTeX
  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
    arXiv
    BibTeX
  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
    arXiv
    BibTeX
  8. Géraud Sénizergues and Armin Weiß
    The isomorphism problem for finite extensions of free groups is in PSPACE
    ArXiv e-prints. 2018.
    BibTeX
  9. Stefan Edelkamp , Armin Weiß and Sebastian Wild
    QuickXsort - A Fast Sorting Scheme in Theory and Practice
    arXiv eprints. abs/1811.01259 2018.
    BibTeX

Conference Articles

  1. Lukas Fleischer
    The Intersection Problem for Finite Semigroups
    DLT 2018, Proceedings, volume 11088 of LNCS, pages 318–329. Springer, 2018.
    arXiv
    BibTeX
  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
    arXiv
    BibTeX
  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
    arXiv
    BibTeX
  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
    arXiv
    BibTeX
  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
    BibTeX

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
    BibTeX

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
    © Elsevier
    arXiv
    BibTeX
  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
    BibTeX
  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
    BibTeX
  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
    BibTeX
  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
    arXiv
    BibTeX
  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
    BibTeX
  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
    arXiv
    BibTeX
  8. Tobias Walter
    Parikh-reducing Church–Rosser representations for some classes of regular languages
    Theoretical Computer Science. 702:34 - 47. 2017.
    DOI
    Sciencedirect
    BibTeX
  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
    BibTeX

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
    arXiv
    BibTeX
  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
    arXiv
    BibTeX
  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
    © Springer
    arXiv
    BibTeX
  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
    BibTeX
  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
    BibTeX

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.
    OPUS
    BibTeX

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
    BibTeX

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
    BibTeX
  2. Stefan Edelkamp and Armin Weiß
    BlockQuicksort: How Branch Mispredictions don’t affect Quicksort
    ArXiv e-prints. abs/1604.06697 2016.
    PDF
    arXiv
    BibTeX
  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
    BibTeX
  4. Volker Diekert and Manfred Kufleitner
    A Survey on the Local Divisor Technique
    Theoretical Computer Science. 610:13–23. 2016.
    DOI
    BibTeX
  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
    BibTeX
  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
    BibTeX
  7. Volker Diekert and Armin Weiß
    QuickHeapsort: Modifications and Improved Analysis
    Theory Comput. Syst.. 59(2):209–230. 2016.
    PDF
    DOI
    BibTeX

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
    arXiv
    BibTeX
  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
    © AMS
    arXiv
    BibTeX
  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
    BibTeX
  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
    BibTeX
  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
    BibTeX
  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
    BibTeX

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
    © AMS
    arXiv
    BibTeX

Theses

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

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
    arXiv
    BibTeX
  2. Volker Diekert and Manfred Kufleitner
    Omega-rational expressions with Bounded Synchronization Delay
    Theory of Computing Systems. 56:686–696. Springer-Verlag, 2015.
    DOI
    BibTeX
  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
    BibTeX
  4. Volker Diekert and Tobias Walter
    Asymptotic Approximation for the Quotient Complexities of Atoms
    Acta Cybernetica. 22:349–357. 2015.
    PDF
    BibTeX
  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
    BibTeX

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
    arXiv
    BibTeX
  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
    arXiv
    BibTeX
  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.
    BibTeX
  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.
    BibTeX
  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
    BibTeX
  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
    BibTeX

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
    OPUS
    BibTeX

2014

Journal Articles

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

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.
    BibTeX
  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
    © Springer
    BibTeX
  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
    BibTeX
  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
    BibTeX
  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
    BibTeX
  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.
    BibTeX

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
    BibTeX
  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
    BibTeX
  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
    arXiv
    BibTeX
  4. Volker Diekert and Armin Weiß
    Context-Free Groups and Their Structure Trees
    International Journal of Algebra and Computation. 23:611–642. 2013.
    DOI
    arXiv
    BibTeX
  5. Volker Diekert and Armin Weiß
    Context-Free Groups and Bass-Serre Theory
    ArXiv e-prints. 2013.
    PDF
    arXiv
    BibTeX
  6. Volker Diekert and Jonathan Kausch
    Logspace computations in graph products
    arXiv eprints. 2013.
    PDF
    arXiv
    BibTeX

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
    arXiv
    BibTeX
  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
    arXiv
    © Springer
    BibTeX
  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
    © Springer
    BibTeX

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
    BibTeX

Books

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

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
    arXiv
    © IOS Press
    BibTeX
  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
    arXiv
    Artikel bei © Maison de l’Informatique et des Mathématiques Discrètes
    BibTeX
  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
    © World Scientific
    BibTeX
  4. Volker Diekert , Manfred Kufleitner and Pascal Weil
    Star-Free Languages are Church-Rosser Congruential
    Theoretical Computer Science. 454:129–135. 2012.
    PDF
    DOI
    arXiv
    © 2012, Elsevier
    BibTeX
  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
    arXiv
    © Elsevier
    BibTeX
  6. Volker Diekert and Steffen Kopecki
    Language theoretical properties of hairpin formations
    Theoretical Computer Science. 429:65–73. 2012.
    DOI
    © Elsevier
    BibTeX
  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
    arXiv
    BibTeX
  8. Volker Diekert and Alexei G. Myasnikov
    Group Extensions over Infinite Words
    International Journal of Foundations of Computer Science. 23:1001-1019. 2012.
    DOI
    BibTeX
  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
    arXiv
    © World Scientific
    BibTeX
  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
    arXiv
    BibTeX

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
    © Springer
    BibTeX
  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
    arXiv
    TechRep
    © Springer
    BibTeX
  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
    BibTeX
  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
    arXiv
    © Springer
    BibTeX
  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
    arXiv
    © Springer
    BibTeX
  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
    arXiv
    © Springer
    BibTeX
  7. Volker Diekert and Anca Muscholl
    On Distributed Monitoring of Asynchronous Systems
    WoLLIC, pages 70-84. 2012.
    BibTeX
  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
    arXiv
    © Springer
    BibTeX
  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
    arXiv
    BibTeX
  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
    arXiv
    © Springer
    BibTeX
  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
    BibTeX
  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
    BibTeX

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
    arXiv
    © World Scientific
    BibTeX
  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
    arXiv
    © Springer
    BibTeX
  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
    arXiv
    © World Scientific
    BibTeX
  4. Steffen Kopecki
    On iterated hairpin completion
    Theoretical Computer Science. 412(29):3629–3638. 2011.
    PDF
    DOI
    arXiv
    © Elsevier
    BibTeX
  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
    arXiv
    © IOS Press
    BibTeX
  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
    arXiv
    © World Scientific
    BibTeX

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
    arXiv
    BibTeX
  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
    arXiv
    TechRep
    BibTeX
  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
    arXiv
    © Springer
    BibTeX
  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.
    BibTeX

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
    arXiv
    TechRep
    BibTeX

Book Chapters

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

Theses

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

2010

Journal Articles

  1. Manfred Kufleitner and Pascal Weil
    On the lattice of sub-pseudovarieties of DA
    Semigroup Forum. 81:243–254. 2010.
    DOI
    © Springer
    BibTeX
  2. Volker Diekert , Tero Harju and Dirk Nowotka
    Weinbaum Factorizations of Primitive Words
    Russian Mathematics. 54(1):16–25. 2010.
    PDF
    DOI
    © Springer
    russian version
    © Kasan State University
    BibTeX
  3. Ulrich Hertrampf and Christoph Minnameier
    Resource bounded frequency computations with three errors
    Algorithmica. 56(3):342–363. 2010.
    DOI
    © Springer
    BibTeX
  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
    © Elsevier
    BibTeX

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
    TechRep
    arXiv
    © Springer
    BibTeX
  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
    Technical Report
    © Springer
    BibTeX
  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
    © Springer
    BibTeX

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
    Poster
    © Springer
    BibTeX

proceedings

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

2009

Journal Articles

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

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
    arXiv
    full version
    BibTeX
  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
    arXiv
    © Springer
    BibTeX
  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
    © Universities Press
    BibTeX
  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
    © Springer
    BibTeX
  5. Edgar Binder and Manfred Kufleitner
    Classification tree sources
    Information Theory Workshop, 2009. ITW 2009. IEEE, pages 218–222. 2009.
    DOI
    © IEEE
    BibTeX
  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
    arXiv
    © Springer
    BibTeX
  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
    arXiv
    BibTeX
  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.
    BibTeX
  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
    © Springer
    BibTeX
  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
    © Elsevier
    BibTeX
  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
    © Springer
    BibTeX
  12. Holger Petersen and Szymon Grabowski
    Range mode and range median queries in constant time and sub-quadratic space
    pages 225–228. 2009.
    DOI
    © Elsevier
    BibTeX

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
    © Springer
    BibTeX

Books

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

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
    © Springer Vieweg
    BibTeX
  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
    © Springer Vieweg
    BibTeX

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
    © Elsevier
    BibTeX
  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
    © World Scientific
    BibTeX
  3. Volker Diekert and Markus Lohrey
    Word equations over graph products
    International Journal of Algebra and Computation. 18:493–533. 2008.
    PDF
    DOI
    © World Scientific
    BibTeX
  4. Volker Diekert and Markus Lohrey
    Word Equations over Graph Products
    International Journal of Algebra and Computation. 18(3):493-533. 2008.
    BibTeX
  5. Volker Diekert , Markus Lohrey and Alexander Miller
    Partially commutative inverse monoids
    Semigroup Forum. 77(2):196–226. 2008.
    DOI
    © Springer
    BibTeX
  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
    © World Scientific
    BibTeX
  7. Jean-Pierre Duval , Tero Harju and Dirk Nowotka
    Unbordered factors and Lyndon words.
    Discrete Mathematics. 308(11):2261–2264. 2008.
    PDF
    DOI
    © Elsevier
    BibTeX
  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
    © IOS Press
    BibTeX
  9. Tero Harju and Dirk Nowotka
    Bordered Conjugates of Words over Large Alphabets
    Electronic Journal of Combinatorics. 15(1) 2008.
    PDF
    © E-JC
    BibTeX
  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
    © Springer
    BibTeX

Conference Articles

  1. V. Claus , V. Diekert and H. Petersen
    Partnerschaftsvermittlung
    Taschenbuch der Algorithmen, pages 373-384. Springer-Verlag, 2008.
    BibTeX
  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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX

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
    © Springer
    BibTeX

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
    © AUP
    BibTeX
  2. Volker Claus , Volker Diekert and Holger Petersen
    Partnerschaftsvermittlung
    Taschenbuch der Algorithmen, pages 373–384. Springer, 2008.
    PDF
    DOI
    © Springer
    BibTeX
  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
    © Springer
    BibTeX

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
    © Elsevier
    BibTeX
  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
    © IOS Press
    BibTeX
  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
    © ACM
    BibTeX
  4. Markus Lohrey and Nicole Ondrusch
    Inverse monoids: decidability and complexity of algebraic questions
    Information and Computation . 205(8):1212–1234. 2007.
    PDF
    DOI
    © Elsevier
    BibTeX

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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX
  7. Holger Petersen
    String Matching with Simple Devices
    pages 32–34. 2007.
    DOI
    © Elsevier
    BibTeX

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
    arXiv
    BibTeX

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.
    BibTeX

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
    © Elsevier
    BibTeX
  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
    © World Scientific
    BibTeX
  3. Markus Lohrey
    Word Problems and Membership Problems on Compressed Words
    SIAM J. Comput.. 35(5):1210-1240. 2006.
    PDF
    DOI
    © SIAM
    BibTeX
  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
    © Elsevier
    BibTeX
  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
    © Elsevier
    BibTeX
  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
    © World Scientific
    BibTeX
  7. Amir M. Ben-Amram and Holger Petersen
    Backing Up in Singly Linked Lists
    Journal of the ACM. 53 ACM, 2006.
    DOI
    © ACM
    BibTeX

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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX
  3. Markus Lohrey and Géraud Sénizergues
    Theories of HNN-Extensions and Amalgamated Products
    ICALP, pages 504–515. 2006.
    PDF
    DOI
    © Springer
    BibTeX
  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
    © IEEE Computer Society
    BibTeX
  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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX
  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
    © IEEE Computer Society Press
    BibTeX
  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
    © Springer
    BibTeX

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
    OPUS
    BibTeX

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
    © Springer
    BibTeX

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
    © Springer
    BibTeX

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
    © Elsevier
    BibTeX
  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
    © Elsevier
    BibTeX
  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
    © Elsevier
    BibTeX
  4. Markus Lohrey and Holger Petersen
    Complexity Results for Prefix Grammars
    RAIRO. Informatique Théorique et Applications. 39(3):391–401. 2005.
    DOI
    © EDP Sciences
    BibTeX

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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX

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
    © Springer
    BibTeX

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
    © Springer
    BibTeX
  2. Volker Diekert and Paul Gastin
    Local temporal logic is expressively complete for cograph dependence alphabets
    Information and Computation. 195:30–52. 2004.
    PDF
    © Elsevier
    BibTeX
  3. Markus Lohrey
    Decidability and complexity in automatic monoids
    3340:308–320. Springer, 2004.
    PDF
    DOI
    © Springer
    BibTeX
  4. Markus Lohrey
    Word problems on compressed words
    3142:906–918. Springer, 2004.
    PDF
    DOI
    © Springer
    BibTeX
  5. Markus Lohrey and Anca Muscholl
    Bounded MSC communication
    Information and Computation. 189(2):160–181. Elsevier Science Publishers Ltd., 2004.
    PDF
    DOI
    © Elsevier
    BibTeX
  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
    © World Scientific
    BibTeX

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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX

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
    © Springer
    BibTeX

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
    © Elsevier
    BibTeX
  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
    © Elsevier
    BibTeX
  3. Markus Lohrey
    Automatic structures of bounded degree
    2850:344–358. Springer, 2003.
    PS
    DOI
    © Springer
    BibTeX
  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
    © Springer
    BibTeX

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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX

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
    © Elsevier
    BibTeX
  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
    © World Scientific
    BibTeX
  3. Markus Lohrey
    Safe realizability of high-level message sequence charts
    2421:177–192. Springer, 2002.
    PS
    DOI
    © Springer
    BibTeX
  4. Markus Lohrey
    Axiomatising Divergence
    2380:585–596. Springer, 2002.
    PS
    DOI
    © Springer
    BibTeX
  5. Dietrich Kuske and Markus Lohrey
    On the theory of one-step rewriting in trace monoids
    2380:752–763. Springer, 2002.
    PS
    DOI
    © Springer
    BibTeX
  6. Markus Lohrey and Anca Muscholl
    Bounded MSC communication
    2303:295–309. Springer, 2002.
    PS
    DOI
    © Springer
    BibTeX
  7. Klaus Wich
    Universal Inherence of Cycle-Free Context-Free Ambiguity Functions
    2380:669–680. Springer, 2002.
    PDF
    DOI
    © Springer
    BibTeX

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
    BibTeX
  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
    © Springer
    BibTeX
  3. Holger Petersen
    Survey of Decision Problems for Regular Expressions
    10th International Conference on Automata and Formal Languages (AFL’02), Debrecen, 2002. Proceedings, 2002.
    BibTeX
  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
    © Springer
    BibTeX

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
    © Springer
    BibTeX
  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
    © Cambridge University Press
    BibTeX

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
    arXiv
    BibTeX
  2. Markus Lohrey
    Bounded MSC communication
    Information and Computation. 170(1):1–25. Elsevier Science Publishers Ltd., 2001.
    DOI
    © Elsevier
    BibTeX
  3. Markus Lohrey
    Word Problems for 2-Homogeneous Monoids and Symmetric Logspace
    2136:500–511. Springer, 2001.
    PS
    DOI
    © Springer
    BibTeX
  4. Klaus Wich
    Characterization of Context-Free Languages with Polynomially Bounded Ambiguity
    2136:703–714. Springer, 2001.
    PDF
    DOI
    © Springer
    BibTeX

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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX
  3. Volker Diekert and Anca Muscholl
    Solvability of Equations in Free Partially Commutative Groups is Decidable
    Proc. 28th International Colloquium Automata, Languages and Programming (ICALP’01), volume 2076 of Lecture Notes in Computer Science, pages 543–554. Springer-Verlag, 2001.
    PS
    DOI
    © Springer
    BibTeX
  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
    © Springer
    BibTeX

Theses

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

2000

Journal Articles

  1. Ulrich Hertrampf
    Algebraic acceptance mechanisms for polynomial time machines
    SIGACT News. 31(2):22–33. 2000.
    DOI
    BibTeX
  2. Ulrich Hertrampf
    Quantencomputer
    Informatik-Spektrum. 23(5):322–324. 2000.
    DOI
    © Springer
    BibTeX
  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
    © Elsevier
    BibTeX
  4. Jürgen Gross and Markus Lohrey
    Implementing Luby’s Algorithm on the Cray T3E
    :467–477. Springer, 2000.
    PS
    DOI
    © Springer
    BibTeX

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.
    BibTeX
  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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX
  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
    © World Scientific
    BibTeX

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
    © Elsevier
    BibTeX
  2. Anca Muscholl
    Matching Specifications for Message Sequence Charts
    1578:273–287. Springer, 1999.
    PDF
    DOI
    © Springer
    BibTeX

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
    © Springer
    BibTeX
  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.
    © World Scientific
    BibTeX
  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
    © Springer
    BibTeX

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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX

Theses

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

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
    © IOS Press
    BibTeX
  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
    © Springer
    BibTeX
  3. Volker Diekert and Paul Gastin
    Approximating Traces
    Acta Informatica. 35:567–593. 1998.
    DOI
    © Springer
    BibTeX
  4. Zoltán Ésik and Michael Bertol
    Nonfinite axiomatizability of the equational theory of shuffle
    Acta Informatica. 35:505–539. 1998.
    PS
    DOI
    © Springer
    BibTeX
  5. Markus Lohrey
    NP-Completeness Results Concerning the Transformation of Logic Programs into Attribute Grammars
    Acta Cybernetica. 13(3):209–224. 1998.
    PS
    © University of Szeged
    BibTeX
  6. Holger Hermanns and Markus Lohrey
    Priority and maximal progress are completely axiomatisable (extended abstract)
    1466:237–252. Springer, 1998.
    PS
    DOI
    © Springer
    BibTeX
  7. Anca Muscholl , Doron Peled and Zhendong Su
    Deciding properties for message sequence charts
    1378:226–242. Springer, 1998.
    PDF
    DOI
    © Springer
    BibTeX

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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX

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
    © Springer
    BibTeX

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
    © Elsevier
    BibTeX

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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX
  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
    © Carleton Scientific
    BibTeX
  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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX

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
    © Springer
    BibTeX
  2. Volker Diekert and Yves Métivier
    Partial Commutation and Traces
    Handbook of Formal Languages, Volume 3: Beyond Words., pages 457–533. 1997.
    DOI
    BibTeX
  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
    © IEEE CSP
    BibTeX
  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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX

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.
    BibTeX

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
    © IOS Press
    BibTeX
  2. Werner Ebinger and Anca Muscholl
    Logical definability on infinite traces
    Theoretical Computer Science. 154:67–84. 1996.
    PDF
    BibTeX
  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
    © Elsevier
    BibTeX
  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
    © Elsevier
    BibTeX
  5. U. Hertrampf , H. Vollmer and K. W. Wagner
    On Balanced vs. Unbalanced Computation Trees
    Math. Systems Theory. 29(4):411–421. 1996.
    DOI
    © Springer
    BibTeX

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
    © Springer
    BibTeX
  2. Volker Diekert , Paul Gastin and Antoine Petit
    Recent developments in trace theory
    Developments in Language Theory II, pages 373–385. World Scientific, 1996.
    DLT’95 bei DBLP
    BibTeX
  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
    © Springer
    BibTeX
  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
    BibTeX

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
    © Elsevier
    BibTeX
  2. Celia Wrathall and Volker Diekert
    On Confluence of One-Rule Trace-Rewriting Systems
    Mathematical Systems Theory. 28:341–361. 1995.
    DOI
    © Springer
    BibTeX
  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
    BibTeX

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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX
  5. Volker Diekert , Paul Gastin and Antoine Petit
    Recent Developments in Trace Theory
    Developments in Language Theory II, pages 373–385. World Scientific, 1995.
    DLT’95 bei DBLP
    BibTeX
  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
    © Springer
    BibTeX
  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
    © IEEE CSP
    BibTeX
  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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX
  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.
    BibTeX

Book Chapters

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

Books

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

1994

Journal Articles

  1. Volker Diekert
    A partial trace semantics for Petri nets
    Theoretical Computer Science. 134:87–105. 1994.
    DOI
    © Elsevier
    BibTeX
  2. Volker Diekert and Anca Muscholl
    Deterministic asynchronous automata for infinite traces
    Acta Informatica. 31:379–397. 1994.
    DOI
    © Springer
    BibTeX
  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
    © Elsevier
    BibTeX
  4. Eric Allender and Ulrich Hertrampf
    Depth Reduction for Circuits of Unbounded Fan-In
    Information and Computation. 112(2):217–238. 1994.
    DOI
    © Elsevier
    BibTeX

Conference Articles

  1. Volker Diekert
    Partial Traces
    Words, Languages and Combinatorics II (Kyoto, Japan 1992), pages 87–97. World Scientific, Singapore, 1994.
    BibTeX
  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
    © Springer
    BibTeX
  3. Ulrich Hertrampf
    Complexity Classes Defined via k-valued Functions
    Structure in Complexity Theory Conference, pages 224–234. 1994.
    CoCo 1994 bei DBLP
    BibTeX
  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
    © Springer
    BibTeX

Theses

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

1993

Journal Articles

  1. Volker Diekert
    On the concatenation of infinite traces
    Theoretical Computer Science. 113:35–54. 1993.
    DOI
    © Elsevier
    BibTeX
  2. Volker Diekert
    Möbius functions and confluent semi-commutations
    Theoretical Computer Science. 108:25–43. 1993.
    DOI
    © Elsevier
    BibTeX
  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
    © Elsevier
    BibTeX

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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX
  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
    © IEEE CSP
    BibTeX

1992

Journal Articles

  1. Volker Diekert
    Mathematical aspects of trace theory
    Mitt. Math. Ges. Hamburg. 12:1171–1181. 1992.
    BibTeX
  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
    © Springer
    BibTeX

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
    © Elsevier
    BibTeX
  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.
    BibTeX
  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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX

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
    © Elsevier
    BibTeX

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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX

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
    © Springer
    BibTeX

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.
    BibTeX
  2. Volker Diekert
    Word problems over traces which are solvable in linear time
    Theoretical Computer Science. 74:3–18. 1990.
    DOI
    © Elsevier
    BibTeX
  3. Ulrich Hertrampf
    Relations among MOD-classes
    Theoretical Computer Science. 74(3):325–328. Elsevier Science Publishers Ltd., 1990.
    DOI
    © Elsevier
    BibTeX

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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX

Books

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

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
    © Springer
    BibTeX

1989

Journal Articles

  1. Volker Diekert
    On the Knuth-Bendix completion for concurrent processes
    Theoretical Computer Science. 66:117–136. 1989.
    DOI
    © Elsevier
    BibTeX
  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.
    BibTeX
  3. Volker Diekert and Walter Vogler
    On the synchronization of traces
    Mathematical Systems Theory. 22:161–175. 1989.
    DOI
    © Springer
    BibTeX

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
    © Springer
    BibTeX

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
    © Springer
    BibTeX
  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.
    BibTeX
  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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX

1987

Journal Articles

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

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
    © Springer
    BibTeX
  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
    © Springer
    BibTeX

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.
    BibTeX

1986

Journal Articles

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

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.
    BibTeX
  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
    © Springer
    BibTeX

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.
    BibTeX

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
    © Springer
    BibTeX

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.
    BibTeX

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.