Search Results

Documents authored by Diekert, Volker

Document
DOI: 10.4230/DagRep.9.3.83
Algorithmic Problems in Group Theory (Dagstuhl Seminar 19131)

Authors: Volker Diekert, Olga Kharlampovich, Markus Lohrey, and Alexei Myasnikov

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.ICALP.2017.96
Solutions of Twisted Word Equations, EDT0L Languages, and Context-Free Groups

Authors: Volker Diekert and Murray Elder

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.ICALP.2016.127
Solutions of Word Equations Over Partially Commutative Structures

Authors: Volker Diekert, Artur Jez, and Manfred Kufleitner

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.ICALP.2016.129
Characterizing Classes of Regular Languages Using Prefix Codes of Bounded Synchronization Delay

Authors: Volker Diekert and Tobias Walter

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.STACS.2012.218
Efficient algorithms for highly compressed data: The Word Problem in Higman's group is in P

Authors: Volker Diekert, Jürn Laun, and Alexander Ushakov

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.STACS.2009.1818
Fragments of First-Order Logic over Infinite Words

Authors: Volker Diekert and Manfred Kufleitner

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

Abstract
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.
Cite as

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
DOI: 10.4230/DagSemRep.292
Logic, Algebra, and Formal Verification of Concurrent Systems (Dagstuhl Seminar 00481)

Authors: Volker Diekert, Manfred Droste, Anca Muscholl, and Doron Peled

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

Abstract
Cite as

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},
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact