Games for complexity of second-order call-by-name programs
We use game semantics to show that program equivalence and program approximation in a second-order fragment of Idealized Algol are PSPACE-complete. The result relies on a MACE construction of deterministic finite automata representing strategies defined by second-order programs and is an improvement over the at least exponential space bounds implied by the work of other authors in which extended regular expressions were used. The approach makes it possible to study the contribution of various constructs of the language to the complexity of program equivalence and demonstrates a similarity between call-by-name game semantics and call-by-name interpreters. (c) 2005 Elsevier B.V. All rights reserved.
game semantics computational complexity program analysis