Testing k-binomial equivalence
read the original abstract
Two words $w_1$ and $w_2$ are said to be $k$-binomial equivalent if every non-empty word $x$ of length at most $k$ over the alphabet of $w_1$ and $w_2$ appears as a scattered factor of $w_1$ exactly as many times as it appears as a scattered factor of $w_2$. We give two different polynomial-time algorithms testing the $k$-binomial equivalence of two words. The first one is deterministic (but the degree of the corresponding polynomial is too high) and the second one is randomised (it is more direct and more efficient). These are the first known algorithms for the problem which run in polynomial time.
This paper has not been read by Pith yet.
Forward citations
Cited by 3 Pith papers
-
Tractable Gap-Constraint Languages for Complex Event Recognition
Subsequence matching with gap-constraints is solvable in O(|D|(|u| + |C|)) time under left-convexity of the languages, optimal under SETH.
-
Binary binomial equivalence via hyperplane arrangements
An explicit arrangement of n hyperplanes in 3-space indexes binary 2-binomial equivalence classes of binary words of length n, with class sizes given by coefficients of Gaussian binomials.
-
Absent Subsequences in Words
The paper introduces minimal and shortest absent subsequences, gives combinatorial characterizations with compact representations, and provides efficient algorithms to test membership and compute the lexicographically...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.