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.
My Menu
Saved Items

Reasoning about Idealized ALGOL Using Regular Languages

Dan R. GhicaContact Information and Guy McCuskerContact Information

(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.

Contact Information Dan R. Ghica
Email: ghica@cs.queensu.ca

Contact Information Guy McCusker
Email: guym@cogs.susx.ac.uk
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.109 • Server: mpweb01
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)