Jumbled Scattered Factors

Annika Huch; Melf Kammholz; Pamela Fleischmann; Tore Ko{\ss}

REVIEW 5 major objections 5 minor 51 references

Jumbled Scattered Factors

T0 review · 5 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper introduces a jumble index for words and proves that it equals the length of the word minus the length of their longest common scattered factor, then uses this to classify jumbled Simon congruence classes and bound the jumbles…

desk verdict A promising but rough paper: the central identity is right with the right qualifier, but Lemma 11 is actually false as stated and needs a size restriction. read the letter →

arxiv 2506.03814 v1 pith:SC5OLYAB submitted 2025-06-04 math.CO cs.FL

Pamela Fleischmann , Annika Huch , Melf Kammholz , Tore Ko{ss} This is my paper

classification math.COcs.FL MSC 68R15

keywords jumbledscatteredfactorssubsequencesParikhvectorsjumbleindexSimon'scongruencek-universalityarchfactorization

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper introduces jumbled scattered factors: a word u is a jumbled scattered factor of w if u's letters can be matched against w's letters without regard to order, as long as no letter is used more often than it appears in w. To quantify how scrambled the match is, the authors define the jumble index δ_w(u) as the fewest letters of u that must be out of place, i.e. not part of a common scattered factor with w. The central structural result is that δ_w(u) = |u| − lcsf(u,w), so the new measure is exactly the classical deletion distance between u and w measured by their longest common scattered factor. On this basis the paper also studies a jumbled version of Simon's congruence and a jumbled version of k-universality, showing that at most k − ι(w) jumbles are needed to make any word jumbled k-universal.

What carries the argument

Three pieces carry the argument. First, Parikh vectors encode a word by the number of occurrences of each letter, making jumbled membership a componentwise inequality of letter counts. Second, the jumble index δ_w(u) is defined as the minimal ℓ such that some |u|−ℓ letters of u occur in order inside w, and Lemma 9(3) ties it exactly to the longest common scattered factor lcsf(u,w). Third, the arch factorization of a word, which splits it into minimal blocks each containing the full alphabet, is used to analyse universality and to prove the one-jumble extension step for words with surplus letter counts.

What would settle it

Find a k-universal word w with at least k+1 occurrences of every letter and a letter x outside the alphabet of the remainder r(w), such that for some length-k scattered factor s of w the jumble index δ_w(sx) equals 2 rather than 1; such a word would disprove Lemma 34 and the one-jumble universality result.

Watch

Extended reading notes

Core claim

For any word w and any jumbled scattered factor u of w, the jumble index equals |u| minus the length of a longest common scattered factor of u and w: δ_w(u) = |u| − lcsf(u,w). This identity converts the new combinatorial measure into the classical subsequence distance, so the minimal number of jumbles is governed by the same quantity as longest common subsequence length. The paper further claims that the jumbled Simon relation has finite index and that its equivalence classes have sizes 1, the number of permutations of the word, or infinity. For jumbled universality, it proves that for every word w and every k no larger than the minimum letter count, at most k − ι(w) jumbles suffice to cover all length-k words, and that under the extra condition that every letter occurs at least k+1 times, a single jumble is enough to step from k-universality up to (k+1)-universality in the jumbled sense.

Load-bearing premise

The load-bearing step is the asserted but not fully proved claim that, for a k-universal word with more than k copies of every letter, appending any letter missing from the remainder alphabet to any length-k scattered factor always costs exactly one jumble.

Editorial extensions

If this is right

