BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Volker Diekert

Volker Diekert appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.GRFormal Languages and Automata TheoryLogic in Computer ScienceDiscrete MathematicsComputational ComplexityData Structures and AlgorithmsComputer Science and Game Theorymath.COSymbolic Computation

Catalog footprint

What is connected

27works
9topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

27 published item(s)

preprint2022arXiv

Context-Free Groups and Bass-Serre Theory

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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Reachability Games and Parity Games

Parity games are positionally determined. This is a fundamental and classical result. In 2010, Calude et al. showed a breakthrough result for finite parity games: the winning regions and their positional winning strategies can be computed in quasi-polynomial time. In the present paper we give a self-contained and detailed proofs for both results. The results in this paper are not meant to be original. The positional determinacy result is shown for possibly infinite parity games using the ideas of Zielonka which he published in 1998. In order to show quasi-polynomial time, we follow Lehtinen's register games, which she introduced in 2018. Although the time complexity of Lehtinen's algorithm is not optimal, register games are conceptually simple and interesting in their own right. Various of our proofs are either new or simplifications of the original proofs. The topics in this paper include the definition and the computation of optimal attractors for reachability games, too.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Solutions to twisted word equations and equations in virtually free groups

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énizergues (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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Amenability of Schreier graphs and strongly generic algorithms for the conjugacy problem

In various occasions the conjugacy problem in finitely generated amalgamated products and HNN extensions can be decided efficiently for elements which cannot be conjugated into the base groups. This observation asks for a bound on how many such elements there are. Such bounds can be derived using the theory of amenable graphs: In this work we examine Schreier graphs of amalgamated products and HNN extensions. For an amalgamated product $G = H *_A K $ with $[H:A] \geq [K:A] \geq 2$, the Schreier graph with respect to $H$ or $K$ turns out to be non-amenable if and only if $[H:A] \geq 3$. Moreover, for an HNN extension of the form $G = <H,b | bab^{-1}=ϕ(a), a \in A >$, we show that the Schreier graph of $G$ with respect to the subgroup $H$ is non-amenable if and only if $A \neq H \neq ϕ(A)$. As application of these characterizations we show that under certain conditions the conjugacy problem in fundamental groups of finite graphs of groups with free abelian vertex groups can be solved in polynomial time on a strongly generic set. Furthermore, the conjugacy problem in groups with more than one end can be solved with a strongly generic algorithm which has essentially the same time complexity as the word problem. These are rather striking results as the word problem might be easy, but the conjugacy problem might be even undecidable. Finally, our results yield another proof that the set where the conjugacy problem of the Baumslag group is decidable in polynomial time is also strongly generic.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Characterizing classes of regular languages using prefix codes of bounded synchronization delay

In this paper we continue a classical work of Schützenberger on codes with bounded synchronization delay. He was interested to characterize 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^\infty)$ and $SD_H(A^\infty$). Our main result shows that $SD_H(A^\infty)$ 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 products 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 products. 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 products.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Solution sets for equations over free groups are EDT0L languages

We show that, given an equation over a finitely generated free group, the set of all solutions in reduced words forms an effectively constructible EDT0L language. In particular, the set of all solutions in reduced words is an indexed language in the sense of Aho. The language characterization we give, as well as further questions about the existence or finiteness of solutions, follow from our explicit construction of a finite directed graph which encodes all the solutions. Our result incorporates the recently invented recompression technique of Jeż, and a new way to integrate solutions of linear Diophantine equations into the process. As a byproduct of our techniques, we improve the complexity from quadratic nondeterministic space in previous works to $\mathsf{NSPACE}(n\log n)$ here.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Note on Monitors and Büchi automata

When a property needs to be checked against an unknown or very complex system, classical exploration techniques like model-checking are not applicable anymore. Sometimes a~monitor can be used, that checks a given property on the underlying system at runtime. A monitor for a property $L$ is a deterministic finite automaton $M_L$ that after each finite execution tells whether (1) every possible extension of the execution is in $L$, or (2) every possible extension is in the complement of $L$, or neither (1) nor (2) holds. Moreover, $L$ being monitorable means that it is always possible that in some future the monitor reaches (1) or (2). Classical examples for monitorable properties are safety and cosafety properties. On the other hand, deterministic liveness properties like "infinitely many $a$'s" are not monitorable. We discuss various monitor constructions with a focus on deterministic omega-regular languages. We locate a proper subclass of of deterministic omega-regular languages but also strictly large than the subclass of languages which are deterministic and codeterministic, and for this subclass there exists a canonical monitor which also accepts the language itself. We also address the problem to decide monitorability in comparison with deciding liveness. The state of the art is as follows. Given a Büchi automaton, it is PSPACE-complete to decide liveness or monitorability. Given an LTL formula, deciding liveness becomes EXPSPACE-complete, but the complexity to decide monitorability remains open.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Equations over free inverse monoids with idempotent variables

