${\Sigma_2^P}^{NP}$ is the set of language decided by an alternating turing machine in existential, and then universal state, with an oracle in NP. Both the universal and the existantial part can ...

You should probably take a look at Is $(NP^{NP})^{NP} = NP^{(NP^{NP})}$? and Are Oracles Associative?. I don't know any canonical definition of $(A^B)^C$ hence I've got the same problem as Tsuyoshi ...

I guess the algorithm to "hash-cons" is really interesting. This idea let us usually save both memory, time, and avoid doing many time the same computation by finding quickly equality between many ...

I think that there should be at least one persistant data structure. In particular, the "persistant array" let us obtains a lot of other persistant data-structures where we wouldn't expect them.

I would like to put some non-deterministic algorithm, which may also be in the Book. In particular, I think of the Immerman's algorithm for non-reachability in directed graph in non deterministic log ...

It is known that perl's so-called regexp is powerful enough to be Turing complete; there is even a compiler from usual program to perl regexp. Hence I doubt it makes sense to search for a name for ...

As Venkat told in comments, it seems hard to understand your definition for oracle which aren't defined as some machine characterisation. Let $A^{(B^C)}$ would be the set of TM in $A$ with an oracle ...

Usually I give the factoring problem as example; I first ask for the number that divide 15; usually people can answer 3, 5, and have fun wondering if 1 and 15 are correct answer. Then I give a huge ...

If I understand correctly, you just want a definition of the logic; then you can find a definition of MSO$_j$ (where 2 is a special case) by example in ''Elements of Finite Model Theory'' of Leonid ...

I think you may find interesting answer in Okasaki's book Purely Functional Data Structures. In this book, many data structures are shown, such that every updates are not expensive (usually only take ...

For information, VO is in fact really more powerful than what you state; it contains the entire analytical hierarchy (hence, also the entire arithmetical hierarchy). The result is not published, ...