Jumble-index computation reduces to longest common subsequence computation, so existing algorithms for longest common subsequences apply directly.
The jumbled Simon relation is an equivalence relation of finite index, and each equivalence class has size 1, the number of permutations of the word, or infinity.
For any word w and any k no larger than the smallest letter count, at most k − ι(w) jumbles suffice to cover every length-k word in the jumbled scattered factor set.
When every letter occurs at least k+1 times in a k-universal word, one jumble is enough to reach jumbled (k+1)-universality.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The identity δ_w(u) = |u| − lcsf(u,w) suggests treating the jumble index as a deletion-only edit distance; one could test whether the jumble-index partition of all jumbled scattered factors coincides exactly with longest-common-scattered-factor length differences.
Because the jumbled scattered-factor relation is a preorder whose antichains are finite, algorithmic results on scattered-factor universality may carry over to the jumbled setting, for instance computing the minimal jumbles for a target k by arch-like factorisations.
The one-jumble step hints that for words with all letter counts at least k+1, the bound k − ι(w) may be far from tight; random experiments on words with skewed Parikh vectors could locate where the bound is actually achieved.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Quick take: the paper introduces a genuinely new angle on scattered factors by adding an abelian jumbling parameter, and the central measure δ_w(u) is exactly |u| minus LCSF for words whose Parikh vector fits inside w. The novelty is modest—the core index is a repackaging of longest common subsequence—but the Simon-equivalence trichotomy and the universality bounds are real additions.

The good: Section 4's trichotomy and Proposition 32's bound are worth a look. Lemma 9(3) is the load-bearing identity, and it is correct in the intended domain: for u∈JScatFact(w), the minimal number of jumbles is |u|−lcsf(u,w). Most proofs are short and credible, and the examples actually clarify the definition.

Soft spots: first, Lemma 9(3) as printed omits the qualifier p(u)≤p(w). Without it the 'if' direction fails—take u=bb, w=ab; lcsf is 1 so ℓ=1, but u is not a jumbled scattered factor. All downstream uses appear to stay in the intended domain, so this is a fixable formal error. Second, Lemma 11 is not merely missing justification; it is false as stated. The proof extends a length-k′ counterexample to length k by inserting letters, but no such extension exists when the word is shorter than k. With u=a, v=aa, k=3, ℓ=1, the length-3 jumbled factor sets are both empty while the ≤3 sets differ. The authors likely intend a restriction like |u|,|v|≥k, and with that restriction the proof might be repairable, but it also needs to show the jumble bound survives the extension. Third, Lemma 34 is terse—the arch argument works, but a sentence explaining why the prefix can be embedded in the arches would help.

Bottom line: the framework is plausible and the flawed statements are localized. The central identity holds up, and the new results in Sections 4 and 5 deserve scrutiny. This is for people working on combinatorics on words, Simon congruence, and string universality. It deserves a serious referee, not a desk reject, but the authors need to add the missing hypothesis and fix Lemma 11.

Referee Report

5 major / 5 minor

Summary. This paper introduces jumbled scattered factors, words whose Parikh vector is componentwise bounded by that of a given word w, together with a 'number of jumbles' ℓ measuring how far such a factor is from being an ordinary scattered factor. The main results are an identity relating the jumble index δ_w(u) to the length of a longest common scattered factor, a study of a jumbled analogue of Simon's congruence with finiteness and cardinality results, and results on jumbled k-universality, including a bound of k−ι(w) on the number of jumbles needed and a 'one jumble is enough' statement under surplus-letter conditions. The paper is purely combinatorial and does not provide algorithms or machine-checked proofs.

Significance. The central observation, that the jumble index equals |u|−lcsf(u,w) for u in JScatFact(w), is elegant and connects a new notion directly to a classical measure; if the surrounding proofs are completed, the paper opens a coherent research direction at the intersection of abelian equivalence and subsequence theory. The universality results using arch factorizations are also promising and provide falsifiable statements (e.g., the characterization in Lemma 34) that can be tested on examples. However, the current version contains a formally false lemma and several substantial proof gaps, so the significance will be realized only after a careful revision.

major comments (5)

