The equivalence problems for various types of finite transducers, pushdown automata, and pushdown transducers are being investigated. The research being done on these problems is expected to contribute to the eventual solution of the famous equivalence problem for deterministic pushdown automata. Two entirely different techniques for proving the decidability of equivalence problems are being used. The first one, called the "test-set approach" has already been successfully applied: the principal investigator in collaboration with J. Karhumaki used it to solve the (previously open) equivalence problem for two classes of finite transducers. The second method based on the "synchronizability conjecture" is intended for DPDAs and deterministic pushdown transducers. The PI is also continuing his investigations in cellular automata and systolic systems. The PI is a leading world figure in the solving of difficult decidability questions. He has recently produced solutions to related problems and is as likely as anyone to solve the difficult problems proposed.
