{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:35:59Z","timestamp":1753889759229,"version":"3.41.2"},"reference-count":1,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2012,8,14]],"date-time":"2012-08-14T00:00:00Z","timestamp":1344902400000},"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>We prove that orthogonal constructor term rewrite systems and lambda-calculus\nwith weak (i.e., no reduction is allowed under the scope of a\nlambda-abstraction) call-by-value reduction can simulate each other with a\nlinear overhead. In particular, weak call-by- value beta-reduction can be\nsimulated by an orthogonal constructor term rewrite system in the same number\nof reduction steps. Conversely, each reduction in a term rewrite system can be\nsimulated by a constant number of beta-reduction steps. This is relevant to\nimplicit computational complexity, because the number of beta steps to normal\nform is polynomially related to the actual cost (that is, as performed on a\nTuring machine) of normalization, under weak call-by-value reduction.\nOrthogonal constructor term rewrite systems and lambda-calculus are thus both\npolynomially related to Turing machines, taking as notion of cost their natural\nparameters.<\/jats:p>","DOI":"10.2168\/lmcs-8(3:12)2012","type":"journal-article","created":{"date-parts":[[2013,11,29]],"date-time":"2013-11-29T08:17:46Z","timestamp":1385713066000},"source":"Crossref","is-referenced-by-count":6,"title":["On Constructor Rewrite Systems and the Lambda Calculus"],"prefix":"10.46298","volume":"Volume 8, Issue 3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9200-070X","authenticated-orcid":false,"given":"Ugo Dal","family":"Lago","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9834-1940","authenticated-orcid":false,"given":"Simone","family":"Martini","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2012,8,14]]},"reference":[{"key":"402:not-found"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/1213\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/1213\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:05:59Z","timestamp":1681243559000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/1213"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8,14]]},"references-count":1,"URL":"https:\/\/doi.org\/10.2168\/lmcs-8(3:12)2012","relation":{"is-same-as":[{"id-type":"arxiv","id":"1208.0515","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1208.0515","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2012,8,14]]},"article-number":"1213"}}