3 citations · 8 across the 9 of their papers we have counts for
15 papers
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…
The State Complexity of Lexicographically Smallest Words and Computing Successors
Lukas Fleischer, Jeffrey Shallit
Given a regular language L over an ordered alphabet , the set of lexicographically smallest (resp., largest) words of each length is itself regular. Moreover, there exists an un…
Words Avoiding Reversed Factors, Revisited
Lukas Fleischer, Jeffrey Shallit
In 2005, Rampersad and the second author proved a number of theorems about infinite words x with the property that if w is any sufficiently long finite factor of x, then its revers…
New Bounds on Antipowers in Words
Lukas Fleischer, Samin Riasat, Jeffrey Shallit
Fici et al. defined a word to be a k-power if it is the concatenation of k consecutive identical blocks, and an r-antipower if it is the concatenation of r pairwise distinct blocks…
Words With Few Palindromes, Revisited
Lukas Fleischer, Jeffrey Shallit
In 2013, Fici and Zamboni proved a number of theorems about finite and infinite words having only a small number of factors that are palindromes. In this paper we rederive some of…
On the Complexity of Properties of Transformation Semigroups
Lukas Fleischer, Trevor Jack
We investigate the computational complexity for determining various properties of a finite transformation semigroup given by generators. We introduce a simple framework to describe…