■
Team
■
Teaching
■
Research
■
Publications
Recent (2019 - 2015)
Former (2014 - 1981)
 

Recent Publications (2019 - 2015)

2019

Journal Articles

  1. Daniele D’Angeli , Dominik Francoeur , Emanuele Rodaro and Jan Philipp Wächter
    Orbits of Automaton Semigroups and Groups
    CoRR. abs/1903.00222 2019.
    PDF
    arXiv
    BibTeX
  2. 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
  3. Jan Philipp Wächter and Armin Weiß
    An Automaton Group with PSPACE-Complete Word Problem
    CoRR. abs/1906.03424 2019.
    BibTeX
  4. Laurent Bartholdi , Michael Figelius , Markus Lohrey and Armin Weiß
    Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems
    CoRR. abs/1909.13781 2019.
    BibTeX
  5. Stefan Edelkamp , Armin Weiß and Sebastian Wild
    QuickXsort: A Fast Sorting Scheme in Theory and Practice
    Algorithmica. 2019.
    DOI
    BibTeX
  6. Volker Diekert , Igor Potapov and Pavel Semukhin
    Decidability of membership problems for flat rational subsets of GL(2,Q) and singular matrices
    CoRR. 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., 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. 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 of Computing Systems. Febuary 2018.
    DOI
    BibTeX
  2. Lukas Fleischer and Manfred Kufleitner
    The complexity of weakly recognizing morphisms
    RAIRO-Theor. Inf. Appl.. 2018.
    DOI
    BibTeX
  3. Lukas Fleischer and Manfred Kufleitner
    Green’s Relations in Deterministic Finite Automata
    Theory Comput. Syst.. Springer, 2018.
    DOI
    BibTeX
  4. Stefan Edelkamp and Armin Weiß
    QuickMergesort: Practically Efficient Constant-Factor Optimal Sorting
    CoRR. abs/1804.10062 2018.
    BibTeX
  5. 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
  6. Daniele D’Angeli , Emanuele Rodaro and Jan Philipp Wächter
    Orbit Expandability of Automaton Semigroups and Groups
    CoRR. abs/1812.07359 2018.
    PDF
    arXiv
    BibTeX
  7. Géraud Sénizergues and Armin Weiß
    The isomorphism problem for finite extensions of free groups is in PSPACE
    ArXiv e-prints. 2018.
    BibTeX
  8. Stefan Edelkamp , Armin Weiß and Sebastian Wild
    QuickXsort - A Fast Sorting Scheme in Theory and Practice
    CoRR. 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. Manfred Kufleitner and Jan Philipp Wächter
    The Word Problem for Omega-Terms over the Trotter-Weil Hierarchy
    Theory of Computing Systems. Springer Nature, May 2017.
    DOI
    BibTeX
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
    BibTeX
  8. 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
  9. Tobias Walter
    Parikh-reducing Church–Rosser representations for some classes of regular languages
    Theoretical Computer Science. 702:34 - 47. 2017.
    DOI
    Sciencedirect
    BibTeX
  10. 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 , 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
  5. 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
  6. 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

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

inbook

  1. Manfred Kufleitner and Jan Philipp Wächter
    The Word Problem for Omega-Terms over the Trotter-Weil Hierarchy
    Kulikov, Alexander S. and Woeginger, Gerhard J., editorpages 237–250. Springer International Publishing, 2016.
    DOI
    BibTeX

2015

Journal Articles

  1. Volker Diekert , Manfred Kufleitner , Klaus Reinhardt and Tobias Walter
    Regular Languages Are Church-Rosser Congruential
    J. ACM. 62:39:1–39:20. ACM, November 2015.
    DOI
    BibTeX
  2. 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
  3. Volker Diekert and Manfred Kufleitner
    Omega-rational expressions with Bounded Synchronization Delay
    Theory of Computing Systems. 56:686–696. Springer-Verlag, 2015.
    DOI
    BibTeX
  4. Volker Diekert and Manfred Kufleitner
    A Survey on the Local Divisor Technique
    Theoretical Computer Science. 610:13–23. 2015.
    DOI
    BibTeX
  5. Volker Diekert and Tobias Walter
    Asymptotic Approximation for the Quotient Complexities of Atoms
    Acta Cybernetica. 22:349–357. 2015.
    PDF
    BibTeX
  6. 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

News

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