Expressibility in the Lambda Calculus with mu We address a problem connected to the unfolding semantics of functional programming languages: give a useful characterization of those infinite lambdaterms that are lambda_letrecexpressible in the sense that they arise as infinite unfoldings of terms in lambda_letrec, the lambdacalculus with letrec. We provide two characterizations, using concepts we introduce for infinite lambdaterms: regularity, strong regularity, and bindingcapturing chains. It turns out that lambda_letrecexpressible infinite lambdaterms form a proper subclass of the regular infinite lambdaterms. In this paper we establish these characterizations only for expressibility in lambda_mu, the lambdacalculus with explicit murecursion. We show that for all infinite lambdaterms T the following are equivalent: (i): T is lambda_muexpressible; (ii): T is strongly regular; (iii): T is regular, and it only has finite bindingcapturing chains.  :123,define regularity and strong regularity for infinite lambdaterms as two different generalizations of regularity for infinite firstorder terms: as the existence of only finitely many subterms that are defined as the reducts of two rewrite relations for decomposing lambdaterms. These rewrite relations act on infinite lambdaterms furnished with a marked prefix of abstractions for collecting decomposed lambdaabstractions and keeping the terms closed under decomposition. They differ in how vacuous abstractions in the prefix are removed.  :199,report accompanies the article with the same title for the proceedings of the conference RTA 2013, and mainly differs from that by providing the proof of the characterization of lambda_muexpressibility with bindingcapturing chains.

A rewriting calculus for cyclic higherorder term graphs Introduced at the end of the nineties, the Rewriting Calculus (rhocalculus, for short) is a simple calculus that fully integrates termrewriting and lambdacalculus. The rewrite rules, acting as elaborated abstractions, their application and the obtained structured results are first class objects of the calculus. The evaluation mechanism, generalizing betareduction, strongly relies on term matching in various theories. In this paper we propose an extension of the rhocalculus, handling graph like structures rather than simple terms. The transformations are performed by explicit application of rewrite rules as first class entities. The possibility of expressing sharing and cycles allows one to represent and compute over regular infinite entities. The calculus over terms is naturally generalized by using unification constraints in addition to the standard rhocalculus matching constraints. This therefore provides us with the basics for a natural extension of an explicit substitution calculus to term graphs. Several examples illustrating the introduced concepts are given.