[Lemma 9(3)] Lemma 9(3) is formally false as stated. Over Σ={a,b}, take u=bb and w=ab. Then lcsf(u,w)=1, so the right-hand side gives ℓ=1, but p(u)=(0,2) is not componentwise ≤ p(w)=(1,1), so u is not in JScatFact(w,ℓ) for any ℓ and δ_w(u) is undefined. The proof of part (1) explicitly uses the hypothesis p(u)≤p(w), and Definition 5 restricts jumbled scattered factors to such words. The statement should read: for u∈JScatFact(w), u∈JScatFact(w,ℓ) iff ℓ=|u|−lcsf(u,w), hence δ_w(u)=|u|−lcsf(u,w). All later applications appear to stay in this intended domain, but the lemma as printed is incorrect and should be corrected.
[Lemma 11] Lemma 11 is false as stated. Let Σ={a,b}, u=aa, v=ab, k=3, ℓ=1. Then JScatFact_3(u,1)=JScatFact_3(v,1)=∅ because no word of length 3 has Parikh vector ≤ (2,0) or ≤ (1,1). However, JScatFact_2(u,1)={aa} whereas JScatFact_2(v,1)={ab,ba}, so the conclusion JScatFact_{≤3}(u,1)=JScatFact_{≤3}(v,1) fails. The proof's assertion that any x∈JScatFact_{k'}(u,ℓ) can be extended to a word in JScatFact_k(u,ℓ) by inserting blocks y_i is unjustified and is false when |u|<k; the lemma needs an explicit length hypothesis (e.g., k≤|u|,|v|) and a proof of the extension step.
[Lemma 34 and Proposition 35] The proof of Lemma 34 asserts without argument that if u[k+1]∈alph(r(w)) then δ_w(u)=0. This is the key property that also underlies the third equality in the proof of Proposition 35 (ScatFact_{k+1}(w)=ScatFact_k(w)·alph(r(w))). It is true, but it needs a proof: because w has exactly k arches, any length-k word can be embedded in the first k arches, and the letter u[k+1] can then be taken from r(w). As written, a load-bearing step of the universality section is left unjustified.
[Lemma 24] The proof of Lemma 24 contains a final paragraph ('Let v∈JScatFact(w)...') that is unrelated to the lemma and appears to be a leftover from another proof; it should be deleted. The derivation of the third claim w∼_{k,ℓ+1}v is only alluded to; it should be spelled out (it follows from the first claim together with the second applied to ℓ+1).
[Proposition 33] The 'dejumbling' step in the proof of Proposition 33 asserts that for u=xay with δ_w(u)>ℓ+1 one can choose a and a split w=αβ satisfying lcsf(x,α)+lcsf(y,β)=lcsf(u,w) and |α|_a>|x|_a, and then insert a into x so that lcsf increases by exactly one. These are standard LCS properties, but they are not proved or cited, and the existence of a letter whose deletion reduces δ_w by exactly one also needs a short argument (choose a letter not used in a longest common scattered factor). Since this step is used to show that every intermediate jumble level is nonempty, the proof should be completed.

minor comments (5)

[Definition 6 and Lemma 9] The overline notation JScatFact(w,ℓ) for the exact-ℓ set is used in several places but is easy to lose in typesetting; please define it explicitly and use it consistently.
[Lemma 11 statement] The statement quantifies 'w∈Σ*' but not u and v; presumably the claim is for all u,v∈Σ*.
[Lemma 9 proof] In the proof of part (1), the equation 'l+|v|=|u|' uses a lowercase ell; this should be ℓ for consistency.
[Corollary 28] The proof claims 'It is left to show that w,u∈JScatFact(v)', but this is not needed for the equivalence and may fail when u has more occurrences than w of some letter other than the chosen a_i; consider removing this sentence or stating the additional hypotheses under which it holds.
[Proposition 29 proof] The proof mentions both u=a_i^{p(w)[i]} and u'=a_i^{p(w')[i]}, but a single word is sufficient; the second word is not needed for the argument.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the jumble index is defined independently and then proved equal to |u| − lcsf(u,w); no fitted inputs or load-bearing self-citations.

full rationale

