Technical University of Ostrava
4pm Monday, 18th of May, 2009
Room 4.31/4.33, Informatics Forum
The decidability question for language equivalence of deterministic pushdown automata (dpda) has been a famous problem in language theory. The question had been open since 1960s, before finally solved positivitely by S\'enizergues in 1997. Later Stirling, and also S\'enizergues, provided simpler proofs than the original long technical proof. So far the strongest version, providing also a primitive recursive complexity upper bound, appeared as a conference paper by Stirling in 2002. The talk is intended to provide another look at this latest version, describing it in a modified conceptual framework, which should hopefully lead to a more illuminating presentation. A crucial point of this modified presentation consists in representing the dpda configurations as trees and working directly with them; thus the previously used transformation to strict deterministic grammars and some other technical issues are avoided.