On inverse deterministic pushdown transductions

摘要

Classes of source languages which can be mapped by a deterministic pushdown (DPDA) transduction into a given object language (while their complement is mapped into the complement of the object language) are studied. Such classes of source languages are inverse DPDA transductions of the given object language. Similarly for classes of object languages. The inverse DPDA transductions of the Dyck sets are studied in greater detail: they can be recognized in deterministic storage (log n)' but do not comprise all context free languages; their emptiness problem is unsolvable and their closure under homomorphism constitutes the r.e. sets. For each object language L we can exhibit a storage hardest language for the class of inverse DPDA transductions of L; similarly for the classes of regular, deterministic context free, and context free object languages. Last, we classify the classes of inverse DPDA transductions of the regular, deterministic context free, context free and deterministic context sensitive languages.