A virtual machine for supporting reversible probabilistic guarded command languages

Hdl Handle:
http://hdl.handle.net/10149/96017
Title:
A virtual machine for supporting reversible probabilistic guarded command languages
Authors:
Stoddart, W. J. (Bill); Lynas, R. (Robert); Zeyda, F. (Frank)
Affiliation:
University of Teesside. School of Computing.
Citation:
Stoddart, W. J., Lynas, R. and Zeyda, F. (2010) 'A virtual machine for supporting reversible probabilistic guarded command languages', Electronic Notes in Theoretical Computer Science, 253 (6), pp.33-56.
Publisher:
Elsevier
Journal:
Electronic Notes in Theoretical Computer Science
Issue Date:
2010
URI:
http://hdl.handle.net/10149/96017
DOI:
10.1016/j.entcs.2010.02.005
Abstract:
We describe a reversible stack based virtual machine designed as an execution platform for a sequential programming language used in a formal development environment. We revoke Dijkstra's "law of the excluded miracle" to obtain a formal description of backtracking through the use of naked guarded commands and non-deterministic choice, with an operational interpretation of the interaction between guards and choice provided by reversibility. Other constructs supported by the machine provide for the collection of all results of a search, a semantically clean "cut" which terminates a search when the accumulated results satisfy some given criteria, and forms of probabilistic choice, which we distinguish from non-deterministic choice. The paper includes a number of example programs.
Type:
Article
Language:
en
Keywords:
backtracking; formal semantics; forth; probability; reversible computing; virtual machine
ISSN:
1571-0661
Rights:
Author can archive post-print (ie final draft post-refereeing). For full details see http://www.sherpa.ac.uk/romeo/ [Accessed 08/04/2010]
Citation Count:
0 [Scopus, 08/04/2010]

Full metadata record

DC FieldValue Language
dc.contributor.authorStoddart, W. J. (Bill)en
dc.contributor.authorLynas, R. (Robert)en
dc.contributor.authorZeyda, F. (Frank)en
dc.date.accessioned2010-04-08T14:18:49Z-
dc.date.available2010-04-08T14:18:49Z-
dc.date.issued2010-
dc.identifier.citationElectronic Notes in Theoretical Computer Science; 253 (6): 33-56en
dc.identifier.issn1571-0661-
dc.identifier.doi10.1016/j.entcs.2010.02.005-
dc.identifier.urihttp://hdl.handle.net/10149/96017-
dc.description.abstractWe describe a reversible stack based virtual machine designed as an execution platform for a sequential programming language used in a formal development environment. We revoke Dijkstra's "law of the excluded miracle" to obtain a formal description of backtracking through the use of naked guarded commands and non-deterministic choice, with an operational interpretation of the interaction between guards and choice provided by reversibility. Other constructs supported by the machine provide for the collection of all results of a search, a semantically clean "cut" which terminates a search when the accumulated results satisfy some given criteria, and forms of probabilistic choice, which we distinguish from non-deterministic choice. The paper includes a number of example programs.en
dc.language.isoenen
dc.publisherElsevieren
dc.rightsAuthor can archive post-print (ie final draft post-refereeing). For full details see http://www.sherpa.ac.uk/romeo/ [Accessed 08/04/2010]en
dc.subjectbacktrackingen
dc.subjectformal semanticsen
dc.subjectforthen
dc.subjectprobabilityen
dc.subjectreversible computingen
dc.subjectvirtual machineen
dc.titleA virtual machine for supporting reversible probabilistic guarded command languagesen
dc.typeArticleen
dc.contributor.departmentUniversity of Teesside. School of Computing.en
dc.identifier.journalElectronic Notes in Theoretical Computer Scienceen
ref.citationcount0 [Scopus, 08/04/2010]en
or.citation.harvardStoddart, W. J., Lynas, R. and Zeyda, F. (2010) 'A virtual machine for supporting reversible probabilistic guarded command languages', Electronic Notes in Theoretical Computer Science, 253 (6), pp.33-56.-
All Items in TeesRep are protected by copyright, with all rights reserved, unless otherwise indicated.