Abstrakt. Vi bevisar att ortogonala konstruktörer term skriva om system och λ-kalculus med svag (dvs ingen minskning är tillåten inom ramen för en λ-abstraktion) call-by-värde minskning kan simulera varandra med en linjär overhead. I synnerhet, svaga call-by value beta-minskning kan simuleras av en ortogonal konstruktör term skriva om systemet i samma antal minskning steg. Omvänt kan varje minskning i en term skriva om systemet simuleras av ett konstant antal beta-minskning steg. Detta är relevant för implicit beräkning komplexitet, eftersom antalet beta steg till normal form är polynomiskt relaterad till den faktiska kostnaden (dvs., som utförs på en Turing maskin) av normalisering, under svag call-by-värde minskning. Ortogonal konstruktör term skriva om system och λ-kalculus är alltså båda polynomiskt relaterade till Turing maskiner, tar som begrepp av kostnad deras naturliga parametrar.
I synnerhet, följande fakta håller frågan öppen för närvarande: antalet delade beta-minskning steg i ett helt lata system är polynomiskt relaterade till den faktiska kostnaden för att utföra minskningen på en Turing maskin (enkel förlängning av REF ), men detta håller inte med optimal delning [AM98].
On Constructor Rewrite Systems and the Lambda Calculus
{'venue': 'Logical Methods in Computer Science, Volume 8, Issue 3 (August 14, 2012) lmcs:1213', 'journal': None, 'mag_field_of_study': ['Computer Science']}