We prove two results to the effect that 1-counter languages give rise to the full complexity of context-free and even recursively enumerable languages: (1) There are pairs of disjoint deterministic one-counter languages whose union, ordered lexicographically, has an un-decidable ∑_3-theory and, alternatively, true arithmetic can be reduced to its first-order theory. (2) It is undecidable whether the union of two disjoint deterministic 1-counter languages, ordered lexicographically, is dense. In several aspects, these results cannot be sharpened any further: (a) they do not hold for single deterministic 1-counter languages [Cau02, Cau03], (b) they do not hold for the ∑_2-theory (Corollary 1.2), and (c) the first-order theory can always be reduced to true arithmetic (since these linear orders are computable structures).
展开▼