We introduce the notion of idempotent variables for studying equations in inverse monoids. It is proved that it is decidable in singly exponential time (DEXPTIME) whether a system of equations in idempotent variables over a free inverse monoid has a solution. The result is proved by a direct reduction to solve language equations with one-sided concatenation and a known complexity result by Baader and Narendran: Unification of concept terms in description logics, 2001. We also show that the problem becomes DEXPTIME hard , as soon as the quotient group of the free inverse monoid has rank at least two. Decidability for systems of typed equations over a free inverse monoid with one irreducible variable and at least one unbalanced equation is proved with the same complexity for the upper bound. Our results improve known complexity bounds by Deis, Meakin, and Senizergues: Equations in free inverse monoids, 2007. Our results also apply to larger families of equations where no decidability has been previously known.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

More Than 1700 Years of Word Equations

Geometry and Diophantine equations have been ever-present in mathematics. Diophantus of Alexandria was born in the 3rd century (as far as we know), but a systematic mathematical study of word equations began only in the 20th century. So, the title of the present article does not seem to be justified at all. However, a linear Diophantine equation can be viewed as a special case of a system of word equations over a unary alphabet, and, more importantly, a word equation can be viewed as a special case of a Diophantine equation. Hence, the problem WordEquations: "Is a given word equation solvable?" is intimately related to Hilbert's 10th problem on the solvability of Diophantine equations. This became clear to the Russian school of mathematics at the latest in the mid 1960s, after which a systematic study of that relation began. Here, we review some recent developments which led to an amazingly simple decision procedure for WordEquations, and to the description of the set of all solutions as an EDT0L language.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Solution sets for equations over free groups are EDT0L languages -- ICALP 2015 version

We show that, given a word equation over a finitely generated free group, the set of all solutions in reduced words forms an EDT0L language. In particular, it is an indexed language in the sense of Aho. The question of whether a description of solution sets in reduced words as an indexed language is possible has been been open for some years, apparently without much hope that a positive answer could hold. Nevertheless, our answer goes far beyond: they are EDT0L, which is a proper subclass of indexed languages. We can additionally handle the existential theory of equations with rational constraints in free products $\star_{1 \leq i \leq s}F_i$, where each $F_i$ is either a free or finite group, or a free monoid with involution. In all cases the result is the same: the set of all solutions in reduced words is EDT0L. This was known only for quadratic word equations by Ferté, Marin and Sénizergues (ToCS 2014), which is a very restricted case. Our general result became possible due to the recent recompression technique of Jeż. In this paper we use a new method to integrate solutions of linear Diophantine equations into the process and obtain more general results than in the related paper (arXiv 1405.5133). For example, we improve the complexity from quadratic nondeterministic space in (arXiv 1405.5133) to quasi-linear nondeterministic space here. This implies an improved complexity for deciding the existential theory of non-abelian free groups: NSPACE($n\log n$). The conjectured complexity is NP, however, we believe that our results are optimal with respect to space complexity, independent of the conjectured NP.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Finding All Solutions of Equations in Free Groups and Monoids with Involution

The aim of this paper is to present a PSPACE algorithm which yields a finite graph of exponential size and which describes the set of all solutions of equations in free groups as well as the set of all solutions of equations in free monoids with involution in the presence of rational constraints. This became possible due to the recently invented emph{recompression} technique of the second author. He successfully applied the recompression technique for pure word equations without involution or rational constraints. In particular, his method could not be used as a black box for free groups (even without rational constraints). Actually, the presence of an involution (inverse elements) and rational constraints complicates the situation and some additional analysis is necessary. Still, the recompression technique is general enough to accommodate both extensions. In the end, it simplifies proofs that solving word equations is in PSPACE (Plandowski 1999) and the corresponding result for equations in free groups with rational constraints (Diekert, Hagenah and Gutierrez 2001). As a byproduct we obtain a direct proof that it is decidable in PSPACE whether or not the solution set is finite.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Logspace computations in graph products

