On inverse deterministic pushdown transductions : (prepublication)
Paul M. B. Vitanyi, Walter J. Savitch · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 1976
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 by a DLBA operating in time O(n 2 ) 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 class of regular and context free object languages.Lastly, we classify the classes of inverse DPDA transduction.s of the regular, deterministic context free, context free and deterministic context sensitive languages.