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 membership problem, as well as the conjugacy problem, for finite inverse semigroups. The closely related membership problem for finite semigroups has been shown to be PSPACE-complete in the transformation model by Kozen (1977) and NL-complete in the Cayley table model by Jones, Lien, and Laaser (1976). More recently, both the membership and the conjugacy problem for finite inverse semigroups were shown to be PSPACE-complete in the partial bijection model by Jack (2023). Here we present a more detailed analysis of the complexity of the membership and conjugacy problems parametrized by varieties of finite inverse semigroups. We establish dichotomy theorems for the partial bijection model and for the Cayley table model. In the partial bijection model these problems are in NC (resp. NP for conjugacy) for strict inverse semigroups and PSPACE-complete otherwise. In the Cayley table model we obtain general 𝖫-algorithms as well as NPOLYLOGTIME upper bounds for Clifford semigroups and 𝖫-completeness otherwise. Furthermore, by applying our findings, we show the following: the intersection non-emptiness problem for inverse automata is PSPACE-complete even for automata with only two states; the subpower membership problem is in NC for every strict inverse semigroup and PSPACE-complete otherwise; the minimum generating set and the equation satisfiability problems are in NP for varieties of finite strict inverse semigroups and PSPACE-complete otherwise.

We characterize those strings whose suffix arrays are based on arithmetic progressions, in particular, arithmetically progressed permutations where all pairs of successive entries of the permutation have the same difference modulo the respective string length. We show that an arithmetically progressed permutation P coincides with the suffix array of a unary, binary, or ternary string. We further analyze the conditions of a given P under which we can find a uniquely defined string over either a binary or ternary alphabet having P as its suffix array. For the binary case, we show its connection to lower Christoffel words, balanced words, and Fibonacci words. In addition to solving the arithmetically progressed suffix array problem, we give the shape of the Burrows–Wheeler transform of those strings solving this problem. These results give rise to numerous future research directions.

Abstract The power word problem for a group $$\varvec{G}$$ G asks whether an expression $$\varvec{u_1^{x_1} \cdots u_n^{x_n}}$$ u 1 x 1 ⋯ u n x n , where the $$\varvec{u_i}$$ u i are words over a finite set of generators of $$\varvec{G}$$ G and the $$\varvec{x_i}$$ x i binary encoded integers, is equal to the identity of $$\varvec{G}$$ G . It is a restriction of the compressed word problem, where the input word is represented by a straight-line program (i.e., an algebraic circuit over $$\varvec{G}$$ G ). We start by showing some easy results concerning the power word problem. In particular, the power word problem for a group $$\varvec{G}$$ G is $$\varvec{\textsf{uNC}^{1}}$$ uNC 1 -many-one reducible to the power word problem for a finite-index subgroup of $$\varvec{G}$$ G . For our main result, we consider graph products of groups that do not have elements of order two. We show that the power word problem in a fixed such graph product is $$\varvec{\textsf{AC} ^0}$$ AC 0 -Turing-reducible to the word problem for the free group $$\varvec{F_2}$$ F 2 and the power word problems of the base groups. Furthermore, we look into the uniform power word problem in a graph product, where the dependence graph and the base groups are part of the input. Given a class of finitely generated groups $$\varvec{\mathcal {C}}$$ C without order two elements, the uniform power word problem in a graph product can be solved in $$\varvec{\textsf{AC} ^0[\textsf{C}_=\textsf{L} ^{{{\,\textrm{UPowWP}\,}}(\mathcal {C})}]}$$ AC 0 [ C = L UPowWP ( C ) ] , where $$\varvec{{{\,\textrm{UPowWP}\,}}(\mathcal {C})}$$ UPowWP ( C ) denotes the uniform power word problem for groups from the class $$\varvec{\mathcal {C}}$$ C . As a consequence of our results, the uniform knapsack problem in right-angled Artin groups is $$\varvec{\textsf{NP}}$$ NP -complete. The present paper is a combination of the two conference papers (Lohrey and Weiß 2019b, Stober and Weiß 2022a). In Stober and Weiß (2022a) our results on graph products were wrongly stated without the additional assumption that the base groups do not have elements of order two. In the present work we correct this mistake. While we strongly conjecture that the result as stated in Stober and Weiß (2022a) is true, our proof relies on this additional assumption.

It is a long-standing open question to determine the minimum number of comparisons S (n) that suffice to sort an array of n elements. Indeed, before this work, S(n) has been known only for n ≤ 22 with the exception of n = 16, 17, and 18.

Abstract MergeInsertion, also known as the Ford-Johnson algorithm, is a sorting algorithm which, up to today, for many input sizes achieves the best known upper bound on the number of comparisons. Indeed, it gets extremely close to the information-theoretic lower bound. While the worst-case behavior is well understood, only little is known about the average case. This work takes a closer look at the average case behavior. In particular, we establish an upper bound of $n \log n - 1.4005n + o(n)$ n log n − 1.4005 n + o ( n ) comparisons. We also give an exact description of the probability distribution of the length of the chain a given element is inserted into and use it to approximate the average number of comparisons numerically. Moreover, we compute the exact average number of comparisons for n up to 148. Furthermore, we experimentally explore the impact of different decision trees for binary insertion. To conclude, we conduct experiments showing that a slightly different insertion order leads to a better average case and we compare the algorithm to Manacher’s combination of merging and MergeInsertion as well as to the recent combined algorithm with (1,2)-Insertionsort by Iwama and Teruyama.