10 papers
Twisted Equations and Palindrome Length
Volker Diekert, Anna E. Frid, Silas Natterer +1
Twisted equations in free groups are equations in which a finite group of symmetries acts on the free group by automorphisms and anti-automorphisms, such as inversion and reversal;…
Word Length and Diameter in Permutation Groups
Markus Lohrey, Alexander Thumm
The input for the binary diameter problem consists of explicitly represented permutations generating a finite group and a binary-encoded nonnegative integer . The question i…
Quadratic Equations in Graph Products of Groups and the Exponent of Periodicity
Volker Diekert, Silas Natterer, Alexander Thumm
In 1977, Makanin established the decidability of equations in free monoids. A key ingredient in his proof is the exponent of periodicity: for a word , it is the largest exponent…
Efficient Compression in Semigroups
Florian Stober, Alexander Thumm, Armin Weiß
Straight-line programs are a central tool in several areas of computer science, including data compression, algebraic complexity theory, and the algorithmic solution of algebraic e…
Quadratic word equations with regular constraints and the exponent of periodicity
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 l…
Finite Semigroups Satisfying an Identity
Alexander Thumm
We determine the maximal pseudovarieties of finite semigroups that satisfy an identity of the form . Applying this classification, we furt…
Membership and Conjugacy in Inverse Semigroups
Lukas Fleischer, Florian Stober, Alexander Thumm +1
The membership problem for an algebraic structure asks whether a given element is contained in some substructure, which is usually given by generators. In this work we study the me…
Finite groups with geodetic Cayley graphs
Murray Elder, Adam Piggott, Florian Stober +2
A connected undirected graph is called \emph{geodetic} if for every pair of vertices there is a unique shortest path connecting them. It has been conjectured that for finite groups…
Streaming algorithms for groups and semigroups
Markus Lohrey, Lukas Lück, Alexander Thumm +1
We investigate deterministic and randomized streaming algorithms for word problems in finitely generated groups and semigroups. For this we introduce the notion of a distinguisher:…
The Ordered Join of Impartial Games
Mišo Gavrilović, Alexander Thumm
Inspired by the theory of poset games, we introduce a new compound of impartial combinatorial games and provide a complete analysis in the spirit of the Sprague-Grundy theory. Furt…