Document

**Published in:** Dagstuhl Reports, Volume 9, Issue 3 (2019)

Since its early days, combinatorial group theory was deeply interwoven with computability theory. In the last 20 years we have seen many new successful interactions between group theory and computer science. On one hand, groups played an important rule in many developments in complexity theory and automata theory. On the other hand, concepts from these computer science fields as well as efficient algorithms, cryptography, and data compression led to the formulation of new questions in group theory. The Dagstuhl Seminar Algorithmic Problems in Group Theory was aimed at bringing together researchers from group theory and computer science so that they can share their expertise. This report documents the material presented during the course of the seminar.

Volker Diekert, Olga Kharlampovich, Markus Lohrey, and Alexei Myasnikov. Algorithmic Problems in Group Theory (Dagstuhl Seminar 19131). In Dagstuhl Reports, Volume 9, Issue 3, pp. 83-110, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{diekert_et_al:DagRep.9.3.83, author = {Diekert, Volker and Kharlampovich, Olga and Lohrey, Markus and Myasnikov, Alexei}, title = {{Algorithmic Problems in Group Theory (Dagstuhl Seminar 19131)}}, pages = {83--110}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2019}, volume = {9}, number = {3}, editor = {Diekert, Volker and Kharlampovich, Olga and Lohrey, Markus and Myasnikov, Alexei}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.3.83}, URN = {urn:nbn:de:0030-drops-112939}, doi = {10.4230/DagRep.9.3.83}, annote = {Keywords: algorithmic group theory; generic-case complexity; circuit complexity; diophantine theories} }

Document

**Published in:** LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

We prove that the full solution set of a twisted word equation with regular constraints is an EDT0L language. It follows that the set of solutions to equations with rational constraints in a context-free group (= finitely generated virtually free group) in reduced normal forms is EDT0L. We can also decide whether or not the solution set is finite, which was an open problem. Moreover, this can all be done in PSPACE. Our results generalize the work by Lohrey and Senizergues (ICALP 2006) and Dahmani and Guirardel (J. of Topology 2010) with respect to complexity and with respect to expressive power. Both papers show that satisfiability is decidable, but neither gave any concrete complexity bound. Our results concern all solutions, and give, in some sense, the "optimal" formal language characterization.

