Paper Info
Title
Declarative algorithms for generation, counting and random sampling of term algebras.
Abstract
From a declarative variant of Rémy's algorithm for uniform random generation of binary trees, we derive a generalization to term algebras of an arbitrary signature. With trees seen as sets of edges connecting vertices labeled with logic variables, we use Prolog's multiple-answer generation mechanism to derive a generic algorithm that counts terms of a given size, generates them all, or samples a random term given the signature of a term algebra. As applications, we implement generators for term algebras defining Motzkin trees, use all-term and random-term generation for mutual cross-testing and describe an extension mechanism that transforms a random sampler for Motzkin trees into one for closed lambda terms.
Year
DOI
Venue
2018
10.1145/3167132.3167262
SAC 2018: Symposium on Applied Computing Pau France April, 2018
Keywords
Field
DocType
declarative algorithms, combinatorial generation, random term generation, edge-based tree representations, term algebras, Motzkin trees, generation of random lambda terms
Term algebra,Vertex (geometry),Binary tree,Algorithm,Prolog,Sampling (statistics),Genetic algorithm,Mathematics,Lambda
Conference
ISBN
Citations 
PageRank 
978-1-4503-5191-1
1
0.35
References 
Authors
5
1
Name
Order
Citations
PageRank
Paul Tarau11529113.14