Skip to main content

Complexity of Language Equivalence for t-Turn Pushdown Automata

Supervisor

Suitable for

MSc in Computer Science

Abstract

Language equivalence for t-Turn Pushdown automata was shown to be in coNP by SĂ©nizergues 2003. The aim of the project is to survey this result and perhaps improve the complexity bound using techniques from the following paper:

James Worrell: Revisiting the Equivalence Problem for Finite Multitape Automata. ICALP (2) 2013: 422-433