Enumeration of generalized BCI lambda-terms (Q396960): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
| (5 intermediate revisions by 4 users not shown) | |||
| Property / author | |||
| Property / author: Daniéle Gardy / rank | |||
| Property / author | |||
| Property / author: Daniéle Gardy / rank | |||
Normal rank | |||
| Property / review text | |||
Summary: We investigate the asymptotic number of elements of size \(n\) in a particular class of closed lambda-terms (so-called \(\mathrm{BCI}(p)\)-terms) which are related to axiom systems of combinatory logic. By deriving a differential equation for the generating function of the counting sequence we obtain a recurrence relation which can be solved asymptotically. We derive differential equations for the generating functions of the counting sequences of other more general classes of terms as well: the class of \(\mathrm{BCK}(p)\)-terms and that of closed lambda-terms. Using elementary arguments we obtain upper and lower estimates for the number of closed lambda-terms of size \(n\). Moreover, a recurrence relation is derived which allows an efficient computation of the counting sequence. \(\mathrm{BCK}(p)\)-terms are discussed briefly. | |||
| Property / review text: Summary: We investigate the asymptotic number of elements of size \(n\) in a particular class of closed lambda-terms (so-called \(\mathrm{BCI}(p)\)-terms) which are related to axiom systems of combinatory logic. By deriving a differential equation for the generating function of the counting sequence we obtain a recurrence relation which can be solved asymptotically. We derive differential equations for the generating functions of the counting sequences of other more general classes of terms as well: the class of \(\mathrm{BCK}(p)\)-terms and that of closed lambda-terms. Using elementary arguments we obtain upper and lower estimates for the number of closed lambda-terms of size \(n\). Moreover, a recurrence relation is derived which allows an efficient computation of the counting sequence. \(\mathrm{BCK}(p)\)-terms are discussed briefly. / rank | |||
Normal rank | |||
| Property / Mathematics Subject Classification ID | |||
| Property / Mathematics Subject Classification ID: 05A16 / rank | |||
Normal rank | |||
| Property / Mathematics Subject Classification ID | |||
| Property / Mathematics Subject Classification ID: 03B40 / rank | |||
Normal rank | |||
| Property / zbMATH DE Number | |||
| Property / zbMATH DE Number: 6330361 / rank | |||
Normal rank | |||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
| Property / arXiv ID | |||
| Property / arXiv ID: 1305.0640 / rank | |||
Normal rank | |||
| links / mardi / name | links / mardi / name | ||
Latest revision as of 14:22, 18 April 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Enumeration of generalized BCI lambda-terms |
scientific article |
Statements
Enumeration of generalized BCI lambda-terms (English)
0 references
14 August 2014
0 references
Summary: We investigate the asymptotic number of elements of size \(n\) in a particular class of closed lambda-terms (so-called \(\mathrm{BCI}(p)\)-terms) which are related to axiom systems of combinatory logic. By deriving a differential equation for the generating function of the counting sequence we obtain a recurrence relation which can be solved asymptotically. We derive differential equations for the generating functions of the counting sequences of other more general classes of terms as well: the class of \(\mathrm{BCK}(p)\)-terms and that of closed lambda-terms. Using elementary arguments we obtain upper and lower estimates for the number of closed lambda-terms of size \(n\). Moreover, a recurrence relation is derived which allows an efficient computation of the counting sequence. \(\mathrm{BCK}(p)\)-terms are discussed briefly.
0 references