We consider three important and well-studied algorithmic problems in group theory: the word, geodesic, and conjugacy problem. We show transfer results from individual groups to graph products. We concentrate on logspace complexity because the challenge is actually in small complexity classes, only. The most difficult transfer result is for the conjugacy problem. We have a general result for graph products, but even in the special case of a graph group the result is new. Graph groups are closely linked to the theory of Mazurkiewicz traces which form an algebraic model for concurrent processes. Our proofs are combinatorial and based on well-known concepts in trace theory. We also use rewriting techniques over traces. For the group-theoretical part we apply Bass-Serre theory. But as we need explicit formulae and as we design concrete algorithms all our group-theoretical calculations are completely explicit and accessible to non-specialists.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Conjugacy in Baumslag's group, generic case complexity, and division in power circuits

The conjugacy problem belongs to algorithmic group theory. It is the following question: given two words x, y over generators of a fixed group G, decide whether x and y are conjugated, i.e., whether there exists some z such that zxz^{-1} = y in G. The conjugacy problem is more difficult than the word problem, in general. We investigate the complexity of the conjugacy problem for two prominent groups: the Baumslag-Solitar group BS(1,2) and the Baumslag(-Gersten) group G(1,2). The conjugacy problem in BS(1,2) is TC^0-complete. To the best of our knowledge BS(1,2) is the first natural infinite non-commutative group where such a precise and low complexity is shown. The Baumslag group G(1,2) is an HNN-extension of BS(1,2). We show that the conjugacy problem is decidable (which has been known before); but our results go far beyond decidability. In particular, we are able to show that conjugacy in G(1,2) can be solved in polynomial time in a strongly generic setting. This means that essentially for all inputs conjugacy in G(1,2) can be decided efficiently. In contrast, we show that under a plausible assumption the average case complexity of the same problem is non-elementary. Moreover, we provide a lower bound for the conjugacy problem in G(1,2) by reducing the division problem in power circuits to the conjugacy problem in G(1,2). The complexity of the division problem in power circuits is an open and interesting problem in integer arithmetic.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

QuickHeapsort: Modifications and improved analysis

We present a new analysis for QuickHeapsort splitting it into the analysis of the partition-phases and the analysis of the heap-phases. This enables us to consider samples of non-constant size for the pivot selection and leads to better theoretical bounds for the algorithm. Furthermore we introduce some modifications of QuickHeapsort, both in-place and using n extra bits. We show that on every input the expected number of comparisons is n lg n - 0.03n + o(n) (in-place) respectively n lg n -0.997 n+ o (n). Both estimates improve the previously known best results. (It is conjectured in Wegener93 that the in-place algorithm Bottom-Up-Heapsort uses at most n lg n + 0.4 n on average and for Weak-Heapsort which uses n extra-bits the average number of comparisons is at most n lg n -0.42n in EdelkampS02.) Moreover, our non-in-place variant can even compete with index based Heapsort variants (e.g. Rank-Heapsort in WangW07) and Relaxed-Weak-Heapsort (n lg n -0.9 n+ o (n) comparisons in the worst case) for which no O(n)-bound on the number of extra bits is known.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

SLP compression for solutions of equations with constraints in free and hyperbolic groups

The paper is a part of an ongoing program which aims to show that the existential theory in free groups (hyperbolic groups or even toral relatively hyperbolic) is NP-complete. For that we study compression of solutions with straight-line programs (SLPs) as suggested originally by Plandowski and Rytter in the context of a single word equation. We review some basic results on SLPs and give full proofs in order to keep this fundamental part of the program self-contained. Next we study systems of equations with constraints in free groups and more generally in free products of abelian groups. We show how to compress minimal solutions with extended Parikh-constraints. This type of constraints allows to express semi linear conditions as e.g. alphabetic information. The result relies on some combinatorial analysis and has not been shown elsewhere. We show similar compression results for Boolean formula of equations over a torsion-free $δ$-hyperbolic group. The situation is much more delicate than in free groups. As byproduct we improve the estimation of the "capacity" constant used by Rips and Sela in their paper "Canonical representatives and equations in hyperbolic groups" from a double-exponential bound in $δ$ to some single-exponential bound. The final section shows compression results for toral relatively hyperbolic group using the work of Dahmani: We show that given a system of equations over a fixed toral relatively hyperbolic group, for every solution of length $N$ there is an SLP for another solution such that the size of the SLP is bounded by some polynomial $p(s+ \log N)$ where $s$ is the size of the system.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Context-Free Groups and Their Structure Trees

