2 citations · 2 across the 3 of their papers we have counts for
10 papers · 1 filter
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…
Efficient Membership Testing for Pseudovarieties of Finite Semigroups
Lukas Fleischer
We consider the complexity of deciding membership of a given finite semigroup to a fixed pseudovariety. While it is known that there exist pseudovarieties with NP-complete or even…
The Intersection Problem for Finite Semigroups
Lukas Fleischer
We investigate the intersection problem for finite semigroups, which asks for a given set of regular languages, represented by recognizing morphisms to finite semigroups, whether t…