Properties of Finite and Pushdown Transducers

Abstract

We consider the subfamilies of rational and pushdown transducers and corresponding translations (relations) which are most frequently encountered in the literature. We survey some of the known results on the characterization, factorization, closure properties, decision problems and comparisons of classes and give new results on these properties using either direct proofs or results from other theories such as homomorphic equivalence.