Journal article
Games for complexity of second-order call-by-name programs
- Abstract:
-
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 PSPACE 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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 1.2MB, Terms of use)
-
- Publisher copy:
- 10.1016/j.tcs.2005.05.013
Authors
- Funding agency for:
- Murawski, A
- Grant:
- GR/R88861/01
- Funding agency for:
- Murawski, A
- Grant:
- GR/R88861/01
- Publisher:
- Elsevier
- Journal:
- Theoretical Computer Science More from this journal
- Volume:
- 343
- Issue:
- 1-2
- Pages:
- 207–236
- Publication date:
- 2005-10-01
- Edition:
- Publisher's version
- DOI:
- ISSN:
-
0304-3975
- Language:
-
English
- Keywords:
- Subjects:
- UUID:
-
uuid:2b4f1d3e-350a-4590-9d6d-929b5da64f7e
- Local pid:
-
ora:10783
- Deposit date:
-
2015-03-31
- ARK identifier:
Terms of use
- Copyright holder:
- Elsevier BV
- Copyright date:
- 2005
- Notes:
- Copyright 2005 Elsevier B.V. All rights reserved. Re-use of this article is permitted in accordance with the Terms and Conditions set out at http://www.elsevier.com/open-access/userlicense/1.0/
- Licence:
- Other
If you are the owner of this record, you can report an update to it here: Report update to this record