bibkey: lohrey2012slp
authors: Markus Lohrey
year: 2012
title: 'Algorithmics on SLP-compressed strings: A survey'
doi: 10.1515/gcc-2012-0016
url: https://doi.org/10.1515/gcc-2012-0016
claim: A straight-line concatenation description can be evaluated in a fixed finite algebra without expanding its represented word; bounded representatives require a fixed generated value set.
strata_touched: []
license: citation-only
triage: anchor

Compressed descriptions and fixed finite values

The survey’s title, author, year and DOI are verified by its Crossref record. It is a bibliographic pointer for SLP-compressed strings. Its full text has not been verified here, and no theorem or precise complexity bound from the survey is imported. The finite-algebra argument below is self-contained elementary exposition, not an attribution of its statement to a numbered result in that source and not a novelty claim.

Fixed finite algebra evaluation

Fix a finite group $G$, a finite alphabet $\Sigma$, a generator interpretation $\eta :\Sigma \to G$, and its finite multiplication table. Suppose that for every value in the submonoid generated by $\eta (\Sigma )$ a representative word over $\Sigma$ is fixed. Their maximum length $C$ is a constant because this value set is fixed and finite. The empty word may represent the identity. These data are independent of the input.

An input consists of finitely many explicitly encoded nodes, each either a letter or an ordered concatenation of two referenced nodes, with a designated root. References must be valid and the dependency graph acyclic. Its bit encoding length is $B$ and its node count is $s$. Shared subexpressions denote repeated word occurrences in the root’s unfolding, rather than multiple executions of the value-computation node.

Proposition (Polynomial acquisition of a bounded representative). A single deterministic algorithm outputs a word of length at most $C$ having the same group value as the fully unfolded root, in $\mathrm{poly}(B)$ bit operations.

Proof. Validate the encoding and obtain a topological order. At a letter store $\eta$ of its label; at a concatenation node store the ordered product of its two stored values. By induction on that order, every stored value equals the value of its unfolded subword. There are $O(s)$ fixed-table multiplications, each operating on constant-size labels. Output the fixed representative of the root value.

The $O(s)$ count concerns algebraic multiplications, not free pointer access. Input parsing, cycle detection, topological sorting, reading and storing references, and retrieving child labels all have ordinary polynomial bit implementations; even repeated scans of the explicit node list suffice. Output cost is bounded by the fixed representative length. No expanded word is needed. The proof uses a homomorphic value map and finite closure; no particular group identity is assumed. $\square$

For the fixed matrices $a=-iX,b=-iY$, the generated group is $Q_8$. The empty word and $a,b,ba,a^2,a^3,b^3,ab$ represent its eight values, with maximum length three. The exact FIB application, its matrix multiplication convention, binary-index shortcut and future-environment limitations are stated in Second-order relation completion §116.

The finiteness hypothesis is substantive. If the group, multiplication table, generators, target precision or representation dimension grows with the input, their description, construction, arithmetic and representative lengths must be counted separately. Equality of endpoint values also does not reproduce the original word, its parse tree, execution clock or intermediate records. Requiring that expanded output can impose a cost proportional to its length. This argument is not a general short-circuit compiler for arbitrary quantum circuits.

Source

• DOI record, Groups – Complexity – Cryptology 4(2), 241–299.
• Crossref metadata.

This note is an original citation-only exposition and includes no copied article text or PDF.

Fibonacci source word and indexed reading

The following elementary example separates aperiodicity of a source word from the cost of observing it. It imports no unverified survey theorem. Define $W_0=a$, $W_1=b$, and $W_{k+2}=W_{k+1}{W}_k$, with $F_0=0,F_1=1$. For $k\ge 1$, $W_k$ is a prefix of $W_{k+1}$; $W_0$ is not a prefix of $W_1$. Their lengths tend to infinity, defining a unique infinite word. Induction gives

$$|W_k|=F_{k+1},{\#}_b(W_k)=F_k.$$

This is the classical Fibonacci word, with $b=0,a=1$: under the substitution $0\mapsto 01,1\mapsto 0$, its $j$th iterated word is $W_{j+1}$. The exact source definition and its bibliographic locator are in the Garg note. The following facts are elementary consequences of that definition, not new antipower results.

If the infinite word were eventually periodic, its frequency of $b$ along all sufficiently long prefixes would converge to a rational number: the number of $b$’s in one period divided by the period length. But along its prefix subsequence $W_k$ the frequency tends to

$$\underset{k\to \infty }{\lim }\frac{F_k}{F_{k+1}}=\frac{1}{\phi },\phi =\frac{1+\sqrt{5}}{2},$$

which is irrational. Hence the word is not eventually periodic. Only this subsequence limit is needed for the contradiction.

Nevertheless, for a positive one-based index $M$ given in canonical binary without leading zeros, its $M$th letter can be computed in $O({\log }^2(M+2))$ bit operations. If padded encodings are allowed, add their actual input-reading length to this bound. Build successive Fibonacci lengths until $|W_k|\ge M$, choosing the least such $k\ge 1$. For $k\ge 2$, compare $M$ with $|W_{k-1}|$: descend to $W_{k-1}$ if it lies in the left part of $W_k=W_{k-1}{W}_{k-2}$, otherwise subtract that length and descend to $W_{k-2}$. At $k=0,1$, return $a,b$ respectively. There are $O(\log (M+2))$ descents and every integer has $O(\log (M+2))$ bits. Maintain consecutive Fibonacci lengths and update them by subtraction when descending, using a constant number of sequentially stored registers. The construction, comparisons, register movement and subtraction then have the stated bit bound, without free access to an exponentially expanded word.

Aperiodicity therefore does not imply high indexed-reading cost. Nor must every observable of an aperiodic source retain its aperiodicity: the fixed Pauli endpoint of these finite words has the project’s three-periodic root value and short compiler. That observation preserves a specified operator, not the entire infinite word or its history.

The same logical distinction appears for primes: eventual periodicity of the prime indicator with a positive period $d$ would, for a sufficiently large prime $p$, force $p+pd=p(1+d)$ to be prime, a contradiction. Yet AKS supplies polynomial-time binary primality testing. This comparison asserts neither an efficient factorization algorithm nor any connection between aperiodicity alone and NP hardness.