Preference and Non-deterministic Choice

Hdl Handle:
http://hdl.handle.net/10149/116087
Title:
Preference and Non-deterministic Choice
Book Title:
Theoretical Aspects of Computing – ICTAC 2010
Authors:
Stoddart, W. J. (Bill); Zeyda, F. (Frank); Dunne, S. E. (Steve)
Editors:
Cavalcanti, A. (Ana); Deharbe, D. (David); Gaudel, M-C. (Marie-Claude); Woodcock, J. C. P. (Jim)
Affiliation:
Teesside University. School of Computing.
Citation:
Stoddart, W. J., Zeyda, F. and Dunne, S. E. (2010) 'Preference and Non-deterministic Choice', 7th international colloquium, Natal, Rio Grande do Norte, Brazil, September 1-3, 2010, in Cavalcanti, A. et. al. (eds) Theoretical Aspects of Computing – ICTAC 2010, Lecture Notes in Computer Science, 6255, pp.137-152.
Publisher:
Springer
Conference:
7th international colloquium, Natal, Rio Grande do Norte, Brazil, September 1-3, 2010
Issue Date:
Sep-2010
URI:
http://hdl.handle.net/10149/116087
DOI:
10.1007/978-3-642-14808-8_10
Additional Links:
http://www.springerlink.com/content/978-3-642-14807-1#section=756553&page=1
Abstract:
After reviewing a previously reported relational model of reversible computing, in which non-deterministic choice may represent provisional choice subject to revision by backtracking, we narrate our attempts to express preference within choice. We begin our investigations by recalling Nelson’s extensions to Dijkstra’s calculus, and considering his biased-choice operator as a model of preference. However, we find that this is too short-sighted for our purpose, and we outline the necessity of incorporating a notion of continuation. After considering how this might be achieved in a predicate-transformer approach, we adopt instead a prospective-value semantics that is easily extensible to probabilistic choice; here, we find a clue that helps us to obtain a first formulation of preference. Our formulation, however, takes us into a world of non-monotonic computations, and we are motivated to move on. We look for further inspiration within the execution structures of our reversible virtual machine which provides a construct that records all results of a backtracking search. We add a modified version that records results sequentially, and take its description as the basis for a “temporal order of continuations” semantics, to which we add implementor’s choice, which is now quite distinct from provisional choice. We give a refinement relation and prove the monotonicity of the new semantics and its consistency with respect to our previous prospective-values formalism.
Type:
Meetings and Proceedings; Book Chapter
Language:
en
Keywords:
backtracking; continuations; reversible computing; semantics
Series/Report no.:
Lecture Notes in Computer Science; 6255
ISSN:
0302-9743; 9783642148071
Rights:
Author can archive post-print (ie final draft post-refereeing). For full details see http://www.sherpa.ac.uk/romeo/ [Accessed 23/11/2010]
Citation Count:
0 [Scopus, 23/11/2010]

Full metadata record

DC FieldValue Language
dc.contributor.authorStoddart, W. J. (Bill)en
dc.contributor.authorZeyda, F. (Frank)en
dc.contributor.authorDunne, S. E. (Steve)en
dc.contributor.editorCavalcanti, A. (Ana)en
dc.contributor.editorDeharbe, D. (David)en
dc.contributor.editorGaudel, M-C. (Marie-Claude)en
dc.contributor.editorWoodcock, J. C. P. (Jim)en
dc.date.accessioned2010-11-23T11:41:31Z-
dc.date.available2010-11-23T11:41:31Z-
dc.date.issued2010-09-
dc.identifier.citation0 [Scopus, 23/11/2010]en
dc.identifier.issn0302-9743-
dc.identifier.issn9783642148071-
dc.identifier.doi10.1007/978-3-642-14808-8_10-
dc.identifier.urihttp://hdl.handle.net/10149/116087-
dc.description.abstractAfter reviewing a previously reported relational model of reversible computing, in which non-deterministic choice may represent provisional choice subject to revision by backtracking, we narrate our attempts to express preference within choice. We begin our investigations by recalling Nelson’s extensions to Dijkstra’s calculus, and considering his biased-choice operator as a model of preference. However, we find that this is too short-sighted for our purpose, and we outline the necessity of incorporating a notion of continuation. After considering how this might be achieved in a predicate-transformer approach, we adopt instead a prospective-value semantics that is easily extensible to probabilistic choice; here, we find a clue that helps us to obtain a first formulation of preference. Our formulation, however, takes us into a world of non-monotonic computations, and we are motivated to move on. We look for further inspiration within the execution structures of our reversible virtual machine which provides a construct that records all results of a backtracking search. We add a modified version that records results sequentially, and take its description as the basis for a “temporal order of continuations” semantics, to which we add implementor’s choice, which is now quite distinct from provisional choice. We give a refinement relation and prove the monotonicity of the new semantics and its consistency with respect to our previous prospective-values formalism.en
dc.language.isoenen
dc.publisherSpringeren
dc.relation.ispartofseriesLecture Notes in Computer Scienceen
dc.relation.ispartofseries6255en
dc.relation.urlhttp://www.springerlink.com/content/978-3-642-14807-1#section=756553&page=1en
dc.rightsAuthor can archive post-print (ie final draft post-refereeing). For full details see http://www.sherpa.ac.uk/romeo/ [Accessed 23/11/2010]en
dc.subjectbacktrackingen
dc.subjectcontinuationsen
dc.subjectreversible computingen
dc.subjectsemanticsen
dc.titlePreference and Non-deterministic Choiceen
dc.typeMeetings and Proceedingsen
dc.typeBook Chapteren
dc.contributor.departmentTeesside University. School of Computing.en
dc.title.bookTheoretical Aspects of Computing – ICTAC 2010en
dc.identifier.conference7th international colloquium, Natal, Rio Grande do Norte, Brazil, September 1-3, 2010en
ref.citationcount0 [Scopus, 23/11/2010]en
or.citation.harvardStoddart, W. J., Zeyda, F. and Dunne, S. E. (2010) 'Preference and Non-deterministic Choice', 7th international colloquium, Natal, Rio Grande do Norte, Brazil, September 1-3, 2010, in Cavalcanti, A. et. al. (eds) Theoretical Aspects of Computing – ICTAC 2010, Lecture Notes in Computer Science, 6255, pp.137-152.-
prism.startingPage137-
prism.endingPage152-
All Items in TeesRep are protected by copyright, with all rights reserved, unless otherwise indicated.