1,720,989 research outputs found
An Algebraic View of the Böhm-out Technique
No full textAbstractUsing an algebraic representation of closed β-normal forms in λ-calculus, the Böhm's theorem is rephrased as an equality predicate between elements of a term algebra. The presented algebraic interpretation gives new insight into the Böhm-out technique and allows for original applications of the method
Abstraction problems in Combinatory Logic: a compositive approach
No full textAbstractThe problem of the translation of λ-terms into combinators (bracket abstraction) is of great importance for the implementation of functional languages. In the literature there exist a lot of algorithms concerning this topic, each of which is based on a particular choice of a combinatory basis, its cardinality, and an abstraction technique. The algorithm presented here originated from a modification of the definition of abstraction given by Curry in 1930, and has the following interesting properties: 1.(i) it employs a potentially infinite basis of combinators, each of which depends on at most two parameters and is, therefore, directly implementable;2.(ii) it gives compact code, introducing a number of basic combinators which is proportional to the size of the expression to be abstracted and invariant for one- and multi-sweep abstraction techniques;3.(iii) it gives the result in the form RIM1… Mn, where R is a regular combinator expressed as a composition of basic combinators, I is the identity combinator, and M1,…, Mn are the constant terms appearing into the expression subjected to the translation process.It appears that a slight modification of the algorithm yields a combinatory equivalent of Hughes' supercombinators
Characterizing X-separability and one side invertibility in lambda-calculus
No full textComputer Society of the IEE
nauty & Traces version 2.5r9
No full textnauty and Traces are programs for computing automorphism groups of graphs and digraphs. They can also produce a canonical label. They are written in a portable subset of C, and run on a considerable number of different systems.
There is a small suite of programs called gtools included in the package. For example, geng can generate non-isomorphic graphs very quickly. There are also generators for bipartite graphs, digraphs, and multigraphs, and programs for manipulating files of graphs in a compact format
Isomorphism test for digraphs with weighted edges
Full text linkColour refinement is at the heart of all the most efficient graph isomorphism software packages. In this paper we present a method for extending the applicability of refinement algorithms to directed graphs with weighted edges. We use Traces as a reference software, but the proposed solution is easily transferrable to any other refinement-based graph isomorphism tool in the literature. We substantiate the claim that the performances of the original algorithm remain substantially unchanged by showing experiments for some classes of benchmark graphs
- …
