Author name cluster

Pamela Fleischmann

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

TCS Journal 2025 Journal Article

Generalised Nyldon words

Pamela Fleischmann
Annika Huch
Dirk Nowotka

One of the most studied famous classes of words is the class of Lyndon words. Their studies are mainly motivated by the property that they factorise the free monoid as shown in the famous Chen-Fox-Lyndon Theorem. Several generalisations of Lyndon words as anti-Lyndon words, Nyldon words or inverse Lyndon words were made over time. In 2014, Grinberg introduced Nyldon words as a new perspective on the factorisation of the free monoid of words. In particular, for Nyldon words the famous Chen-Fox-Lyndon Theorem is considered w. r. t. a reversed lexicographical order, i. e. , a lexicographically non-decreasing factorisation where each factor is smaller or equal than its successor. Further, a generalised lexicographical order is defined by equipping each position i in a word in Σ ⁎ with a total order ◃ i on Σ. For combining the concept of a generalised order as for generalised Lyndon words and the class of Nyldon words, we investigate a non-decreasing factorisation of the free monoid w. r. t. this generalised ordering and introduce generalised Nyldon words. We show that those words even force a unique non-decreasing factorisation, form a right Hall set, and coincide with the anti-Lyndon words.

Details DOI

I&C Journal 2025 Journal Article

k-Universality of Regular Languages

Duncan Adamson
Pamela Fleischmann
Annika Huch
Tore Koß
Florin Manea
Dirk Nowotka

A subsequence of a word w is a word u such that u = w [ i 1 ] w [ i 2 ] … w [ i k ], for some set of indices 1 ≤ i 1 < i 2 < … < i k ≤ | w |. A word w is k-subsequence universal over an alphabet Σ if every word in Σ k appears in w as a subsequence. In this paper, we study the intersection between the set of k-subsequence universal words over some alphabet Σ and regular languages over Σ. We call a regular language L k-∃-subsequence universal if there exists a k-subsequence universal word in L, and k-∀-subsequence universal if every word of L is k-subsequence universal. We give algorithms solving the problems of deciding if a given regular language, represented by a finite automaton recognising it, is k-∃-subsequence universal and, respectively, if it is k-∀-subsequence universal, for a given k. The algorithms are FPT w. r. t. the size of the input alphabet, and their run-time does not depend on k; they run in polynomial time in the number n of states of the input automaton when the size of the input alphabet is O ( log ⁡ n ). Moreover, we show that the problem of deciding if a given regular language is k-∃-subsequence universal is NP-complete, when the language is over a large alphabet. Further, we provide algorithms for counting the number of k-subsequence universal words (paths) accepted by a given deterministic (respectively, non-deterministic) finite automaton, and ranking an input word (path) within the set of k-subsequence universal words accepted by a given finite automaton.

Details DOI

TCS Journal 2023 Journal Article

Nearly k-universal words – Investigating a part of Simon's congruence

Pamela Fleischmann
Lukas Haschke
Jonas Höfer
Annika Huch
Annika Mayrock
Dirk Nowotka

Determining the index of Simon's congruence is a long outstanding open problem. Two words u and v are called Simon congruent if they have the same set of scattered factors (also known as subwords or subsequences), which are parts of the word in the correct order but not necessarily consecutive, e. g. , oath is a scattered factor of logarithm but tail is not. Following the idea of scattered factor k-universality (also known as k-richness), we investigate m-nearly k-universality, i. e. , words where exactly m scattered factors of length k are absent. We present full characterisations as well as the indexes of the congruence for very small and very large m. Moreover, we give a full combinatorial characterisation of m-nearly k-universal words which are additionally ( k − 1 ) -universal.

Details DOI

TCS Journal 2019 Journal Article

Repetition avoidance in products of factors

Pamela Fleischmann
Pascal Ochem
Kamellia Reshadi

We consider a variation on a classical avoidance problem from combinatorics on words that has been introduced by Mousavi and Shallit at DLT 2013. Let pexp i ( w ) be the supremum of the exponent over the products (concatenation) of i factors of the word w. The repetition threshold Image 1 is then the infimum of pexp i ( w ) over all words w ∈ Σ k ω. Mousavi and Shallit obtained that Image 2 and Image 3. We show that Image 4 if i is even and Image 5 if i is odd and i ⩾ 3.

Details DOI