Let Gamma be a connected, locally finite graph of finite tree width and G be a group acting on it with finitely many orbits and finite node stabilizers. We provide an elementary and direct construction of a tree T on which G acts with finitely many orbits and finite vertex stabilizers. Moreover, the tree is defined directly in terms of the structure tree of optimally nested cuts of Gamma. Once the tree is constructed, standard Bass-Serre theory yields that G is virtually free. This approach simplifies the existing proofs for the fundamental result of Muller and Schupp that characterizes context-free groups as f.g. virtually free groups. Our construction avoids the explicit use of Stallings' structure theorem and it is self-contained. We also give a simplified proof for an important consequence of the structure tree theory by Dicks and Dunwoody which has been stated by Thomassen and Woess. It says that a f.g. group is accessible if and only if its Cayley graph is accessible.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Cyclic rewriting and conjugacy problems

Cyclic words are equivalence classes of cyclic permutations of ordinary words. When a group is given by a rewriting relation, a rewriting system on cyclic words is induced, which is used to construct algorithms to find minimal length elements of conjugacy classes in the group. These techniques are applied to the universal groups of Stallings pregroups and in particular to free products with amalgamation, HNN-extensions and virtually free groups, to yield simple and intuitive algorithms and proofs of conjugacy criteria.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Logspace Computations in Coxeter Groups and Graph Groups

Computing normal forms in groups (or monoids) is in general harder than solving the word problem (equality testing). However, normal form computation has a much wider range of applications. It is therefore interesting to investigate the complexity of computing normal forms for important classes of groups. For Coxeter groups we show that the following algorithmic tasks can be solved by a deterministic Turing machine using logarithmic work space, only: 1. Compute the length of any geodesic normal form. 2. Compute the set of letters occurring in any geodesic normal form. 3. Compute the Parikh-image of any geodesic normal form in case that all defining relations have even length (i.e., in even Coxeter groups.) 4. For right-angled Coxeter groups we can do actually compute the short length normal form in logspace. (Note that short length normal forms are geodesic.) Next, we apply the results to right-angled Artin groups. They are also known as free partially commutative groups or as graph groups. As a consequence of our result on right-angled Coxeter groups we show that shortlex normal forms in graph groups can be computed in logspace, too. Graph groups play an important role in group theory, and they have a close connection to concurrency theory. As an application of our results we show that the word problem for free partially commutative inverse monoids is in logspace. This result generalizes a result of Ondrusch and the third author on free inverse monoids. Concurrent systems which are deterministic and co-deterministic can be studied via inverse monoids.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On distributed monitoring of asynchronous systems

Distributed systems are notoriously difficult to understand and analyze in order to assert their correction w.r.t. given properties. They often exhibit a huge number of different behaviors, as soon as the active entities (peers, agents, processes, etc) behave in an asynchronous manner. Already the modelization of such systems is a non-trivial task, let alone their formal verification. The purpose of this paper is to discuss the problem of distributed monitoring on a simple model of finite-state distributed automata based on shared actions, called asynchronous automata. Monitoring is a question related to runtime verification: assume that we have to check a property $L$ against an unknown or very complex system $A$, so that classical static analysis is not possible. Therefore instead of model-checking a monitor is used, that checks the property on the underlying system at runtime. We are interested here in monitoring distributed systems modeled as asynchronous automata. It is natural to require that monitors should be of the same kind as the underlying system, so we consider here distributed monitoring. A distributed monitor does not have a global view of the system, therefore we propose the notion of locally monitorable trace language. Our main result shows that if the distributed alphabet of actions is connected and if $L$ is a set of infinite traces such that both $L$ and its complement $L^c$ are countable unions of locally safety languages, then $L$ is locally monitorable. We also show that over infinite traces, recognizable countable unions of locally safety languages are precisely the complements of deterministic languages.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Regular Languages are Church-Rosser Congruential

