On the complexity of alpha conversion

DOI10.2178/JSL/1203350781MaRDI QIDQ5444695zbMATH OpenOpenAlexFDO

Authors Richard Statman

Publication date 25 February 2008

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://projecteuclid.org/euclid.jsl/1203350781

zbMATH Keywords

alpha convertible combinators

Mathematics Subject Classification ID

Combinatory logic and lambda calculus (03B40) Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Alpha-conversion and typability
• Algorithms for extended alpha-equivalence and complexity
• NP-completeness of a combinator optimization problem
• Abstraction problems in combinatory logic: A compositive approach
• Effective reduction and conversion strategies for combinators

Cites work

• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Incidence matrices and interval graphs

Cited in

(5)

• Alpha-conversion and typability
• Algorithms for extended alpha-equivalence and complexity
• Varying alpha
• Foundations of Software Science and Computational Structures
• -avoidance

This page was built for publication: On the complexity of alpha conversion

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