The central identity Lemma 9(3), δ_w(u) = |u| − lcsf(u,w), is a direct consequence of Definitions 5 and 6 together with Definition 8: JScatFact(w,ℓ) asks for a common scattered factor of u and w of length |u|−ℓ, so minimizing ℓ is exactly maximizing the length of a common scattered factor. This is a theorem about the new measure, not a definition of the measure in terms of lcsf, so it is not circular. No parameter is fitted to data and no prediction is statistically forced. The self-citations that appear (e.g., [14] in Lemma 38, [33] in Proposition 16) cite standard or prior results about universality and well-quasi-ordering; they are background facts, not inputs that secretly define the jumble index. The formally incorrect statement of Lemma 9(3), which omits the hypothesis p(u) ≤ p(w), and the terse arch-factorization step in Lemma 34 are correctness or completeness concerns, not circular dependencies. The paper's new results (jumbled Simon congruence, jumbled universality bounds) are derived from explicit definitions and external classical theorems (Lyndon–Schützenberger, Hébrard arch factorization), with no reduction of a claimed output to an equivalent input.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper's results are derived from standard definitions and prior theorems. No free parameters are fitted to data and no new unobserved entities are postulated. The main external inputs are the arch factorization, the Lyndon-Schützenberger theorem, Kruskal's well-quasi-ordering, and classical Simon congruence results.

assumptions (4)

domain assumption Arch factorization of a word exists uniquely, with each arch having universality index 1 and a remainder whose alphabet is a proper subset, and the standard arch properties hold (Definition 15).
Used in Lemmas 34-36 to characterize 1-jumbled factors and to construct the words w_x; properties are cited from Hébrard [23].
standard math Lyndon-Schützenberger theorem: if xy = yx, then x and y are powers of a common word.
Used in Lemma 36 to conclude v = x^{|v|} from xv = vx when x is a single letter.
standard math Kruskal's theorem that words over a finite alphabet are well-quasi-ordered under the scattered factor relation.
Used in Proposition 16 to show every set of pairwise |_J-incomparable words is finite.
domain assumption Known results on the classical Simon congruence, in particular that its classes have size 1 or infinity for ℓ = 0.
Used in Section 4 as the baseline against which jumbled Simon classes are compared, citing Lothaire [36] and Simon [46].

how reviews work

0 comments

Cite this review

Pith. "Pith review of Jumbled Scattered Factors." pith.science (2026). https://pith.science/paper/SC5OLYAB

@misc{pith2026250603814,
  author       = {Pith},
  title        = {Pith review of: Jumbled Scattered Factors},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SC5OLYAB}},
  note         = {Machine review of arXiv:2506.03814}
}

abstract

In this work, we combine the research on (absent) scattered factors with the one of jumbled words. For instance, $\mathtt{wolf}$ is an absent scattered factor of $\mathtt{cauliflower}$ but since $\mathtt{lfow}$, a jumbled (or abelian) version of $\mathtt{wolf}$, is a scattered factor, $\mathtt{wolf}$ occurs as a jumbled scattered factor in $\mathtt{cauliflower}$. A \emph{jumbled scattered factor} $u$ of a word $w$ is constructed by letters of $w$ with the only rule that the number of occurrences per letter in $u$ is smaller than or equal to the one in $w$. We proceed to partition and characterise the set of jumbled scattered factors by the number of jumbled letters and use the latter as a measure. For this new class of words, we relate the folklore longest common subsequence (scattered factor) to the number of required jumbles. Further, we investigate the smallest possible number of jumbles alongside the jumbled scattered factor relation as well as Simon's congruence from the point of view of jumbled scattered factors and jumbled universality.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

51 extracted references · 51 canonical work pages

[1]

Adamson, P

D. Adamson, P. Fleischmann, A. Huch, T. Koß, F. Manea, and D. Nowotka. k- universality of regular languages. InISAAC 2023, volume 283 ofLIPIcs, pages 4:1–4:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023

work page 2023
[2]

Tight Bounds for the Number of Absent Subsequences

D. Adamson, P. Fleischmann, A. Huch, and M. Wiedenhöft. Tight bounds for the number of absent scattered factors.CoRR, abs/2407.18599, 2024. URL:https: //doi.org/10.48550/arXiv.2407.18599

work page Pith review arXiv doi:10.48550/arxiv.2407.18599 2024
[3]

Artikis, A

A. Artikis, A. Margara, M. Ugarte, S. Vansummeren, and M. Weidlich. Complex event recognition languages: Tutorial. InDEBS, pages 7–10, 2017

