Table 1.
Some languages recognized in 2O(n) time by 2QCFAs.
| Language | Description |
|---|---|
| PAL | { w ∣ w = wR } |
| TWIN | { w#w ∣ w ∈ { a, b }∗ } |
| MULT | { x#y#z | x, y, z are natural numbers in binary notation and x ⋅ y = z } |
| SQUARE | { aibi2 ∣ i > 0 } |
| POWER | { aib2i ∣ i > 0 } |
| any “polynomial language” | A polynomial language [27] is defined as , where a1, …, ak, b1, …, br are distinct symbols, and each pi is a polynomial with integer coefficients. |
| WG | the word problem for G, where G is any finitely generated virtually free group |
Figure 1.
A verifier V for a language recognized by 2DFA(2) M.
Figure 2.
A prover that simulates N1 on its input and reports its head readings in each round.
Figure 3.
A verifier based on a DS-FK problem (PAD(L),
), where L ∈ ℒ(2DFA(2s)).
Figure 4.
A quantum prover based on (PAD(L),
), where L ∈ BQTISP∗(2kn, s(n)) ∩ ℒ(2DFA(2s)).
Figure 5.
A verifier V based on (PAD(SQUARE), PAD(SUBSQUARE)).
Figure 6.
A quantum prover based on (PAD(SQUARE), PAD(SUBSQUARE)).