×

zbMATH — the first resource for mathematics

Full abstraction for expressiveness: history, myths and facts. (English) Zbl 1361.68028
Summary: What does it mean that an encoding is fully abstract? What does it not mean? In this position paper, we want to help the reader to evaluate the real benefits of using such a notion when studying the expressiveness of programming languages. Several examples and counterexamples are given. In some cases, we work at a very abstract level; in other cases, we give concrete samples taken from the field of process calculi, where the theory of expressiveness has been mostly developed in the last years.

MSC:
68N15 Theory of programming languages
68N30 Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] DOI: 10.4204/EPTCS.89.7
[2] DOI: 10.1145/365230.365257 · Zbl 0149.12505
[3] DOI: 10.1007/BFb0057019
[4] DOI: 10.1145/114005.102808
[5] The {\(\pi\)}-Calculus: A Theory of Mobile Processes (2001)
[6] DOI: 10.1016/j.entcs.2007.11.004 · Zbl 1277.68189
[7] DOI: 10.1016/j.ic.2010.05.002 · Zbl 1209.68336
[8] DOI: 10.1007/s00446-010-0120-6 · Zbl 1231.68169
[9] The Essence of ALGOL pp 345– (1981)
[10] DOI: 10.1016/j.ic.2008.05.001 · Zbl 1169.68009
[11] DOI: 10.1145/362349.362364 · Zbl 0193.15101
[12] DOI: 10.1016/j.tcs.2009.11.011 · Zbl 1191.68436
[13] DOI: 10.1016/j.ic.2005.03.004 · Zbl 1101.68062
[14] DOI: 10.1016/0167-6423(91)90036-W · Zbl 0745.68033
[15] DOI: 10.1007/3-540-46432-8_19
[16] DOI: 10.1016/0304-3975(84)90113-0 · Zbl 0985.68518
[17] DOI: 10.1016/0304-3975(77)90044-5 · Zbl 0369.68006
[18] DOI: 10.1007/978-3-642-37036-6_18 · Zbl 1381.68215
[19] DOI: 10.1007/978-3-642-28729-9_14 · Zbl 1352.68190
[20] DOI: 10.1007/978-3-540-68679-8_29 · Zbl 1143.68470
[21] DOI: 10.1006/inco.1994.1004 · Zbl 0788.68014
[22] Computer Languages 1 pp 219– (1976)
[23] Nordic Journal of Computing 10 pp 70– (2003)
[24] DOI: 10.1016/j.entcs.2008.04.011 · Zbl 1279.68264
[25] DOI: 10.1016/j.tcs.2007.07.009 · Zbl 1143.68051
[26] DOI: 10.1017/S0960129503004043
[27] DOI: 10.1016/S0304-3975(97)00220-X · Zbl 0915.68059
[28] DOI: 10.1006/inco.2000.2868 · Zbl 1003.68080
[29] DOI: 10.1007/11817949_4 · Zbl 1151.68548
[30] DOI: 10.1016/S0304-3975(97)00223-5 · Zbl 0915.68009
[31] DOI: 10.1016/0167-6423(93)90004-9 · Zbl 0809.68049
[32] DOI: 10.1016/S0304-3975(99)00230-3 · Zbl 0954.68072
[33] DOI: 10.1007/3-540-55719-9_114
[34] Communicating and Mobile Systems: The {\(\pi\)}-Calculus (1999)
[35] Logic and Algebra of Specification (1993)
[36] Communication and Concurrency (1989) · Zbl 0683.68008
[37] DOI: 10.1017/S0960129504004323 · Zbl 1093.68026
[38] DOI: 10.1007/3-540-46432-8_16
[39] DOI: 10.1007/3-540-62034-6_64
[40] DOI: 10.1016/S1571-0661(04)00122-7
[41] Springer-Verlag Lecture Notes in Computer Science 119 pp 389– (1996)
[42] DOI: 10.1007/3-540-57208-2_6
[43] DOI: 10.1007/BFb0039066
[44] Introduction to Metamathematics (1952) · Zbl 0047.00703
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.