work page 2017
[4]

R. A. Baeza-Yates. Searching subsequences.Theor. Comput. Sci., 78(2):363–376, 1991

work page 1991
[5]

Bannai, T

H. Bannai, T. I, T. Kociumaka, D. Köppl, and S. J. Puglisi. Computing longest Lyndon subsequences and longest common Lyndon subsequences.Algorithmica, 86(3):735–756, 2024

work page 2024
[6]

Barker, P

L. Barker, P. Fleischmann, K. Harwardt, F. Manea, and D. Nowotka. Scattered factor-universality of words. InDLT 2020, volume 12086 ofLNCS, pages 14–28. Springer, 2020

work page 2020
[7]

Baumann, M

P. Baumann, M. Ganardi, R. S. Thinniyam, and G. Zetzsche. Existential defin- ability over the subword ordering.Log. Methods Comput. Sci., 19(4), 2023

work page 2023
[8]

Bringmann and M

K. Bringmann and M. Künnemann. Multivariate fine-grained complexity of longest common subsequence. InSODA 2018, pages 1216–1235. SIAM, 2018

work page 2018

Show all 51 references

[9]

Burcsi, F

P. Burcsi, F. Cicalese, G. Fici, and Z. Lipták. Algorithms for jumbled pattern matching in strings.Int. J. Found. Comput. Sci., 23(2):357–374, 2012

2012
[10]

J. D. Day, P. Fleischmann, M. Kosche, T. Koß, F. Manea, and S.Siemer. The edit distance to k-subsequence universality. InSTACS 2021, volume 187 ofLIPIcs, pages 25:1–25:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021

2021
[11]

D. T. Do, T. T. Q. Le, and N.-Q.-K. Le. Using deep neural networks and biological subwords to detect protein s-sulfenylation sites.Briefings Bioinform., 22(3), 2021

2021
[12]

A. W. M. Dress and P. L. Erdős. Reconstructing words from subwords in linear time.Annals of Combinatorics, 8:457–462, 2005

2005
[13]

S. Z. Fazekas, T. Koß, F. Manea, R. Mercas, and T. Specht. Subsequence matching and analysis problems for formal languages. InISAAC 2024, volume 322 ofLIPIcs, pages 28:1–28:23, 2024

2024
[14]

Fleischmann, S.B

P. Fleischmann, S.B. Germann, and D. Nowotka. Scattered factor universality–the power of the remainder.preprint arXiv:2104.09063 (published at RuFiDim), 2021

2021 arXiv
[15]

Fleischmann, L

P. Fleischmann, L. Haschke, J. Höfer, A. Huch, A. Mayrock, and D. Nowotka. Nearlyk-universal words - investigating a part of Simon’s congruence.Theor. Comput. Sci., 974:114113, 2023

2023
[16]

Fleischmann, J

P. Fleischmann, J. Höfer, A. Huch, and D. Nowotka.α-β-factorization and the binary case of Simon’s congruence. InFCT 2023, volume 14292 ofLNCS, pages 190–204. Springer, 2023

2023
[17]

Fleischmann, S

P. Fleischmann, S. Kim, T. Koß, F. Manea, D. Nowotka, S. Siemer, and M. Wieden- höft. Matching patterns with variables under Simon’s congruence. InRP 2023, volume 14235 ofLNCS, pages 155–170. Springer, 2023

2023
[18]

Fleischmann, M

P. Fleischmann, M. Lejeune, F. Manea, D. Nowotka, and M. Rigo. Reconstructing words from right-bounded-block words.Int. J. Found. Comput. Sci., 32(6):619– 640, 2021

2021
[19]

P. J. Forrester and A. Mays. Finite size corrections relating to distributions of the length of longest increasing subsequences.Adv. Appl. Math., 145:102482, 2023. Jumbled Scattered Factors 17

2023
[20]

Frochaux and S

A. Frochaux and S. Kleest-Meißner. Puzzling over subsequence-query extensions: Disjunction and generalised gaps. InAMW 2023, volume 3409 ofCEUR Workshop Proceedings. CEUR-WS.org, 2023

