■
Team
■
Teaching
■
Research
■
Publications
Recent (2021 - 2017)
Former (2016 - 1981)
 

Recent Publications (2021 - 2017)

2021

Journal Articles

  1. Caroline Mattes and Armin Weiß
    Parallel algorithms for power circuits and the word problem of the Baumslag group
    CoRR. abs/2102.09921 2021.
    BibTeX
  2. Heiko Dietrich , Murray Elder , Adam Piggott , Youming Qiao and Armin Weiß
    The isomorphism problem for plain groups is in \Sigma_3^\text{P} \Sigma_3^\text{P}
    arXiv eprints. 2021.
    BibTeX
  3. Jan Philipp Wächter and Armin Weiß
    An Automaton Group with PSPACE-Complete Word Problem
    Theory Comput. Syst.. 2021.
    BibTeX

Conference Articles

  1. Volker Diekert , Henning Fernau and Petra Wolf
    Properties of Graphs Specified by a Regular Language
    Developments in Language Theory - 25th International Conference, DLT 2021, Porto, Portugal, August 16-20, 2021, Proceedings, volume 12811 of Lecture Notes in Computer Science, pages 117–129. Springer, 2021.
    DOI
    BibTeX
  2. Caroline Mattes and Armin Weiß
    Parallel Algorithms for Power Circuits and the Word Problem of the Baumslag Group
    46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, August 23-27, 2021, Tallinn, Estonia, volume 202 of LIPIcs, pages 74:1–74:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
    DOI
    BibTeX

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. :1–35. 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. Paweł Idziak , Piotr Kawałek , Jacek Krzaczkowski and Armin Weiß
    Equation satisfiability in solvable groups
    arXiv eprints. abs/2010.11788 2020.
    BibTeX
  4. Florian Stober and Armin Weiß
    On the Average Case of MergeInsertion
    Theory Comput. Syst.. 64(7):1197–1224. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 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

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

News

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