Volker Diekert and Murray Elder. Solutions of Twisted Word Equations, EDT0L Languages, and Context-Free Groups. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 96:1-96:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{diekert_et_al:LIPIcs.ICALP.2017.96, author = {Diekert, Volker and Elder, Murray}, title = {{Solutions of Twisted Word Equations, EDT0L Languages, and Context-Free Groups}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {96:1--96:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.96}, URN = {urn:nbn:de:0030-drops-73976}, doi = {10.4230/LIPIcs.ICALP.2017.96}, annote = {Keywords: Twisted word equation, EDT0L, virtually free group, context-free group} }

Document

**Published in:** LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

We give NSPACE(n*log(n)) algorithms solving the following decision problems. Satisfiability: Is the given equation over a free partially commutative monoid with involution (resp. a free partially commutative group) solvable? Finiteness: Are there only finitely many solutions of such an equation? PSPACE algorithms with worse complexities for the first problem are known, but so far, a PSPACE algorithm for the second problem was out of reach. Our results are much stronger: Given such an equation, its solutions form an EDT0L language effectively representable in NSPACE(n*log(n)). In particular, we give an effective description of the set of all solutions for equations with constraints in free partially commutative monoids and groups.

Volker Diekert, Artur Jez, and Manfred Kufleitner. Solutions of Word Equations Over Partially Commutative Structures. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 127:1-127:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{diekert_et_al:LIPIcs.ICALP.2016.127, author = {Diekert, Volker and Jez, Artur and Kufleitner, Manfred}, title = {{Solutions of Word Equations Over Partially Commutative Structures}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {127:1--127:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.127}, URN = {urn:nbn:de:0030-drops-62624}, doi = {10.4230/LIPIcs.ICALP.2016.127}, annote = {Keywords: Word equations, EDT0L language, trace monoid, right-angled Artin group, partial commutation} }

Document

**Published in:** LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

In this paper we continue a classical work of Schützenberger on codes with bounded synchronization delay. He was interested in characterizing those regular languages where the groups in the syntactic monoid belong to a variety H. He allowed operations on the language side which are union, intersection, concatenation and modified Kleene-star involving a mapping of a prefix code of bounded synchronization delay to a group G in H, but no complementation. In our notation this leads to the language classes SD_G(A^{infinity}) and SD_H(A^{infinity}). Our main result shows that SD_H(A^{infinity}) always corresponds to the languages having syntactic monoids where all subgroups are in H. Schützenberger showed this for a variety H if H contains Abelian groups, only. Our method shows the general result for all H directly on finite and infinite words. Furthermore, we introduce the notion of local Rees extensions which refers to a simple type of classical Rees extensions. We give a decomposition of a monoid in terms of its groups and local Rees extensions. This gives a somewhat similar, but simpler decomposition than in Rhodes' synthesis theorem. Moreover, we need a singly exponential number of operations, only. Finally, our decomposition yields an answer to a question in a recent paper of Almeida and Klíma about varieties that are closed under Rees extensions.

Volker Diekert and Tobias Walter. Characterizing Classes of Regular Languages Using Prefix Codes of Bounded Synchronization Delay. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 129:1-129:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{diekert_et_al:LIPIcs.ICALP.2016.129, author = {Diekert, Volker and Walter, Tobias}, title = {{Characterizing Classes of Regular Languages Using Prefix Codes of Bounded Synchronization Delay}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {129:1--129:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.129}, URN = {urn:nbn:de:0030-drops-62642}, doi = {10.4230/LIPIcs.ICALP.2016.129}, annote = {Keywords: formal language, synchronization delay, variety, Rees extension} }

Document

**Published in:** LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Power circuits are data structures which support efficient algorithms
for highly compressed integers. Using this new data structure it has
been shown recently by Myasnikov, Ushakov and Won that the Word Problem of the one-relator Baumslag group is in P. Before that the best known upper bound was non-elementary. In the present paper we provide new results for power circuits and we give new applications in algorithmic group theory: 1. We define a modified reduction procedure on power circuits which runs in quadratic time thereby improving the known cubic time complexity. 2. We improve the complexity of the Word Problem for the Baumslag group to cubic time thereby providing the first practical algorithm for that problem. (The algorithm has been implemented and is available in the CRAG library.) 3. The main result is that the Word Problem of Higman's group is decidable in polynomial time. The situation for Higman's group is more complicated than for the Baumslag group and forced us to advance the theory of Power Circuits.

Volker Diekert, Jürn Laun, and Alexander Ushakov. Efficient algorithms for highly compressed data: The Word Problem in Higman's group is in P. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 218-229, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{diekert_et_al:LIPIcs.STACS.2012.218, author = {Diekert, Volker and Laun, J\"{u}rn and Ushakov, Alexander}, title = {{Efficient algorithms for highly compressed data: The Word Problem in Higman's group is in P}}, booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)}, pages = {218--229}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-35-4}, ISSN = {1868-8969}, year = {2012}, volume = {14}, editor = {D\"{u}rr, Christoph and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.218}, URN = {urn:nbn:de:0030-drops-34204}, doi = {10.4230/LIPIcs.STACS.2012.218}, annote = {Keywords: Algorithmic group theory, Data structures, Compression, Word Problem} }

Document

**Published in:** LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

We give topological and algebraic characterizations as well as language theoretic descriptions of the following subclasses of first-order logic $\mathrm{FO}[<]$ for $\omega$-languages: $\Sigma_2$, $\Delta_2$, $\mathrm{FO}^2 \cap \Sigma_2$ (and by duality $\mathrm{FO}^2 \cap \Pi_2$), and $\mathrm{FO}^2$. These descriptions extend the respective results for finite words. In particular, we relate the above fragments to language classes of certain (unambiguous) polynomials. An immediate consequence is the decidability of the membership problem of these classes, but this was shown before by Wilke (1998) and Boja{\'n}czyk (2008) and is therefore not our main focus. The paper is about the interplay of algebraic, topological, and language theoretic properties.

Volker Diekert and Manfred Kufleitner. Fragments of First-Order Logic over Infinite Words. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 325-336, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{diekert_et_al:LIPIcs.STACS.2009.1818, author = {Diekert, Volker and Kufleitner, Manfred}, title = {{Fragments of First-Order Logic over Infinite Words}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {325--336}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1818}, URN = {urn:nbn:de:0030-drops-18185}, doi = {10.4230/LIPIcs.STACS.2009.1818}, annote = {Keywords: Infinite words, Regular languages, First-order logic, Automata theory, Semigroups, Topology} }

Document

**Published in:** Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Volker Diekert, Manfred Droste, Anca Muscholl, and Doron Peled. Logic, Algebra, and Formal Verification of Concurrent Systems (Dagstuhl Seminar 00481). Dagstuhl Seminar Report 292, pp. 1-26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2001)

Copy BibTex To Clipboard

@TechReport{diekert_et_al:DagSemRep.292, author = {Diekert, Volker and Droste, Manfred and Muscholl, Anca and Peled, Doron}, title = {{Logic, Algebra, and Formal Verification of Concurrent Systems (Dagstuhl Seminar 00481)}}, pages = {1--26}, ISSN = {1619-0203}, year = {2001}, type = {Dagstuhl Seminar Report}, number = {292}, institution = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.292}, URN = {urn:nbn:de:0030-drops-151760}, doi = {10.4230/DagSemRep.292}, }