Journal article icon

Journal article

Functions with local state: regularity and undecidability

Abstract:

We study programs of a finitary ML-like language RMLf with ground-type references. RMLf permits the use of functions with locally declared variables that remain private and persist from one use of the function to the next. Using game semantics we show that this leads to undecidability of program equivalence already at second order. We also examine the extent to which this feature can be captured by regular languages. This gives a decidability result for a second-order fr...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Publisher's version

Actions


Access Document


Files:
Publisher copy:
10.1016/j.tcs.2004.12.036

Authors


More by this author
Institution:
University of Oxford
Department:
Mathematical, Physical & Life Sciences Division - Department of Computer Science
Role:
Author
Publisher:
Elsevier Publisher's website
Journal:
Theoretical Computer Science Journal website
Volume:
338
Issue:
1-3
Pages:
315–349
Publication date:
2005-06-05
DOI:
ISSN:
0304-3975
URN:
uuid:537af42f-01ca-427e-a341-8e114caa5117
Local pid:
ora:10758

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP