article

Stochastic λ-calculi: An extended abstract

Author:

Dana S. ScottAuthors Info & Claims

Journal of Applied Logic, Volume 12, Issue 3

Pages 369 - 376

https://doi.org/10.1016/j.jal.2014.03.003

Published: 01 September 2014 Publication History

Abstract

It is shown how the operators in the ''graph model'' for @l-calculus (which can function as a programming language for Recursive Function Theory) can be expanded to allow for ''random combinators''. The result then is a model for a new language for random algorithms.

References

[1]

http://www.cs.tulane.edu/~mwm/Michael_Misloves_Home_Page/Research.html

Google Scholar

[2]

Cardone, F. and Hindley, J.R., Lambda-calculus and combinators in the 20th century. In: Gabbay, Dov M., Woods, John (Eds.), Handbook of the History of Logic, vol. 5. North-Holland/Elsevier Science. pp. 723-818.

Google Scholar

[3]

de'Liguoro, U. and Piperno, A., Nondeterministic extensions of untyped λ-calculus. Inf. Comput. v122. 149-177.

Digital Library

Google Scholar

[4]

Friedberg, Richard M. and Rogers Jr., Hartley, Reducibility and completeness for sets of integers. Math. Log. Q. v5. 117-125.

Google Scholar

[5]

Gierz, G., Hofmann, K.H., Keimel, K., Lawson, J.D., Mislove, M. and Scott, D.S., Continuous Lattices and Domains. 2003. Encyclopedia of Mathematics and Its Applications, 2003.Cambridge University Press.

Google Scholar

[6]

Lago, Ugo Dal and Zorzi, Margherita, Probabilistic operational semantics for the lambda calculus. RAIRO Theor. Inform. Appl. v46. 413-450.

Crossref

Google Scholar

[7]

Myhill, John and Shepherdson, John C., Effective operations on partial recursive functions. Z. Math. Log. Grundl. Math. v1. 310-317.

Google Scholar

[8]

Plotkin, Gordon D., Set-theoretical and other elementary models of the λ-calculus. Theor. Comput. Sci. v121. 351-409.

Digital Library

Google Scholar

[9]

Rogers Jr., Hartley, Theory of Recursive Functions and Effective Computability. 1967. McGraw-Hill.

Crossref

Google Scholar

[10]

Scott, Dana S., Data types as lattices. SIAM J. Comput. v5. 522-587.

Google Scholar

Cited By

View all

Di Gianantonio PEdalat ASobocinski PLago UEsparza J(2024)A Cartesian Closed Category for Random VariablesProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662126(1-14)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662126
de Amorim PKozen DMardare RPanangaden PRoberts MGorla D(2021)Universal semantics for the stochastic λ-calculusProceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science10.1109/LICS52264.2021.9470747(1-12)Online publication date: 29-Jun-2021
https://dl.acm.org/doi/10.1109/LICS52264.2021.9470747
Faggian CRocca SBouyer P(2019)Lambda calculus and probabilistic computationProceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science10.5555/3470152.3470186(1-13)Online publication date: 24-Jun-2019
https://dl.acm.org/doi/10.5555/3470152.3470186
Show More Cited By

Stochastic λ-calculi: An extended abstract
1. Computing methodologies
  1. Artificial intelligence
    1. Knowledge representation and reasoning
2. Theory of computation
  1. Models of computation

Recommendations

On Bisimilarity in Lambda Calculi with Continuous Probabilistic Choice
Abstract
Applicative bisimiliarity is a coinductively-defined program equivalence in which programs are tested as argument-passing processes. Starting with the seminal work by Abramsky, applicative bisimiliarity has been proved to be a powerful technique ...
On Probabilistic Applicative Bisimulation and Call-by-Value λ-Calculi
Proceedings of the 23rd European Symposium on Programming Languages and Systems - Volume 8410

Probabilistic applicative bisimulation is a recently introduced coinductive methodology for program equivalence in a probabilistic, higher-order, setting. In this paper, the technique is applied to a typed, call-by-value, lambda-calculus. Surprisingly, ...
Infinitary Lambda Calculi from a Linear Perspective
LICS '16: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science

We introduce a linear infinitary λ-calculus, called ℓΛ∞, in which two exponential modalities are available, the first one being the usual, finitary one, the other being the only construct interpreted coinductively. The obtained calculus embeds the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of Applied Logic Volume 12, Issue 3

September, 2014

148 pages

ISSN:1570-8683

Issue’s Table of Contents

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 September 2014

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Di Gianantonio PEdalat ASobocinski PLago UEsparza J(2024)A Cartesian Closed Category for Random VariablesProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662126(1-14)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662126
de Amorim PKozen DMardare RPanangaden PRoberts MGorla D(2021)Universal semantics for the stochastic λ-calculusProceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science10.1109/LICS52264.2021.9470747(1-12)Online publication date: 29-Jun-2021
https://dl.acm.org/doi/10.1109/LICS52264.2021.9470747
Faggian CRocca SBouyer P(2019)Lambda calculus and probabilistic computationProceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science10.5555/3470152.3470186(1-13)Online publication date: 24-Jun-2019
https://dl.acm.org/doi/10.5555/3470152.3470186
Bacci GFurber RKozen DMardare RPanangaden PScott D(2018)Boolean-Valued Semantics for the Stochastic λ-CalculusProceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3209108.3209175(669-678)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.1145/3209108.3209175
Ehrhard TPagani MTasson C(2018)Full Abstraction for Probabilistic PCFJournal of the ACM10.1145/316454065:4(1-44)Online publication date: 26-Apr-2018
https://dl.acm.org/doi/10.1145/3164540
Heunen CKammar OStaton SYang HAceto LIngólfsdóttir A(2017)A convenient category for higher-order probability theoryProceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science10.5555/3329995.3330072(1-12)Online publication date: 20-Jun-2017
https://dl.acm.org/doi/10.5555/3329995.3330072
Coquand TMannaa BRuch FAceto LIngólfsdóttir A(2017)Stack semantics of type theoryProceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science10.5555/3329995.3330065(1-11)Online publication date: 20-Jun-2017
https://dl.acm.org/doi/10.5555/3329995.3330065
Jansen NKaminski BKatoen JOlmedo FGretz FMcIver A(2015)Conditioning in Probabilistic ProgrammingElectronic Notes in Theoretical Computer Science (ENTCS)10.1016/j.entcs.2015.12.013319:C(199-216)Online publication date: 21-Dec-2015
https://dl.acm.org/doi/10.1016/j.entcs.2015.12.013

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Recommendations

On Bisimilarity in Lambda Calculi with Continuous Probabilistic Choice

On Probabilistic Applicative Bisimulation and Call-by-Value λ-Calculi

Infinitary Lambda Calculi from a Linear Perspective

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations