■
Team
■
Teaching
■
Research
■
Publications
Recent (2020 - 2016)
Former (2015 - 1981)
 

Recent Publications (2020 - 2016)

2020

Journal Articles

  1. Carlos Camino , Volker Diekert , Besik Dundua , Mircea Marin and Géraud Sénizergues
    Regular matching problems for infinite trees
    arXiv e-prints. :18. July 2020.
    BibTeX
  2. Stefan Edelkamp , Armin Weiß and Sebastian Wild
    QuickXsort: A Fast Sorting Scheme in Theory and Practice
    Algorithmica. 82(3):509–588. 2020.
    DOI
    BibTeX
  3. Florian Stober and Armin Weiß
    On the Average Case of MergeInsertion
    Theory Comput. Syst.. 2020.
    DOI
    BibTeX

Conference Articles

  1. Jan Philipp Wächter and Armin Weiß
    An Automaton Group with PSPACE-Complete Word Problem
    37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France, pages 6:1–6:17. 2020.
    DOI
    BibTeX
  2. Laurent Bartholdi , Michael Figelius , Markus Lohrey and Armin Weiß
    Groups with ALOGTIME-Hard Word Problems and PSPACE-Complete Circuit Value Problems
    35th Computational Complexity Conference, CCC 2020, July 28-31, 2020, Saarbrücken, Germany (Virtual Conference), volume 169 of LIPIcs, pages 29:1–29:29. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
    DOI
    BibTeX
  3. Armin Weiß
    Hardness of Equations over Finite Solvable Groups Under the Exponential Time Hypothesis
    47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), pages 102:1–102:19. 2020.
    PDF
    DOI
    arXiv
    BibTeX

2019

Journal Articles

  1. Daniele D’Angeli , Dominik Francoeur , Emanuele Rodaro and Jan Philipp Wächter
    Orbits of Automaton Semigroups and Groups
    ArXiv e-prints. abs/1903.00222 2019.
    PDF
    arXiv
    BibTeX
  2. Jan Philipp Wächter and Armin Weiß
    An Automaton Group with PSPACE-Complete Word Problem
    ArXiv e-prints. abs/1906.03424 2019.
    PDF
    arXiv
    BibTeX
  3. Alexei Miasnikov , Svetla Vassileva and Armin Weiß
    The Conjugacy Problem in Free Solvable Groups and Wreath Products of Abelian Groups is in TC^0 ^0
    Theory Comput. Syst.. 63(4):809–832. 2019.
    DOI
    BibTeX
  4. Stefan Edelkamp and Armin Weiß
    BlockQuicksort: Avoiding Branch Mispredictions in Quicksort
    J. Exp. Algorithmics. 24(1):1.4:1–1.4:22. ACM, 2019.
    DOI
    BibTeX
  5. Laurent Bartholdi , Michael Figelius , Markus Lohrey and Armin Weiß
    Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems
    arXiv eprints. abs/1909.13781 2019.
    BibTeX
  6. Volker Diekert , Igor Potapov and Pavel Semukhin
    Decidability of membership problems for flat rational subsets of GL(2,Q) and singular matrices
    arXiv eprints. abs/1910.02302 2019.
    BibTeX

Conference Articles

  1. Stefan Edelkamp and Armin Weiß
    Worst-Case Efficient Sorting with QuickMergesort
    Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments, ALENEX 2019, San Diego, CA, USA, January 7-8, 2019., pages 1–14. 2019.
    DOI
    BibTeX
  2. Markus Lohrey and Armin Weiß
    The Power Word Problem
    44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, Proceedings, volume 138 of LIPIcs, pages 43:1–43:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
    BibTeX
  3. Florian Stober and Armin Weiß
    On the Average Case of MergeInsertion
    Combinatorial Algorithms - 30th International Workshop, IWOCA 2019, Pisa, Italy, July 23-25, 2019, Proceedings, pages 417–429. 2019.
    DOI
    BibTeX

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

News

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