Figure 1.
Figure 2.
Figure 3.
Figure 4.
Figure 5.
Figure 6.
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
|
WG | the word problem for G, where G is any finitely generated virtually free group |