Browsing by Author "Diekert, Volker (Prof. Dr. rer. nat. habil.)"

Now showing 1 - 3 of 3

Open Access
Formal language theory of hairpin formations
(2011) Kopecki, Steffen; Diekert, Volker (Prof. Dr. rer. nat. habil.)
The (bounded) hairpin completion, the hairpin lengthening, and their iterated versions are operations on formal languages which have been inspired by the hairpin formation in DNA biochemistry. In this paper we discuss the hairpin formations from a language theoretic point of view. The hairpin completion of a formal language has been defined in 2006. In the first paper on this topic it has been shown that the hairpin completion of a regular language is not necessarily regular but always linear context-free. In the same paper the open problem was stated, if it is decidable, whether the hairpin completion of a regular language is regular. We solved this problem positively in 2009. Here, we prove that the problem is NL-complete and we present an algorithm whose time complexity is bounded by a polynomial of degree 8. As a by-product of our technique to prove the complexities, we obtain that the hairpin completion of a regular language is actually an unambiguous linear context-free language. In addition, we provide results concerning language classes within the regular languages. We show that if the hairpin completion of an aperiodic (i.e., star-free) language is regular, then the hairpin completion is aperiodic, too. The same is true for the language class induced by the variety LDA. The hairpin lengthening is a variant of the hairpin completion which has been investigated first in 2010. The hairpin lengthening of a regular language seems to behave quite similar to the hairpin completion: It is not necessarily regular but linear context-free. We prove, however, that the hairpin lengthening of a regular language may be an inherent ambiguous linear language. We also consider the problem if it is decidable, whether the hairpin lengthening of a regular language is regular, but we are only able to prove decidability for the one-sided case of hairpin lengthening. (The one-sided case is closer to biochemistry, yet the two-sided case is more interesting from a theoretic point of view). The bounded hairpin completion can be seen as a weaker variant of the hairpin completion. It is well-known that all language classes in the Chomsky hierarchy are closed under bounded hairpin completion and that context-free, context-sensitive, and recursively enumerable languages are closed under iterated bounded hairpin completion. In 2009 it was asked in literature, whether the regular languages are closed under iterated bounded hairpin completion as well. We solve this question by presenting a more general result. We give an effective representation for the iterated bounded hairpin completion which uses union, intersection with regular sets, and concatenation with regular. Thus, all lan- guage classes which are (effectively) closed under these basic operations are also (effectively) closed under iterated bounded hairpin completion. This applies to all classes in the Chomsky hierarchy and to all usual complexity classes. Furthermore, we give an exponential lower and upper bound for the size of non-deterministic finite automata accepting the iterated bounded hairpin completion of a regular language. The iterated (unbounded) hairpin completion of a regular language is known to be context-sensitive and it may be not context-free. However, it is was not known whether the iterated hairpin completion of a singleton (or finite language) is always regular or context-free. This was stated as an open problem in 2008. In contrast to the previous questions this one has a negative answer. We give an example of a singleton whose iterated hairpin completion is not context-free.
Open Access
On the complexity of conjugacy in amalgamated products and HNN extensions
(2015) Weiß, Armin; Diekert, Volker (Prof. Dr. rer. nat. habil.)
This thesis deals with the conjugacy problem in classes of groups which can be written as HNN extension or amalgamated product. The conjugacy problem is one of the fundamental problems in algorithmic group theory which were introduced by Max Dehn in 1911. It poses the question whether two group elements given as words over a fixed set of generators are conjugate. Thus, it is a generalization of the word problem, which asks whether some input word represents the identity. Both, word and conjugacy problem, are undecidable in general. In this thesis, we consider not only decidability, but also complexity of conjugacy. We consider fundamental groups of finite graphs of groups as defined by Serre - a generalization of both HNN extensions and amalgamated products. Another crucial concept for us are strongly generic algorithms - a formalization of algorithms which work for "most" inputs. The following are our main results: The elements of an HNN extension which cannot be conjugated into the base group form a strongly generic set if and only if both inclusions of the associated subgroup into the base group are not surjective. For amalgamated products we prove an analogous result. Following a construction by Stillwell, we derive some undecidability results for the conjugacy problem in HNN extensions with free (abelian) base groups. Next, we show that conjugacy is decidable if all associated subgroups are cyclic or if the base group is abelian and there is only one stable letter. Moreover, in a fundamental group of a graph of groups with free abelian vertex groups, conjugacy is strongly generically in P. Moreover, we consider the case where all edge groups are finite: If conjugacy can be decided in time T(N) in the vertex groups, then it can be decided in time O(log N * T(N)) in the fundamental group under some reasonable assumptions on T (here, N is the length of the input). We also derive some basic transfer results for circuit complexity in the same class of groups. Furthermore, we examine the conjugacy problem of generalized Baumslag-Solitar groups. Our main results are: the conjugacy problem in solvable Baumslag-Solitar groups is TC0-complete, and in arbitrary generalized Baumslag-Solitar groups it can be decided in LOGDCFL. The uniform conjugacy problem for generalized Baumslag-Solitar groups is hard for EXPSPACE. Finally, we deal with the conjugacy problem in the Baumslag group, an HNN extension of the Baumslag-Solitar group BS12. The Baumslag group has a non-elementary Dehn function, and thus, for a long time, it was considered to have a very hard word problem, until Miaskikov, Ushakov, and Won showed that the word problem, indeed, is in P by introducing a new data structure, the so-called power circuits. We follow their approach and show that the conjugacy problem is strongly generically in P. We conjecture that there is no polynomial time algorithm which works for all inputs, because the divisibility problem in power circuits can be reduced to this conjugacy problem. Also, we prove that the comparison problem in power circuits is complete for P under logspace reductions.
Open Access
Solving algorithmic problems in Baumslag-Solitar groups and their extensions using data compression
(2012) Laun, Jürn-Jochen; Diekert, Volker (Prof. Dr. rer. nat. habil.)
This thesis deals with algorithmic group theory and the application of data compression techniques in this area. Elements of the Baumslag-Solitar groups can be represented by comparatively short sequences of generators while their canonical normal forms are exponentially longer. As a consequence, algorithms that solve the word problem by computing such normal forms have to apply compression of the same order to their working data in order to satisfy polynomial time and space contraints. A common way to do this is to write numbers in binary. Going in the opposite direction, the problem of finding a shortest representation of a group element, a so-called geodesic, is also of interest. For example, geodesics can be used to make statements about growth inside groups. In Chapter 2, geodesic normal forms for the Baumslag-Solitar group BS(p,q) are defined and an algorithm is developed that computes them in polynomial time if p divides q. For arbitrary p and q, a partial solution is given which includes the horocyclic subgroup. Experimental results suggest that the horocyclic growth series of BS(2,3) is irrational. In some extensions of the Baumslag-Solitar groups, for example Higman's group and the Baumslag-Gersten group, the discrepancy between the lengths of geodesics and normal forms cannot even be described by an elementary function. This makes conventional approaches to the word problem infeasible. Recently, a data structure has been introduced that makes integers of this magnitude manageable. With the help of these so-called “power circuits”, the word problem for the Baumslag-Gersten group BG(1,2) has been proved to be polynomial-time solvable. In Chapter 3, the crucial reduction procedure for power circuits is improved, thereby decreasing the best known upper time bound for the word problem for BG(1,2) from O(n^7) to O(n^3). At the same time, power circuits are generalized so as to allow bases other than 2. This makes the data structure apt for the generalized Baumslag-Gersten groups BG(1,q) with q>=2. In Chapter 4, power circuits are used to solve the word problem for Higman's group H_4(1,2), an amalgamated product of four copies of BS(1,2). For this group, a time bound of O(n^6) is proved. Again, the generalized notion of power circuit allows an extension of the solution to a larger class of groups H_4(1,q). The algorithm also works for an even more generalized version H_f(1,q) of Higman's group, where an arbitrary number f>=4 of copies of BS(1,q) are amalgamated. The time complexity of the algorithm remains O(n^6) and does not depend on f.