2023
[21]

Gagie, D

T. Gagie, D. Hermelin, G. M. Landau, and O. Weimann. Binary jumbled pattern matching on trees and tree-like structures.Algorithmica, 73(3):571–588, 2015

2015
[22]

Halfon, P

S. Halfon, P. Schnoebelen, and G. Zetzsche. Decidability, complexity, and expres- siveness of first-order logic over the subword ordering. InLICS 2017, pages 1–12. IEEE Computer Society, 2017

2017
[23]

J.-J. Hébrard. An algorithm for distinguishing efficiently bit-strings by their sub- sequences.Theor. Comput. Sci., 82(1):35–49, 1991

1991
[24]

Karandikar, M

P. Karandikar, M. Kufleitner, and P. Schnoebelen. On the index of Simon’s con- gruence for piecewise testability.Inf. Process. Lett., 115(4):515–519, 2015

2015
[25]

Karandikar and P

P. Karandikar and P. Schnoebelen. The height of piecewise-testable languages and the complexity of the logic of subwords.Log. Methods Comput. Sci., 15(2), 2019

2019
[26]

Karhumäki, S

J. Karhumäki, S. Puzynina, M. Rao, and M. A. Whiteland. On cardinalities of k-abelian equivalence classes.Theor. Comput. Sci., 658:190–204, 2017

2017
[27]

Kim, Y.-S

S. Kim, Y.-S. Han, S.-K. Ko, and K. Salomaa. On Simon’s congruence closure of a string.Theor. Comput. Sci., 972:114078, 2023

2023
[28]

Kim, Y.-S

S. Kim, Y.-S. Han, S.-K. Ko, and K. Salomaa. On the Simon’s congruence neigh- borhood of languages. InDLT, volume 13911 ofLNCS, pages 168–181. Springer, 2023

2023
[29]

Kim, S.-K

S. Kim, S.-K. Ko, and Y.-S. Han. Simon’s congruence pattern matching.Theor. Comput. Sci., 994:114478, 2024

2024
[30]

Kleest-Meißner, R

S. Kleest-Meißner, R. Sattler, M. L. Schmid, N. Schweikardt, and M. Weidlich. Discovering event queries from traces: Laying foundations for subsequence-queries with wildcards and gap-size constraints. InICDT, volume 220 ofLIPIcs, pages 18:1–18:21, 2022

2022
[31]

Kleest-Meißner, R

S. Kleest-Meißner, R. Sattler, Markus L. Schmid, N. Schweikardt, and M. Weidlich. Discovering multi-dimensional subsequence queries from traces - from theory to practice. InBTW, volume P-331 ofLNI, pages 511–533, 2023

2023
[32]

Kosche, T

M. Kosche, T. Koß, F. Manea, and S. Siemer. Absent subsequences in words. Fundam. Informaticae, 189(3-4):199–240, 2022

2022
[33]

The theory of well-quasi-ordering: A frequently discovered concept.J

Joseph B Kruskal. The theory of well-quasi-ordering: A frequently discovered concept.J. Comb. Theory, Ser. A, 13(3):297–305, 1972

1972
[34]

D. Kuske. The subtrace order and counting first-order logic. InCSR, pages 289–
[35]

Kuske and G

D. Kuske and G. Zetzsche. Languages ordered by the subword order. InFoSSaCS, pages 348–364. Springer International Publishing, 2019

2019
[36]

Lothaire.Combinatorics on Words

M. Lothaire.Combinatorics on Words. Cambridge Mathematical Library. Cam- bridge University Press, 1997

1997
[37]

D. Maier. The complexity of some problems on subsequences and supersequences. J. ACM, 25(2):322–336, 1978

1978
[38]

J. Manuch. Characterization of a word by its subwords. InDLT 1999, pages 210–219. World Scientific, 1999

1999
[39]

Mateescu, A

A. Mateescu, A. Salomaa, and S. Yu. Subword histories and parikh matrices.J. Comput. Syst. Sci., 68(1):1–21, 2004

2004
[40]

