parsing regex with HTML
it's (still, always, will never not be) crazy to me that two finite automata are reducible to one finite automaton but that two stacks is a turing machine.
but hmmm.......one stack's series of operations will always necessarily conform to the paired push–pop protocol. what is the "series of operations" for two?
well, imagine two work for some time, and each produce their own intermediate state (and allow negative push/pop). then the two are compared somehow (?)
why does single-stack paired push/pop achieve immediate solvability? because any previous intermediate state can be converted to any desired final state, by (if necessary) popping everything off then popping exactly the required order back on.
why does dual-automaton reduce? well, we can reframe it as "cartesian product of states, both moving at once". to transition to the desired final state from any intermediate state, each constituent automaton independently makes the same moves it would have alone. there is no move together that escapes the individual constraints, or vice versa.
two-stack with only one symbol is equivalent to one-stack one-sym i.e. an integer
in the case of overlapping stack syms (assume binary for both) the two may produce intermediate states that do not "unzip" or "match up" cleanly
oh oh oh i get it! (?)
the two stacks start from some left and right boundary towards each other in the center. on adjacent input indices, they have each now independently built up a stack (a bit string).
two interpretations:
(1) [adversarial] no matter what one stack does to achieve a desired final state, the other can thwart it. this is clearly true even if they both start with empty stack, and both decisions are made simultaneously.
(2) [goal] the desired final goal is to achieve a specific bit string composed of the left and the right stack's concatenated 1/0 contributions (ignore negatives).
the actual tape machine reduction (which was a challenge problem from jeremy spinrad to me many years ago, and which i just now discovered), is very similar to the above idea, but with the goal to produce a specific tape state.
so both come in from each side, generating the appropriate tape marks, and meet in the middle. however, the head of the tape machine must be at the correct index! but this is simple, by just identifying the distance from each boundary to the central head, and performing only up to those pushes
recall "stack cycles"—stack increments in such cases arrive in units of the stack diff corresponding to the path traced by a traversal of any of the currently active cycles for this point.
let's consider simplified: single stack sym. regardless of diff lengths per cycle available on either side, the two sides can match up: either one diff is an integer multiple of the other, hence match, or diffs are not aligned, which upon repeated addition will match (least common multiple).
the goal in the stack cycles construct is to match the negative of the other's state, hell or high water.
unlike the repeated addition case, the existence of a least common multiple is not guaranteed when consecutive bits (stack syms) do not always share a "color" [only a negated form of the same stack sym will cancel out a stack push, and only if both stack elements are each at the top of their stack]
"match the negative"—false. goal is to construct a given stack diff (sequence of polarized stack syms) separating the two cyclic nodes, by some in-order, one-at-a-time selection of left cycles (pushing more from left) and right cycles (pushing more from right)
so first off, this "stack diff" concept seemed reasonable enough at first, but this construction of "colored" bit strings is just such a ridiculous mathematical object
and the only way to reduce the length of a multicolored bit string is by matching the negation of its top symbol, repeatedly. this weirdly sounds like cryptography now
oh, what if we generate some sequence of cycles from both sides (cycles may pop), then concatenate the left stack diff (from left) with the right (from right), and removing the gap separating the tops of both stacks (which are now adjacent; if stack tops negated each other, pop them off pairwise until stable). this results in an unbroken contiguous multicolored bit string.
i wanna extract the colors. what does that achieve? are they independent?
i would suspect stack cycles can be constructed so that intermediate popping occurs to varying degrees, so consecutive colored bits would not correspond to the cycles. also implies that cycles should incorporate the same pairs of consecutive polarized stack syms at multiple points along the same or different cycles.
so not independent—in fact, deterministic. perhaps we just have two colors (orange/blue) and the orange ones are shifted to the left to produce the final bit string, which is clearly some sort of checksum
i think "linear language" is a better name than "finite-state language", because the matching is literally linear time and because there are no loops