The original publication is available at http://www.springerlink.com/content/y46h6501746506p0/fulltext.pdf
Inspired by recent work of Meduna on deep pushdown automata, we consider the computational power of a class of basic program schemes, NPSDSs, based around assignments, while-loops and non-deterministic guessing but with access
to a deep pushdown stack which, apart from having the usual push and pop instructions, also has deep-push instructions which allow elements to be pushed to stack locations deep within the stack. We syntactically define sub-classes of NPSDSs by restricting the occurrences of pops, pushes and deep-pushes and capture the complexity classes NP and PSPACE. Furthermore, we show that all problems accepted by program schemes of NPSDSs are in EXPTIME.
We study the infinite words generated by an iterated gsm. The motivation was two fold. The first one was given by the apparent similarity between the iterated gsm and the iterated morphism. However contrary to the appearences almost all questions become undecidable. The second one was to disprove the following conjecture of Berstel: The language of coprefixes of an infinite word w is context free iff w is generated by an iterated gsm. We use for that the infinite word: w = abca2ba2bca4ba4ba2ba4bc ... (a2nb)2nc .... We prove also that the degree of the ambiguity problem for coprefixes of iterated gsm is ¿1-complete in the Kleene hierarchy. This result fills the gap between the degree of this problem for iterated morphisms which is ¿0 and for arbitrary context-free grammars which is ¿2-complete.
This work has been supported by the “Accion Integrada Hispano Francesa, 1987, 20/10”
We study the class of sets with small generalized Kolmogorov complexity. The following results are established: 1. A set has small generalized Kolmogorov complexity if and only if it is “semi-isomorphic” to a tally set. 2. The class of sets with small generalized Kolmogorov complexity is properly included in the class of “self-p-printable” sets. 3. The class of self-p-printable sets is properly included in the class of sets with “selfproducible circuits”. 4. A set S has self-producible circuits if and only if there is a tally set T such that P(T)=P(S). 5. If a set S has self-producible circuits, then NP(S)=NPB(S), where NPB( ) is the restriction of NP( ) studied by Book, Long, and Selman . 6. If a set S is such that NP(S) =NPB(S), then NP(S)¿P(S¿SAT).