VDVolker Diekert

Volker Diekert

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Volker Diekert has a total of 41 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Quadratic word equations with regular constraints and the exponent of periodicity

    by Volker Diekert, Silas Natterer, Alexander Thumm

    In this article, we study word equations in free semigroups and the conjecture that the existence of infinitely many solutions entails the existence of solutions with arbitrarily large exponent of periodicity. We examine this question in the broader framework of word equations with regular constraints and establish new positive results: the conjecture holds for all quadratic word equations with constraints in finite semigroups from the variety $$\textbf{DLG}$$ DLG and its dual $$\textbf{DRG}$$ DRG , encompassing all finite groups, commutative semigroups, and $$\mathcal {J}$$ J -trivial semigroups.

  • Solutions of Word Equations over Partially Commutative Structures

    by Volker Diekert, Artur Jez, Manfred Kufleitner, Alexander Thumm

    Let M(A, I) be a free partially commutative monoid with involution and G(A, I) its quotient group (for example, a right-angled Artin or Coxeter group). We show that for any system of word equations over M(A, I) with recognizable constraints, the solution set – in M(A, I) or in G(A, I) – is an EDT0L language. It is given by an NFA [ ] recognizing endomorphisms over some extended monoid. Furthermore, if the input size is n, then [ ] can be constructed effectively by an NSPACE(n log n)-transducer. As a consequence, both Satisfiability (whether the system admits a solution) and Finiteness (whether the solution set is infinite) are decidable in NSPACE(n log n). For a natural subclass of constraints, we conjecture that these problems are NP-complete.

  • Open Access

    Word equations and the exponent of periodicity

    by Volker Diekert, Silas Natterer, Alexander Thumm

    In this article, we study word equations in free semigroups and the conjecture that the existence of infinitely many solutions entails the existence of solutions with arbitrarily large exponent of periodicity. We examine this question in the broader framework of word equations with regular constraints and establish new positive results: the conjecture holds for all quadratic word equations with constraints in finite semigroups from the variety $\mathbf{DLG}$ and its left-right dual $\mathbf{DRG}$, encompassing, in particular, all finite groups, commutative semigroups, and $\mathcal{J}$-trivial semigroups.

  • Open Access

    Decidability of membership problems for flat rational subsets of $\mathrm{GL}(2,\mathbb{Q})$ and singular matrices

    by Volker Diekert, Igor Potapov, Pavel Semukhin

    We consider membership problems for rational sets in matrix semigroups. For a semigroup $M$, the rational sets $\mathrm{Rat}(M)$ are defined as sets accepted by NFA whose transitions are labeled by elements of $M$. The membership problem asks whether $g\in R$, where $g\in M$ and $R\in \mathrm{Rat}(M)$. In this work, we introduce the notion of flat rational sets: if $M$ is a semigroup and $N$ is its subsemigroup, then flat rational sets of $M$ over $N$ are finite unions of the form $L_0g_1L_1 \cdots g_t L_t$ where all $L_i\in \mathrm{Rat}(N)$ and $g_i\in M$. We show that the emptiness problem for Boolean combinations of flat rational subsets of $\mathrm{GL}(2,\mathbb{Q})$ over $\mathrm{GL}(2,\mathbb{Z})$ is decidable. It is possible that the above result cannot be pushed any further due to the following dichotomy: if $G$ is a f.g. group such that $\mathrm{GL}(2,\mathbb{Z}) <G\leq\mathrm{GL}(2,\mathbb{Q})$, then either $G\cong \mathrm{GL}(2,\mathbb{Z})\times \mathbb{Z}^k$ or $G$ contains an extension of the Baumslag-Solitar group of infinite index. In the first case, the membership problem for rational subsets of $G$ is decidable. However, in the second case, the decidability of the membership problem has been open for many years. The latter fact has been the driving force to focus on the class of flat rational sets. It appears as a natural restriction that allowed us to prove new decidability results for $2\times 2$ matrices with rational entries. For example, we prove that the membership problem is decidable in exponential time for flat rational subsets of $\mathrm{GL}(2,\mathbb{Q})$ over $\mathrm{GL}(2,\mathbb{Z})$ but becomes decidable in doubly exponential time if we extend $\mathrm{GL}(2,\mathbb{Z})$ by matrices with determinant greater than $1$. We also show doubly exponential time bound for the membership problem for flat rational subsets that include singular matrices.

  • Reachability Games and Parity Games

    by Volker Diekert, Manfred Kufleitner

  • Open Access

    Properties of graphs specified by a regular language

    by Volker Diekert, Henning Fernau, Petra Wolf

    Traditionally, graph algorithms get a single graph as input, and then they should decide if this graph satisfies a certain property $$\varPhi $$ Φ . What happens if this question is modified in a way that we get a possibly infinite family of graphs as an input, and the question is if there is a graph satisfying $$\varPhi $$ Φ in the family? We approach this question by using formal languages for specifying families of graphs, in particular by regular sets of words. We show that certain graph properties can be decided by studying the syntactic monoid of the specification language L if a certain torsion condition is satisfied. This condition holds trivially if L is regular. More specifically, we use a natural binary encoding of finite graphs over a binary alphabet $$\varSigma $$ Σ , and we define a regular set $$\mathbb {G}\subseteq \varSigma ^*$$ G ⊆ Σ ∗ such that every nonempty word $$w\in \mathbb {G}$$ w ∈ G defines a finite and nonempty graph. Also, graph properties can then be syntactically defined as languages over $$\varSigma $$ Σ . Then, we ask whether the automaton $$\mathcal {A}$$ A specifies some graph satisfying a certain property $$\varPhi $$ Φ . Our structural results show that we can answer this question for all “typical” graph properties. In order to show our results, we split L into a finite union of subsets and every subset of this union defines in a natural way a single finite graph F where some edges and vertices are marked. The marked graph in turn defines an infinite graph $$F^\infty $$ F ∞ and therefore the family of finite subgraphs of $$F^\infty $$ F ∞ where F appears as an induced subgraph. This yields a geometric description of all graphs specified by L based on splitting L into finitely many pieces; then using the notion of graph retraction, we obtain an easily understandable description of the graphs in each piece.


  • Open Access

    Context-Free Groups and Bass-Serre Theory

    by Volker Diekert, Armin Weiß

    The word problem of a finitely generated group is the formal language of words over the generators which are equal to the identity in the group. If this language happens to be context-free, then the group is called context-free. Finitely generated virtually free groups are context-free. In a seminal paper Muller and Schupp showed the converse: A context-free group is virtually free. Over the past decades a wide range of other characterizations of context-free groups have been found. The present notes survey most of these characterizations. Our aim is to show how the different characterizations of context-free groups are interconnected. Moreover, we present a self-contained access to the Muller-Schupp theorem without using Stallings' structure theorem or a separate accessibility result. We also give an introduction to some classical results linking groups with formal language theory.

  • Open Access

    Solutions to twisted word equations and equations in virtually free groups

    by Volker Diekert, Murray Elder

    It is well known that the problem solving equations in virtually free groups can be reduced to the problem of solving twisted word equations with regular constraints over free monoids with involution. In this paper we prove that the set of all solutions of a twisted word equation is an EDT0L language whose specification can be computed in $\mathsf{PSPACE}$. Within the same complexity bound we can decide whether the solution set is empty, finite, or infinite. In the second part of the paper we apply the results for twisted equations to obtain in $\mathsf{PSPACE}$ an EDT0L description of the solution set of equations with rational constraints for finitely generated virtually free groups in standard normal forms with respect to a natural set of generators. If the rational constraints are given by a homomorphism into a fixed (or "small enough") finite monoid, then our algorithms can be implemented in $\mathsf{NSPACE}(n^2\log n)$, that is, in quasi-quadratic nondeterministic space. Our results generalize the work by Lohrey and S\'enizergues (ICALP 2006) and Dahmani and Guirardel (J. of Topology 2010) with respect to both complexity and expressive power. Neither paper gave any concrete complexity bound and the results in these papers are stated for subsets of solutions only, whereas our results concern all solutions.

  • Open Access

    Properties of Graphs Specified by a Regular Language

    by Volker Diekert, Henning Fernau, Petra Wolf

    Traditionally, graph algorithms get a single graph as input, and then they should decide if this graph satisfies a certain property $\Phi$. What happens if this question is modified in a way that we get a possibly infinite family of graphs as an input, and the question is if there is a graph satisfying $\Phi$ in the family? We approach this question by using formal languages for specifying families of graphs, in particular by regular sets of words. We show that certain graph properties can be decided by studying the syntactic monoid of the specification language $L$ if a certain torsion condition is satisfied. This condition holds trivially if $L$ is regular. More specifically, we use a natural binary encoding of finite graphs over a binary alphabet $\Sigma$, and we define a regular set $\mathbb{G}\subseteq \Sigma^*$ such that every nonempty word $w\in \mathbb{G}$ defines a finite and nonempty graph. Also, graph properties can then be syntactically defined as languages over $\Sigma$. Then, we ask whether the automaton $\mathcal{A}$ specifies some graph satisfying a certain property~$\Phi$. Our structural results show that we can answer this question for all "typical" graph properties. In order to show our results, we split $L$ into a finite union of subsets and every subset of this union defines in a natural way a single finite graph $F$ where some edges and vertices are marked. The marked graph in turn defines an infinite graph $F^\infty$ and therefore the family of finite subgraphs of $F^\infty$ where $F$ appears as an induced subgraph. This yields a geometric description of all graphs specified by $L$ based on splitting $L$ into finitely many pieces; then using the notion of graph retraction, we obtain an easily understandable description of the graphs in each piece.