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 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.
| Author: | Manfred Schmidt-Schauß, Elena Machkasova, David Sabel |
|---|---|
| URN: | urn:nbn:de:hebis:30-77868 |
| 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 |
| Date of Publication (online): | 22.06.2010 |
| Year of first Publication: | 2009 |
| Publishing Institution: | Univ.-Bibliothek Frankfurt am Main |
| Tag: | Kontextuelle Gleichheit contextual equivalence; non-determinism; semantics |
| SWD-Keyword: | Formale Semantik; Lambda-Kalkül; Nichtdeterminismus |
| HeBIS PPN: | 224526219 |
| Institutes: | Informatik |
| Dewey Decimal Classification: | 004 Datenverarbeitung; Informatik |
| Sammlungen: | Universitätspublikationen |
| Licence (German): |  Veröffentlichungsvertrag für Publikationen ohne Print on Demand |
