Unary profile of lambda terms with restricted De Bruijn indices

2021
journal article
article
dc.abstract.enIn 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.affiliationWydział Matematyki i Informatyki : Instytut Informatyki Analitycznejpl
dc.contributor.authorGrygiel, Katarzyna - 136103 pl
dc.contributor.authorLarcher, Isabellapl
dc.date.accession2021-02-15pl
dc.date.accessioned2021-04-26T13:20:16Z
dc.date.available2021-04-26T13:20:16Z
dc.date.issued2021pl
dc.date.openaccess0
dc.description.accesstimew momencie opublikowania
dc.description.number3pl
dc.description.versionostateczna wersja wydawcy
dc.description.volume22pl
dc.identifier.articleidhal-02313735v3pl
dc.identifier.eissn1365-8050pl
dc.identifier.issn1462-7264pl
dc.identifier.projectSFB F50-03pl
dc.identifier.projectROD UJ / OPpl
dc.identifier.urihttps://ruj.uj.edu.pl/xmlui/handle/item/269815
dc.identifier.weblinkhttps://hal.archives-ouvertes.fr/hal-02313735v3pl
dc.languageengpl
dc.language.containerengpl
dc.rightsUdzielam licencji. Uznanie autorstwa 4.0 Międzynarodowa*
dc.rights.licenceCC-BY
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/legalcode.pl*
dc.share.typeotwarte czasopismo
dc.subject.enprofile of lambda termspl
dc.subject.ensingularity analysispl
dc.subject.enlambda terms with restrictionspl
dc.subtypeArticlepl
dc.titleUnary profile of lambda terms with restricted De Bruijn indicespl
dc.title.journalDiscrete Mathematics and Theoretical Computer Sciencepl
dc.title.volume(CLA'19)pl
dc.typeJournalArticlepl
dspace.entity.typePublication
dc.abstract.enpl
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.affiliationpl
Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej
dc.contributor.authorpl
Grygiel, Katarzyna - 136103
dc.contributor.authorpl
Larcher, Isabella
dc.date.accessionpl
2021-02-15
dc.date.accessioned
2021-04-26T13:20:16Z
dc.date.available
2021-04-26T13:20:16Z
dc.date.issuedpl
2021
dc.date.openaccess
0
dc.description.accesstime
w momencie opublikowania
dc.description.numberpl
3
dc.description.version
ostateczna wersja wydawcy
dc.description.volumepl
22
dc.identifier.articleidpl
hal-02313735v3
dc.identifier.eissnpl
1365-8050
dc.identifier.issnpl
1462-7264
dc.identifier.projectpl
SFB F50-03
dc.identifier.projectpl
ROD UJ / OP
dc.identifier.uri
https://ruj.uj.edu.pl/xmlui/handle/item/269815
dc.identifier.weblinkpl
https://hal.archives-ouvertes.fr/hal-02313735v3
dc.languagepl
eng
dc.language.containerpl
eng
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.enpl
profile of lambda terms
dc.subject.enpl
singularity analysis
dc.subject.enpl
lambda terms with restrictions
dc.subtypepl
Article
dc.titlepl
Unary profile of lambda terms with restricted De Bruijn indices
dc.title.journalpl
Discrete Mathematics and Theoretical Computer Science
dc.title.volumepl
(CLA'19)
dc.typepl
JournalArticle
dspace.entity.type
Publication

* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.

Views
11
Views per month
Views per city
Wroclaw
2
Dublin
1
Downloads
grygiel_unary_profile_of_lambda_terms_with_restricted_2021.pdf
4