R. Parikh. On context-free languages.J. ACM, 13(4):570–581, 1966

1966
[41]

Puzynina

S. Puzynina. Abelian properties of words. InWORDS 2019, volume 11682 of LNCS, pages 28–45. Springer, 2019

2019
[42]

A. Salomaa. Counting (scattered) subwords.Bull. EATheor. Comput. Sci., 81:165– 179, 2003. 18 Fleischmann et al

2003
[43]

Sattler, S

R. Sattler, S. Kleest-Meißner, S. Lange, M. L. Schmid, N. Schweikardt, and M. Wei- dlich. Disces: Systematic discovery of event stream queries.Proc. ACM Manag. Data, 3(1), 2025

2025
[44]

Schnoebelen and J

P. Schnoebelen and J. Veron. On arch factorization and subword universality for words and compressed words. InWORDS 2023, volume 13899 ofLNCS, pages 274–287. Springer, 2023

2023
[45]

Simon.Hierarchies of events with dot-depth one

I. Simon.Hierarchies of events with dot-depth one. PhD thesis, University of Waterloo, 1972

1972
[46]

I. Simon. Piecewise testable events. InAFL, 2nd GI Conference, Kaiserslautern, May 20-23, 1975, volume 33 ofLNCS, pages 214–222. Springer, 1975

1975
[47]

Tronícek

Z. Tronícek. On problems related to absent subsequences. InCOCOA 2023, volume 14462 ofLNCS, pages 351–363. Springer, 2023

2023
[48]

R. A. Wagner and M. J. Fischer. The string-to-string correction problem.J. ACM, 21(1):168–173, 1974

1974
[49]

C. Wang, K. Cho, and J. Gu. Neural machine translation with byte-level subwords. InEAAI 2020, pages 9154–9160. AAAI Press, 2020

2020
[50]

Zetzsche

G. Zetzsche. The Complexity of Downward Closure Comparisons. InICALP 2016, volume 55 ofLIPIcs, pages 123:1–123:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016

2016
[302]

Springer International Publishing, 2020

2020

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Adamson, P

D. Adamson, P. Fleischmann, A. Huch, T. Koß, F. Manea, and D. Nowotka. k- universality of regular languages. InISAAC 2023, volume 283 ofLIPIcs, pages 4:1–4:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023

work page 2023

[2] [2]

Tight Bounds for the Number of Absent Subsequences

D. Adamson, P. Fleischmann, A. Huch, and M. Wiedenhöft. Tight bounds for the number of absent scattered factors.CoRR, abs/2407.18599, 2024. URL:https: //doi.org/10.48550/arXiv.2407.18599

work page Pith review arXiv doi:10.48550/arxiv.2407.18599 2024

[3] [3]

Artikis, A

A. Artikis, A. Margara, M. Ugarte, S. Vansummeren, and M. Weidlich. Complex event recognition languages: Tutorial. InDEBS, pages 7–10, 2017

work page 2017

[4] [4]

R. A. Baeza-Yates. Searching subsequences.Theor. Comput. Sci., 78(2):363–376, 1991

work page 1991

[5] [5]

Bannai, T

H. Bannai, T. I, T. Kociumaka, D. Köppl, and S. J. Puglisi. Computing longest Lyndon subsequences and longest common Lyndon subsequences.Algorithmica, 86(3):735–756, 2024

work page 2024

[6] [6]

Barker, P

L. Barker, P. Fleischmann, K. Harwardt, F. Manea, and D. Nowotka. Scattered factor-universality of words. InDLT 2020, volume 12086 ofLNCS, pages 14–28. Springer, 2020

work page 2020

[7] [7]

Baumann, M

P. Baumann, M. Ganardi, R. S. Thinniyam, and G. Zetzsche. Existential defin- ability over the subword ordering.Log. Methods Comput. Sci., 19(4), 2023

work page 2023

[8] [8]

Bringmann and M

K. Bringmann and M. Künnemann. Multivariate fine-grained complexity of longest common subsequence. InSODA 2018, pages 1216–1235. SIAM, 2018

work page 2018