On constructor rewrite systems and the lambda calculus

DOI10.2168/LMCS-8(3:12)2012MaRDI QIDQ2904629zbMATH OpenOpenAlexFDO

Authors Ugo Dal Lago, Simone Martini

Publication date 15 August 2012

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2168/lmcs-8(3:12)2012

zbMATH Keywords

implicit computational complexitylambda calculusterm rewriting

Mathematics Subject Classification ID

Combinatory logic and lambda calculus (03B40) Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Functional programming and lambda calculus (68N18) Grammars and rewriting systems (68Q42)

Recommendations

• On Constructor Rewrite Systems and the Lambda-Calculus
• The λ-calculus with constructors: Syntax, confluence and separation
• A Lambda-Calculus with Constructors
• Semantics of typed lambda-calculus with constructors
• Implementing first-order rewriting with constructor systems
• Continuation models for the lambda calculus with constructors
• On the confluence of lambda-calculus with conditional rewriting
• A Polymorphic Type System for the Lambda-Calculus with Constructors
• Constructor equivalent term rewriting systems
• Consistency and Completeness of Rewriting in the Calculus of Constructions

Cited in

(15)

• On sharing, memoization, and polynomial time
• (In)efficiency and reasonable cost models
• A combination framework for complexity
• Enriching the lambda calculus with contexts: toward a theory of incremental program construction
• A Lambda-Calculus with Constructors
• A Polymorphic Type System for the Lambda-Calculus with Constructors
• On Constructor Rewrite Systems and the Lambda-Calculus
• The λ-calculus with constructors: Syntax, confluence and separation
• Linear pattern matching of compressed terms and polynomial rewriting
• Counting environments and closures
• A Fresh Look at the λ-Calculus
• Linear depth increase of lambda terms in leftmost-outermost rewrite sequences
• Exponentials as Substitutions and the Cost of Cut Elimination in Linear Logic
• Exponentials as substitutions and the cost of cut elimination in linear logic
• A characterization of basic feasible functionals through higher-order rewriting and tuple interpretations

This page was built for publication: On constructor rewrite systems and the lambda calculus

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2904629)