{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:35:38Z","timestamp":1753889738441,"version":"3.41.2"},"reference-count":1,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2015,3,16]],"date-time":"2015-03-16T00:00:00Z","timestamp":1426464000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>This paper shows equivalence of several versions of applicative similarity\nand contextual approximation, and hence also of applicative bisimilarity and\ncontextual equivalence, in LR, the deterministic call-by-need lambda calculus\nwith letrec extended by data constructors, case-expressions and Haskell's\nseq-operator. LR models an untyped version of the core language of Haskell. The\nuse of bisimilarities simplifies equivalence proofs in calculi and opens a way\nfor more convenient correctness proofs for program transformations. The proof\nis by a fully abstract and surjective transfer into a call-by-name calculus,\nwhich is an extension of Abramsky's lazy lambda calculus. In the latter\ncalculus equivalence of our similarities and contextual approximation can be\nshown by Howe's method. Similarity is transferred back to LR on the basis of an\ninductively defined similarity. The translation from the call-by-need letrec\ncalculus into the extended call-by-name lambda calculus is the composition of\ntwo translations. The first translation replaces the call-by-need strategy by a\ncall-by-name strategy and its correctness is shown by exploiting infinite trees\nwhich emerge by unfolding the letrec expressions. The second translation\nencodes letrec-expressions by using multi-fixpoint combinators and its\ncorrectness is shown syntactically by comparing reductions of both calculi. A\nfurther result of this paper is an isomorphism between the mentioned calculi,\nwhich is also an identity on letrec-free expressions.<\/jats:p>","DOI":"10.2168\/lmcs-11(1:7)2015","type":"journal-article","created":{"date-parts":[[2015,5,18]],"date-time":"2015-05-18T07:33:27Z","timestamp":1431934407000},"source":"Crossref","is-referenced-by-count":4,"title":["Simulation in the Call-by-Need Lambda-Calculus with Letrec, Case, Constructors, and Seq"],"prefix":"10.46298","volume":"Volume 11, Issue 1","author":[{"given":"Manfred","family":"Schmidt-Schau\u00df","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5109-3273","authenticated-orcid":false,"given":"David","family":"Sabel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elena","family":"Machkasova","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2015,3,16]]},"reference":[{"key":"692:not-found"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/930\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/930\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T19:59:17Z","timestamp":1681243157000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/930"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,16]]},"references-count":1,"URL":"https:\/\/doi.org\/10.2168\/lmcs-11(1:7)2015","relation":{"is-same-as":[{"id-type":"arxiv","id":"1502.03216","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1502.03216","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2015,3,16]]},"article-number":"930"}}