Counterexamples to simulation in non-deterministic call-by-need lambda-calculi with letrec

This note shows that in non-deterministic extended lambda calculi with letrec, the tool of applicative (bi)simulation is in general not usable for contextual equivalence, by giving a counterexample adapted from data flow
This note shows that in non-deterministic extended lambda calculi with letrec, the tool of applicative (bi)simulation is in general not usable for contextual equivalence, by giving a counterexample adapted from data flow analysis. It also shown that there is a flaw in a lemma and a theorem concerning finite simulation in a conference paper by the first two authors.
show moreshow less

Download full text files

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

    Share in Twitter Search Google Scholar
Metadaten
Author:Manfred Schmidt-Schauß, Elena Machkasova, David Sabel
URN:urn:nbn:de:hebis:30-77868
URL:http://www.ki.informatik.uni-frankfurt.de/papers/schauss/simcounter-IB38.pdf
Parent Title (English):Technical report Frank / Johann-Wolfgang-Goethe-Universität, Fachbereich Informatik und Mathematik, Institut für Informatik ; 38
Series (Serial Number):Technical report Frank / Johann-Wolfgang-Goethe-Universität, Fachbereich Informatik und Mathematik, Institut für Informatik (38)
Publisher:Johann Wolfgang Goethe-Univ., Fachbereich Informatik und Mathematik, Inst. für Informatik, Research group for Artificial Intelligence and Software Technology
Place of publication:Frankfurt [am Main]
Document Type:Working Paper
Language:English
Year of Completion:2009
Year of first Publication:2009
Publishing Institution:Univ.-Bibliothek Frankfurt am Main
Release Date:2010/06/22
Tag:Kontextuelle Gleichheit
contextual equivalence; non-determinism; semantics
SWD-Keyword:Formale Semantik; Lambda-Kalkül; Nichtdeterminismus
Pagenumber:10
First Page:1
Last Page:10
HeBIS PPN:224526219
Institutes:Informatik
Dewey Decimal Classification:004 Datenverarbeitung; Informatik
Sammlungen:Universitätspublikationen
Licence (German):License Logo Veröffentlichungsvertrag für Publikationen

$Rev: 11761 $