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
  2. Funda Gul and Armin Weiß
    On the dimension of matrix embeddings of torsion-free nilpotent groups
    J. Algebra. 477:516–539. 2017.
    DOI
  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
  4. 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
  5. 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
  6. Tobias Walter
    Parikh-reducing Church–Rosser representations for some classes of regular languages
    Theoretical Computer Science. 702:34 - 47. 2017.
    DOI

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

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

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
  2. Stefan Edelkamp and Armin Weiß
    BlockQuicksort: How Branch Mispredictions don’t affect Quicksort
    ArXiv e-prints. abs/1604.06697 2016.
    PDF
  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
  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
  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

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

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

Theses

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

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

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
  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
  3. Volker Diekert and Manfred Kufleitner
    Omega-rational expressions with Bounded Synchronization Delay
    Theory of Computing Systems. 56:686–696. Springer-Verlag, 2015.
    DOI
  4. Volker Diekert and Manfred Kufleitner
    A Survey on the Local Divisor Technique
    Theoretical Computer Science. 610:13–23. 2015.
    DOI
  5. Volker Diekert and Tobias Walter
    Asymptotic Approximation for the Quotient Complexities of Atoms
    Acta Cybernetica. 22:349–357. 2015.
    PDF
  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

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

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

2014

Journal Articles

  1. Volker Diekert and Martin Leucker
    Topology, monitorable properties and runtime verification
    Theoretical Computer Science. 537:29–41. 2014.
    DOI

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.
  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
  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
  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
  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
  6. Volker Diekert and Jonathan Kausch
    Logspace computations in graph products
    ISSAC, pages 138-145. 2014.

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

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

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

Books

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

News

[Jun’17] Lukas’ paper “Green’s Relations in Finite Transformation Semigroups” and Armin’s paper “The conjugacy problem in free solvable groups and wreath product of abelian groups is in $\text{TC}^0$ \text{TC}^0 “ both have received a Best Paper Award at the 12th International Computer Science Symposium in Russia (CSR).