Simple view
Full metadata view
Authors
Statistics
Unary profile of lambda terms with restricted De Bruijn indices
profile of lambda terms
singularity analysis
lambda terms with restrictions
In this paper we present an average-case analysis of closed lambda terms with restricted values of De Bruijn indices in the model where each occurrence of a variable contributes one to the size. Given a fixed integer k, a lambda term in which all De Bruijn indices are bounded by k has the following shape: It starts with k De Bruijn levels, forming the so-called hat of the term, to which some number of k-colored Motzkin trees are attached. By means of analytic combinatorics, we show that the size of this hat is constant on average and that the average number of De Bruijn levels of k-colored Motzkin trees of size n is asymptotically Θ(√ n). Combining these two facts, we conclude that the maximal non-empty De Bruijn level in a lambda term with restrictions on De Bruijn indices and of size n is, on average, also of order √ n. On this basis, we provide the average unary profile of such lambda terms.
dc.abstract.en | In this paper we present an average-case analysis of closed lambda terms with restricted values of De Bruijn indices in the model where each occurrence of a variable contributes one to the size. Given a fixed integer k, a lambda term in which all De Bruijn indices are bounded by k has the following shape: It starts with k De Bruijn levels, forming the so-called hat of the term, to which some number of k-colored Motzkin trees are attached. By means of analytic combinatorics, we show that the size of this hat is constant on average and that the average number of De Bruijn levels of k-colored Motzkin trees of size n is asymptotically Θ(√ n). Combining these two facts, we conclude that the maximal non-empty De Bruijn level in a lambda term with restrictions on De Bruijn indices and of size n is, on average, also of order √ n. On this basis, we provide the average unary profile of such lambda terms. | pl |
dc.affiliation | Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej | pl |
dc.contributor.author | Grygiel, Katarzyna - 136103 | pl |
dc.contributor.author | Larcher, Isabella | pl |
dc.date.accession | 2021-02-15 | pl |
dc.date.accessioned | 2021-04-26T13:20:16Z | |
dc.date.available | 2021-04-26T13:20:16Z | |
dc.date.issued | 2021 | pl |
dc.date.openaccess | 0 | |
dc.description.accesstime | w momencie opublikowania | |
dc.description.number | 3 | pl |
dc.description.version | ostateczna wersja wydawcy | |
dc.description.volume | 22 | pl |
dc.identifier.articleid | hal-02313735v3 | pl |
dc.identifier.issn | 1365-8050 | |
dc.identifier.project | SFB F50-03 | pl |
dc.identifier.project | ROD UJ / OP | pl |
dc.identifier.uri | https://ruj.uj.edu.pl/xmlui/handle/item/269815 | |
dc.identifier.weblink | https://hal.archives-ouvertes.fr/hal-02313735v3 | pl |
dc.language | eng | pl |
dc.language.container | eng | pl |
dc.rights | Udzielam licencji. Uznanie autorstwa 4.0 Międzynarodowa | * |
dc.rights.licence | CC-BY | |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/legalcode.pl | * |
dc.share.type | otwarte czasopismo | |
dc.subject.en | profile of lambda terms | pl |
dc.subject.en | singularity analysis | pl |
dc.subject.en | lambda terms with restrictions | pl |
dc.subtype | Article | pl |
dc.title | Unary profile of lambda terms with restricted De Bruijn indices | pl |
dc.title.journal | Discrete Mathematics and Theoretical Computer Science | |
dc.title.volume | (CLA'19) | pl |
dc.type | JournalArticle | pl |
dspace.entity.type | Publication |
* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.
Views
15
Views per month
Views per city
Downloads
Open Access