On the likelihood of normalization in combinatory logic.
Saved in:
| Title: | On the likelihood of normalization in combinatory logic. |
|---|---|
| Authors: | BENDKOWSKI, MACIEJ1 bendkowski@tcs.uj.edu.pl, GRYGIEL, KATARZYNA1 grygiel@tcs.uj.edu.pl, ZAIONC, MAREK1 zaionc@tcs.uj.edu.pl |
| Source: | Journal of Logic & Computation. Oct2017, Vol. 27 Issue 7, p2251-2269. 19p. |
| Subjects: | Combinatory logic, Likelihood ratio tests, Asymptotic normality, Lambda calculus, Mathematical notation |
| Abstract: | We present a quantitative basis-independent analysis of combinatory logic. Using a general argument regarding plane binary trees with labelled leaves, we generalize the results of David et al. (see [11]) and Bendkowski et al. (see [6]) to all Turing-complete combinator bases proving, inter alia, that asymptotically almost no combinator is strongly normalizing nor typeable. We exploit the structure of recently discovered normal-order reduction grammars (see [3]) showing that for each positive n, the set of SK-combinators reducing in n normal-order reduction steps has positive asymptotic density in the set of all combinators. Our approach is constructive, allowing us to systematically find new asymptotically significant fractions of the set of normalizing combinators. We show that the density of normalizing combinators cannot be less than 34%, improving the previously best lower bound of approximately 3% (see [6]). Finally, we present some super-computer experimental results, conjecturing that the density of the set of normalizing combinators is close to 85%. [ABSTRACT FROM AUTHOR] |
| Copyright of Journal of Logic & Computation is the property of Oxford University Press / USA and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 125778807 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: On the likelihood of normalization in combinatory logic. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22BENDKOWSKI%2C+MACIEJ%22">BENDKOWSKI, MACIEJ</searchLink><relatesTo>1</relatesTo><i> bendkowski@tcs.uj.edu.pl</i><br /><searchLink fieldCode="AR" term="%22GRYGIEL%2C+KATARZYNA%22">GRYGIEL, KATARZYNA</searchLink><relatesTo>1</relatesTo><i> grygiel@tcs.uj.edu.pl</i><br /><searchLink fieldCode="AR" term="%22ZAIONC%2C+MAREK%22">ZAIONC, MAREK</searchLink><relatesTo>1</relatesTo><i> zaionc@tcs.uj.edu.pl</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Journal+of+Logic+%26+Computation%22">Journal of Logic & Computation</searchLink>. Oct2017, Vol. 27 Issue 7, p2251-2269. 19p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Combinatory+logic%22">Combinatory logic</searchLink><br /><searchLink fieldCode="DE" term="%22Likelihood+ratio+tests%22">Likelihood ratio tests</searchLink><br /><searchLink fieldCode="DE" term="%22Asymptotic+normality%22">Asymptotic normality</searchLink><br /><searchLink fieldCode="DE" term="%22Lambda+calculus%22">Lambda calculus</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+notation%22">Mathematical notation</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: We present a quantitative basis-independent analysis of combinatory logic. Using a general argument regarding plane binary trees with labelled leaves, we generalize the results of David et al. (see [11]) and Bendkowski et al. (see [6]) to all Turing-complete combinator bases proving, inter alia, that asymptotically almost no combinator is strongly normalizing nor typeable. We exploit the structure of recently discovered normal-order reduction grammars (see [3]) showing that for each positive n, the set of SK-combinators reducing in n normal-order reduction steps has positive asymptotic density in the set of all combinators. Our approach is constructive, allowing us to systematically find new asymptotically significant fractions of the set of normalizing combinators. We show that the density of normalizing combinators cannot be less than 34%, improving the previously best lower bound of approximately 3% (see [6]). Finally, we present some super-computer experimental results, conjecturing that the density of the set of normalizing combinators is close to 85%. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Journal of Logic & Computation is the property of Oxford University Press / USA and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=125778807 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1093/logcom/exx005 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 19 StartPage: 2251 Subjects: – SubjectFull: Combinatory logic Type: general – SubjectFull: Likelihood ratio tests Type: general – SubjectFull: Asymptotic normality Type: general – SubjectFull: Lambda calculus Type: general – SubjectFull: Mathematical notation Type: general Titles: – TitleFull: On the likelihood of normalization in combinatory logic. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: BENDKOWSKI, MACIEJ – PersonEntity: Name: NameFull: GRYGIEL, KATARZYNA – PersonEntity: Name: NameFull: ZAIONC, MAREK IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 10 Text: Oct2017 Type: published Y: 2017 Identifiers: – Type: issn-print Value: 0955792X Numbering: – Type: volume Value: 27 – Type: issue Value: 7 Titles: – TitleFull: Journal of Logic & Computation Type: main |
| ResultId | 1 |
