Abstract :
By generalizing the notions of a one counter machine and of a finite turn pushdown store automaton, it is possible to define an omega 2-hierarchy of families of context-free languages such that each subfamily is infinite, closed under union, concatenation and closure, homomorphism, intersection with regular sets and inverse homomorphism and reversal. Each subfamily can be characterized in a manner akin to the Chomsky-Schutzenberger characterization of the context-free languages. Whenever two subfamilies are incomparable it is undecidable whether a member of one belongs to the other.