This paper proves a long standing conjecture in formal language theory. It shows that all regular languages are Church-Rosser congruential. The class of Church-Rosser congruential languages was introduced by McNaughton, Narendran, and Otto in 1988. A language L is Church-Rosser congruential, if there exists a finite confluent, and length-reducing semi-Thue system S such that L is a finite union of congruence classes modulo S. It was known that there are deterministic linear context-free languages which are not Church-Rosser congruential, but on the other hand it was strongly believed that all regular language are of this form. Actually, this paper proves a more general result.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Deciding Regularity of Hairpin Completions of Regular Languages in Polynomial Time

The hairpin completion is an operation on formal languages that has been inspired by the hairpin formation in DNA biochemistry and by DNA computing. In this paper we investigate the hairpin completion of regular languages. It is well known that hairpin completions of regular languages are linear context-free and not necessarily regular. As regularity of a (linear) context-free language is not decidable, the question arose whether regularity of a hairpin completion of regular languages is decidable. We prove that this problem is decidable and we provide a polynomial time algorithm. Furthermore, we prove that the hairpin completion of regular languages is an unambiguous linear context-free language and, as such, it has an effectively computable growth function. Moreover, we show that the growth of the hairpin completion is exponential if and only if the growth of the underlying languages is exponential and, in case the hairpin completion is regular, then the hairpin completion and the underlying languages have the same growth indicator.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Efficient algorithms for highly compressed data: The Word Problem in Higman's group is in P

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 has been non-elementary. In the present paper we provide new results for power circuits and we give new applications in algorithmic algebra and 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. The improvement is crucial for our other results. 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. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Group extensions over infinite words

We construct an extension $E(A,G)$ of a given group $G$ by infinite non-Archimedean words over an discretely ordered abelian group like $Z^n$. This yields an effective and uniform method to study various groups that "behave like $G$". We show that the Word Problem for f.g. subgroups in the extension is decidable if and only if and only if the Cyclic Membership Problem in $G$ is decidable. The present paper embeds the partial monoid of infinite words as defined by Myasnikov, Remeslennikov, and Serbin (Contemp. Math., Amer. Math. Soc., 378:37-77, 2005) into $E(A,G)$. Moreover, we define the extension group $E(A,G)$ for arbitrary groups $G$ and not only for free groups as done in previous work. We show some structural results about the group (existence and type of torsion elements, generation by elements of order 2) and we show that some interesting HNN extensions of $G$ embed naturally in the larger group $E(A,G)$.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

It Is NL-complete to Decide Whether a Hairpin Completion of Regular Languages Is Regular

The hairpin completion is an operation on formal languages which is inspired by the hairpin formation in biochemistry. Hairpin formations occur naturally within DNA-computing. It has been known that the hairpin completion of a regular language is linear context-free, but not regular, in general. However, for some time it is was open whether the regularity of the hairpin completion of a regular language is is decidable. In 2009 this decidability problem has been solved positively by providing a polynomial time algorithm. In this paper we improve the complexity bound by showing that the decision problem is actually NL-complete. This complexity bound holds for both, the one-sided and the two-sided hairpin completions.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Star-Free Languages are Church-Rosser Congruential

The class of Church-Rosser congruential languages has been introduced by McNaughton, Narendran, and Otto in 1988. A language L is Church-Rosser congruential (belongs to CRCL), if there is a finite, confluent, and length-reducing semi-Thue system S such that L is a finite union of congruence classes modulo S. To date, it is still open whether every regular language is in CRCL. In this paper, we show that every star-free language is in CRCL. In fact, we prove a stronger statement: For every star-free language L there exists a finite, confluent, and subword-reducing semi-Thue system S such that the total number of congruence classes modulo S is finite and such that L is a union of congruence classes modulo S. The construction turns out to be effective.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Geodesic rewriting systems and pregroups

In this paper we study rewriting systems for groups and monoids, focusing on situations where finite convergent systems may be difficult to find or do not exist. We consider systems which have no length increasing rules and are confluent and then systems in which the length reducing rules lead to geodesics. Combining these properties we arrive at our main object of study which we call geodesically perfect rewriting systems. We show that these are well-behaved and convenient to use, and give several examples of classes of groups for which they can be constructed from natural presentations. We describe a Knuth-Bendix completion process to construct such systems, show how they may be found with the help of Stallings' pregroups and conversely may be used to construct such pregroups.

0 citations0 reviewsNo code linkedOpen access