TY  - UNPD
A1  - Schmidt-Schauß, Manfred
A1  - Sabel, David
T1  - Applicative may- and should-simulation in the call-by-value
lambda calculus with amb
T2  - Technical report Frank / Johann-Wolfgang-Goethe-Universität, Fachbereich Informatik und Mathematik, Institut für Informatik ; 54
N2  - Motivated by the question whether sound and expressive applicative similarities for program calculi with should-convergence exist, this paper investigates expressive applicative similarities for the untyped call-by-value lambda-calculus extended with McCarthy's ambiguous choice operator amb. Soundness of the applicative similarities w.r.t. contextual equivalence based on may-and should-convergence is proved by adapting Howe's method to should-convergence. As usual for nondeterministic calculi, similarity is not complete w.r.t. contextual equivalence which requires a rather complex counter example as a witness. Also the call-by-value lambda-calculus with the weaker nondeterministic construct erratic choice is analyzed and sound applicative similarities are provided. This justifies the expectation that also for more expressive and call-by-need higher-order calculi there are sound and powerful similarities for should-convergence.
T3  - Technical report Frank / Johann-Wolfgang-Goethe-Universität, Fachbereich Informatik und Mathematik, Institut für Informatik - 54 
Y1  - 2014
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/33609
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30:3-336093
UR  - http://www.ki.informatik.uni-frankfurt.de/papers/frank/frank-54.pdf
SP  - 1
EP  - 19
PB  - Johann Wolfgang Goethe-Univ., Fachbereich Informatik und Mathematik, Inst. für Informatik, Research group for Artificial Intelligence and Software Technology
CY  - Frankfurt [am Main]
ER  -