Algorithms for Extended Alpha-Equivalence and Complexity

Schmidt-Schauß, Manfred; Rau, Conrad; Sabel, David

doi:10.4230/LIPIcs.RTA.2013.255

Document

Algorithms for Extended Alpha-Equivalence and Complexity

Authors Manfred Schmidt-Schauß, Conrad Rau, David Sabel

Part of: Volume: 24th International Conference on Rewriting Techniques and Applications (RTA 2013)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: International Conference on Rewriting Techniques and Applications (RTA)
License: Creative Commons Attribution 3.0 Unported license
Publication Date: 2013-06-24

PDF

File

PDF

LIPIcs.RTA.2013.255.pdf

Filesize: 0.52 MB
16 pages

Document Identifiers

DOI: 10.4230/LIPIcs.RTA.2013.255
URN: urn:nbn:de:0030-drops-40667

Subject Classification

Keywords

alpha-equivalence
higher-order calculi
deduction
pi-calculus

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

Abstract

Equality of expressions in lambda-calculi, higher-order programming languages, higher-order programming calculi and process calculi is defined as alpha-equivalence. Permutability of bindings in let-constructs and structural congruence axioms extend alpha-equivalence. We analyse these extended alpha-equivalences and show that there are calculi with polynomial time algorithms, that a multiple-binding "let" may make alpha-equivalence as hard as finding graph-isomorphisms, and that the replication operator in the pi-calculus may lead to an EXPSPACE-hard alpha-equivalence problem.

Cite As Get BibTex

Manfred Schmidt-Schauß, Conrad Rau, and David Sabel. Algorithms for Extended Alpha-Equivalence and Complexity. In 24th International Conference on Rewriting Techniques and Applications (RTA 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 21, pp. 255-270, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013) https://doi.org/10.4230/LIPIcs.RTA.2013.255

Author Details

Manfred Schmidt-Schauß

Conrad Rau

David Sabel

Any Issues?

Feedback on the Current Page

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail