The Library
ML and extended branching VASS
Tools
Tools
Tools
Cotton-Barratt, C., Murawski, Andrzej S. and Ong, C.-H. L. (2017) ML and extended branching VASS. In: 26th European Symposium on Programming (ESOP'17), Uppsala, Sweden, 22-29 Apr 2017. Published in: Programming Languages and Systems, 10201 pp. 314-340. ISBN 9783662544334. ISSN 0302-9743.
|
PDF
WRAP-ML-extended-branching-VASS-2017-Murawski-2017.pdf - Accepted Version - Requires a PDF viewer. Download (818Kb) | Preview |
Official URL: https://doi.org/10.1007/978-3-662-54434-1_12
Abstract
We prove that the observational equivalence problem for a finitary fragment of ML is recursively equivalent to the reachability problem for extended branching vector addition systems with states (EBVASS). Our proof uses the fully abstract game semantics of the language. We introduce a new class of automata, VPCMA, as a representation of the game semantics. VPCMA are a version of class memory automata equipped with a visibly pushdown stack; they serve as a bridge enabling interreducibility of decision problems between the game semantics and EBVASS. The results of this paper complete our programme to give an automata classification of the ML types with respect to the observational equivalence problem for closed terms.
| Item Type: | Conference Item (Paper) | ||||||
|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||
| Divisions: | Faculty of Science > WMG (Formerly the Warwick Manufacturing Group) | ||||||
| Library of Congress Subject Headings (LCSH): | ML (Computer program language), Programming languages (Electronic computers), Game-theoretical semantics | ||||||
| Series Name: | Lecture Notes in Computer Science | ||||||
| Journal or Publication Title: | Programming Languages and Systems | ||||||
| Publisher: | Springer | ||||||
| ISBN: | 9783662544334 | ||||||
| ISSN: | 0302-9743 | ||||||
| Official Date: | 19 March 2017 | ||||||
| Dates: |
|
||||||
| Date of first compliant deposit: | 8 March 2017 | ||||||
| Volume: | 10201 | ||||||
| Page Range: | pp. 314-340 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||
| Conference Paper Type: | Paper | ||||||
| Title of Event: | 26th European Symposium on Programming (ESOP'17) | ||||||
| Type of Event: | Conference | ||||||
| Location of Event: | Uppsala, Sweden | ||||||
| Date(s) of Event: | 22-29 Apr 2017 | ||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
