Source-linked AI summary
Subsequence Analysis Problems for Binary Parikh Matrices
Szilárd Zsolt Fazekas, Xinhao Huang, Robert Mercaş
TL;DR
The paper asks how existential and universal subsequence universality can be characterized for binary languages with fixed counts of a, b, and ab. It provides exact arithmetic characterizations and an additive approximation scheme for fixed-pattern containment probability.
Problem
The paper studies existential and universal subsequence universality for binary languages whose words share fixed counts of a, b, and scattered ab subsequences.
Source: §1 · p. 2Method
It analyzes count-defined binary language classes using arithmetic characterizations and develops a partition-based additive approximation scheme for fixed-pattern containment probabilities.
Source: §1 · p. 2Results
Both universality indices have exact arithmetic characterizations computable in polynomial time, and fixed-pattern containment probability admits an additive polynomial-time approximation scheme for fixed error tolerance.
Source: §1 · p. 2Takeaways & Limitations
The containment probability captures the density of representatives containing a pattern, between the existential and universal quantifier extremes.
Source: §1 · p. 2
Abstract
from arXiv · showhide
The universality index corresponding to a word is the largest integer k such that every word of length k over the given alphabet occurs in it as a subsequence. Relative to languages this notion can be investigated with respect to both existential and universal quantifiers, with the former corresponding to the existence of a word in the language with universality index at least k, while the latter considers the index across all words that the language contains. In this work we study the existential (exists-universality) and universal (forall-universality) subsequence universality (as introduced in [Adamson et al., ISAAC 2023]) for binary languages consisting of all words with a fixed number of letters a, letters b, and subsequences ab. We prove that both exists- and forall-universality admit exact arithmetic characterizations for these languages. Extending the above notions, we end the paper by initiating the analysis of the probability of a fixed word occurring as subsequence of the words in such a language. To this end, we prove that, for every fixed pattern word w and an error tolerance, given as input the subsequence counts describing a language, the ratio of words in the language having the pattern w as a subsequence admits an additive approximation scheme that is polynomial-time in the binary encoding of the input counts.
1 Introduction
The paper studies subsequence universality in binary languages defined by fixed counts of a, b, and scattered ab subsequences. It gives arithmetic characterizations of existential and universal universality and an additive approximation scheme for the probability that a fixed pattern occurs.
1 Introduction
- Subsequence analysis also connects to formal-language and verification questions because downward closures of languages have finite automata-theoretic representations.The introduction situates this connection in results by Higman and Haines.Source: §1 · p. 1
- The languages L_A,B,C contain binary words with exactly A letters a, B letters b, and C scattered subsequences ab.They are nonempty exactly when 0 ≤ C ≤ AB, with counts encoded in binary.Source: §1 · p. 2
- The paper determines whether some word, or every word, in each language is k-universal and characterizes both resulting indices.These are the existential and universal quantifier choices for language-level subsequence universality.Source: §1 · p. 2
- Both universality indices for binary 2-deck classes admit exact arithmetic characterizations and are computable in polynomial time in the input counts’ bitlength.The existential result uses A, B, and a formula in the multiplicities; the universal result rules out 4-universality for nonempty classes and analyzes length-three patterns.Source: §1 · p. 2
- The probability that a uniformly chosen representative contains a fixed pattern interpolates between existential and universal containment.Probability 1 and probability greater than 0 correspond to the universal and existential questions for the fixed pattern abab.Source: §1 · p. 2
- For every fixed pattern and error tolerance, its containment probability has an additive approximation scheme polynomial in the bitlength of A, B, and C.The proof uses a correspondence between words in the class and partitions inside an A×B rectangle, together with counting bounds and procedures.Source: §1 · pp. 2–3
2 Preliminaries
The preliminaries define subsequence universality and the binary Parikh-matrix language class used in the paper. They also establish an arch-based characterization of universal binary words and the scope of the nonempty-language assumption.
2 Preliminaries
- A binary Parikh-matrix language L_A,B,C consists of words with A letters a, B letters b, and C subsequences ab; it is nonempty exactly when 0 ≤ C ≤ AB.For binary words, the counts of length-one subsequences and ab determine the 2-deck.Source: §2 · pp. 3–4
- A word is k-universal when every length-k word over the alphabet occurs in it as a subsequence.The equivalent condition is that its subsequences include the full k-spectrum.Source: §2 · p. 4
- The universal index is considered only for nonempty languages, since it is meaningless for an empty language.Source: §2 · p. 4
- The arch-factorization splits a word from the left into shortest possible factors containing every alphabet letter, except possibly the last factor.For binary words, k-universality is characterized by containing a subsequence in {ab,ba}^k.Source: §2 · p. 4
- The shortest k-universal binary words are exactly the words in {ab,ba}^k.Source: §2 · p. 4
3 ∃-universality
Existential universality is characterized by count thresholds and an interval-realization lemma: a candidate alternating subsequence can be embedded in a word with the required counts. These results yield polynomial-time decisions and index computation.
3 ∃-universality
- For fixed v and counts A ≥ |v|_a and B ≥ |v|_b, attainable ab-counts among words containing v form the integer interval [|v|_ab, AB−|v|_ba].The endpoints follow from pairs already contributed by v; adjacent swaps of extra letters realize every intermediate count.Source: §3 · p. 5
- For v in {ab,ba}^k, its ab-subsequence count is determined by its ab blocks and cross-block contributions.Each pair of distinct blocks contributes one ab pair, and each ab block contributes one additional pair.Source: §3 · p. 5
- Theorem 3.3 states that a nonempty L_A,B,C is k-∃-universal if and only if A and B are at least k and C satisfies an additional lower-bound condition.Source: §3 · p. 5
- A k-universal representative can be constructed by choosing v in {ab,ba}^k with a suitable number of ab blocks and embedding it within the prescribed counts.The interval condition is N+t(v) ≤ C ≤ AB−(N+k−t(v)); a feasible integer t(v) yields the embedding.Source: §3 · p. 5
- The decision problem and computation of the existential universality index are polynomial-time in the binary input counts.The decision uses integer comparisons; the index formula uses an integer square root.Source: §3 · p. 6
4 ∀-universality
For binary Parikh matrix languages, forall-universality has an exact arithmetic characterization: its index ranges from 0 to 3 according to the counts A, B, and C. The characterization yields a polynomial-time decision and computation algorithm.
4 ∀-universality
- No nonempty binary Parikh matrix language is 4-∀-universal, so its forall-universality index is at most 3.Avoidance of aaa or bbb is possible when the respective letter count is below 3.Source: §4 · pp. 6–7
- A nonempty language is 2-∀-universal exactly when A,B ≥2 and min(C, AB−C)>0.These conditions ensure every word contains aa, bb, ab, and ba as subsequences.Source: §4 · p. 6
- A nonempty language is 3-∀-universal exactly when A,B ≥3, min(C, AB−C)>max(A,B), and neither A nor B divides C.The proof checks whether any representative can avoid one of the eight binary patterns of length 3.Source: §4 · pp. 6–7
- The forall-universality index is 3 under the stated count and divisibility conditions, otherwise 2, 1, or 0 according to progressively weaker count conditions.Index 2 requires A,B ≥2 and min(C, AB−C)>0; index 1 requires A,B ≥1; the index is 0 if either count is zero.Source: §4 · pp. 6–7
- Given A, B, C, and k in binary, deciding k-∀-universality and computing the index take polynomial time.The procedure checks nonemptiness and a constant number of arithmetic comparisons and divisibility conditions.Source: §4 · p. 8
5 An additive approximation scheme for fixed-pattern containment
The section studies the probability that a fixed binary pattern occurs as a subsequence in a nonempty binary Parikh-matrix language. It gives an additive approximation scheme, using exact computation in boundary cases and a near-one guarantee when all four counts are large.
5 An additive approximation scheme for fixed-pattern containment
- The probability is the fraction of language words containing w; its endpoints correspond to existential and universal subsequence questions.The existential endpoint asks whether the probability is positive, while the universal endpoint asks whether it is 1.Source: §5 · p. 8
- Exact universal subsequence testing is hard even for the fixed pattern abab, motivating approximation of the containment probability.The complement problem is FACTORING*-hard.Source: §5 · pp. 8–9
- For fixed w, avoiding words match one of finitely many alternating templates, yielding a polynomial bound in min{C, AB−C}+1.Each word in the language corresponds to a partition of area C inside an A×B rectangle.Source: §5 · pp. 9–10
- A Gaussian-binomial coefficient lower bound supports the interior probability estimate when A, B, C, and AB−C are sufficiently large.The coefficient bound is stated for every fixed exponent E.Source: §5 · pp. 10, 12
- Once A, B, C, and AB−C exceed a pattern- and error-dependent threshold, any nonzero containment probability is at least 1−ε.The algorithm can then output 1 with additive error at most ε.Source: §5 · pp. 12, 14
- If any of A, B, C, or AB−C is bounded by a fixed R, the probability can be computed exactly in time f_w(R)·poly(log A+log B+log C).Small area is handled by enumerating partitions; bounded height uses fixed-dimensional integer-point counting, and reversal or letter exchange reduces the other boundary cases.Source: §5 · pp. 12–13
- For fixed pattern w and error tolerance ε, the probability admits an additive approximation algorithm polynomial in the binary input counts’ bitlength.The running-time polynomial may depend on w and ε.Source: §5 · pp. 13–14
- The algorithm first tests whether any language word contains w; if none does, it returns 0, otherwise it uses exact boundary computation or the interior estimate.The existence test is polynomial-time, and the interior case returns 1.Source: §5 · pp. 13–14