Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Reasoning about Idealized ALGOL Using Regular Languages
| |
|
Reasoning about Idealized ALGOL Using Regular Languages
Dan R. Ghica7 and Guy McCusker8 
| (7) |
Department of Computing and Information Science, Queen’s University, Kingston, Ontario, Canada, K7L 3N6 |
| (8) |
School of Cognitive and Computing Sciences, University of Sussex at Brighton, Falmer, Brighton, UK, BN1 9QH |
Abstract
We explain how recent developments in game semantics can be applied to reasoning about equivalence of terms in a non-trivial
fragment of Idealized AupLGOL (IA) by expressing sets of complete plays as regular languages. Being derived directly from the fully abstract game semantics
for IA, our method of reasoning inherits its desirable theoretical properties. The method is mathematically elementary and
formal, which makes it uniquely suitable for automation. We show that reasoning can be carried out using only a meta-language
of extended regular expressions, a language for which equivalence is formally decidable.
Keywords Game semantics - ALGOL-like languages - regular languages
This author acknowledges the support of a PGSB grant from the Natural Sciences and Engineering Research Council of Canada.
This paper was written while visiting University of Edinburgh, Laboratory for Foundations of Computer Science.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|