Pushdown Automata and Game Semantics

  • Stirling, Colin (Principal Investigator)

Project Details


Examined various decision problems in automata theory that are applicable to the semantics of programming languages.

Layman's description

Trying to understand when it is possible to solve a particular set of equations.

Key findings

Developed automata and games for examining structures with binding and, in particular, terms of lambda calculus.. These techniques were used to solve an outstanding open problem in the theory of simply typed lambda calculus,
namely the higher-order matching problem.
Effective start/end date1/12/0431/05/10


  • EPSRC: £94,424.00


Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.