2022
Journal Articles
- Regular matching problems for infinite treesLogical Methods in Computer Science. Volume 18, Issue 1, 25:1–25:38 2022.
- Parallel complexity for nilpotent groupsInternat. J. Algebra Comput.. 32(5):895–928. 2022.
- Equation Satisfiability in Solvable GroupsTheory of Computing Systems. 2022.
- An Automaton Group with PSPACE-Complete Word ProblemTheory of Computing Systems. 2022.
Conference Articles
- The Isomorphism Problem for Plain Groups Is in39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022, March 15-18, 2022, Marseille, France (Virtual Conference), volume 219 of LIPIcs, pages 26:1–26:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
- Satisfiability problems for finite groupsICALP 2022, Proceedings, volume 229 of LIPIcs, pages 127:1–127:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
- The Power Word Problem in Graph ProductsDevelopments in Language Theory - 26th International Conference, DLT 2022, Proceedings, volume 13257 of Lecture Notes in Computer Science, pages 286–298. Springer, 2022.
Miscellaneous
- Improved Parallel Algorithms for Generalized Baumslag Groups
2021
Journal Articles
- Parallel algorithms for power circuits and the word problem of the Baumslag groupCoRR. abs/2102.09921 2021.
- The isomorphism problem for plain groups is inarXiv eprints. 2021.
Conference Articles
- Properties of Graphs Specified by a Regular LanguageDevelopments 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.
- Parallel Algorithms for Power Circuits and the Word Problem of the Baumslag Group46th 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.
2020
Journal Articles
- QuickXsort: A Fast Sorting Scheme in Theory and PracticeAlgorithmica. 82(3):509–588. 2020.
- Equation satisfiability in solvable groupsarXiv eprints. abs/2010.11788 2020.
- On the Average Case of MergeInsertionTheory Comput. Syst.. 64(7):1197–1224. 2020.
Conference Articles
- An Automaton Group with PSPACE-Complete Word Problem37th 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.
- Groups with ALOGTIME-Hard Word Problems and PSPACE-Complete Circuit Value Problems35th 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.
- Hardness of Equations over Finite Solvable Groups Under the Exponential Time Hypothesis47th 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.
2019
Journal Articles
- Orbits of Automaton Semigroups and GroupsArXiv e-prints. abs/1903.00222 2019.
- An Automaton Group with PSPACE-Complete Word ProblemArXiv e-prints. abs/1906.03424 2019.
- The Conjugacy Problem in Free Solvable Groups and Wreath Products of Abelian Groups is in TCTheory Comput. Syst.. 63(4):809–832. 2019.
- BlockQuicksort: Avoiding Branch Mispredictions in QuicksortJ. Exp. Algorithmics. 24(1):1.4:1–1.4:22. ACM, 2019.
- Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problemsarXiv eprints. abs/1909.13781 2019.
Conference Articles
- Worst-Case Efficient Sorting with QuickMergesortProceedings 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.
- The Power Word Problem44th 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.
- On the Average Case of MergeInsertionCombinatorial Algorithms - 30th International Workshop, IWOCA 2019, Pisa, Italy, July 23-25, 2019, Proceedings, pages 417–429. 2019.
Technical Reports
- Decidability of membership problems for flat rational subsets of GL(2,
) and singular matrices
2019.
2018
Journal Articles
- The complexity of weakly recognizing morphismsRAIRO-Theor. Inf. Appl.. 2018.
- Green’s Relations in Deterministic Finite AutomataTheory Comput. Syst.. Springer, 2018.
- QuickMergesort: Practically Efficient Constant-Factor Optimal SortingarXiv eprints. abs/1804.10062 2018.
- The Word Problem for Omega-Terms over the Trotter-Weil HierarchyTheory of Computing Systems. 62:682–738. Springer, 2018.
- Level two of the quantifier alternation hierarchy over infinite wordsTheory of Computing Systems. 62:467–480. Springer, 2018.
- On the Structure Theory of Partial Automaton SemigroupsArXiv e-prints. abs/1811.09420 2018.
- Orbit Expandability of Automaton Semigroups and GroupsArXiv e-prints. abs/1812.07359 2018.
- The isomorphism problem for finite extensions of free groups is in PSPACEArXiv e-prints. 2018.
- QuickXsort - A Fast Sorting Scheme in Theory and PracticearXiv eprints. abs/1811.01259 2018.
Conference Articles
- The Intersection Problem for Finite SemigroupsDLT 2018, Proceedings, volume 11088 of LNCS, pages 318–329. Springer, 2018.
- Testing Simon’s congruenceMFCS 2018, Proceedings, volume 117 of LIPIcs, pages 62:1–62:13. Dagstuhl Publishing, 2018.
- On the Complexity of the Cayley Semigroup Membership ProblemCCC 2018, Proceedings, volume 102 of LIPIcs, pages 25:1–25:12. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018.
- The Intersection Problem for Finite MonoidsSTACS 2018, Proceedings, volume 96 of LIPIcs, pages 30:1–30:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018.
- The Isomorphism Problem for Finite Extensions of Free Groups Is In PSPACE45th 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.
Book Chapters
- Log-Space Complexity of the Conjugacy Problem in Wreath ProductsInfinite Group Theory, Chapter 12, pages 215-236. World Scientific, 2018.
2017
Journal Articles
- On the dimension of matrix embeddings of torsion-free nilpotent groupsJ. Algebra. 477:516–539. 2017.
- The Half-Levels of the FO2 Alternation HierarchyTheory Comput. Syst.. 61(2):352–370. Springer, 2017.
- Equations Over Free Inverse Monoids with Idempotent VariablesTheory Comput. Syst.. 61:494–520. 2017.
- Characterizing classes of regular languages using prefix codes of bounded synchronization delayInternational Journal of Algebra and Computation. 27:561–590. 2017.
circuits for algorithmic problems in nilpotent groups
ArXiv e-prints. abs/1702.06616 2017.- On the complexity of the word problem for automaton semigroups and automaton groupsAdvances in Applied Mathematics. 90():160 - 187. 2017.
- Automaton Semigroups and Groups: on the Undecidability of Problems Related to Freeness and FinitenessArXiv e-prints. abs/1712.07408 2017.
- Parikh-reducing Church–Rosser representations for some classes of regular languagesTheoretical Computer Science. 702:34 - 47. 2017.
- Amenability of Schreier graphs and strongly generic algorithms for the conjugacy problemJ. Symb. Comput.. 83:147–165. 2017.
Conference Articles
- Church-Rosser Systems, Codes with Bounded Synchronization Delay and Local Rees ExtensionsWORDS 2017, Proceedings, volume 10432 of LNCS, pages 6–16. Springer, 2017.
- Green’s Relations in Finite Transformation SemigroupsCSR 2017, Proceedings, volume 10304 of LNCS, pages 112–125. Springer, 2017.
- The conjugacy problem in free solvable groups and wreath product of abelian groups is inComputer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Kazan, Russia, June 8-12, 2017, Proceedings, pages 217–231. 2017.
- Solutions of Twisted Word Equations, EDT0L Languages, and Context-Free Groups44th 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.
- TC
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.
Theses
- The parallel complexity of certain algorithmic problems in group theoryDissertation, Institut für Formale Methoden der Informatik, Universität Stuttgart, 2017.
Book Chapters
- Context-Free Groups and Bass-Serre TheoryAlgorithmic and Geometric Topics Around Free Groups and Automorphisms, Advanced Courses in Mathematics - CRM Barcelona, Birkhäuser, 2017.