×

The better bubbling lemma. (English) Zbl 1277.03016

Jouannaud, Jean-Pierre (ed.) et al., Proceedings of the second international workshop on developments in computational models (DCM 2006), Venice, Italy, July 16, 2006. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 171, No. 3, 77-84 (2007).
Summary: BCD [H. Barendregt et al., J. Symb. Log. 48, 931–940 (1983; Zbl 0545.03004)] relies for its modeling of \(\lambda\) calculus in intersection type filters on a key theorem – BL (for the bubbling lemma, following someone). This lemma has been extended to BBL (the Better Bubbling Lemma) in [G. Castagna and A. Frisch, Lect. Notes Comput. Sci. 3580, 30–34 (2005; Zbl 1082.68581); M. Dezani-Ciancaglini et al., Electron. Notes Theor. Comput. Sci. 70, No. 1, 88–105 (2003; Zbl 1270.03043)] to encompass Boolean structure, including specifically union types. There are resonances, explored in [Dezani-Ciancaglini et al., loc. cit.; M. Dezani-Ciancaglini et al., Notre Dame J. Formal Logic 43, No. 3, 129–145 (2002; Zbl 1042.03019)], between intersection and union type theories and the already existing minimal positive relevant logic B+ of [R. Routley and the author, J. Philos. Log. 1, 192–208 (1972; Zbl 0317.02019)]. (Indeed [K. Pal and the author, Australas. J. Log. 3, 14–32 (2005; Zbl 1073.03011)] applies BL and BBL to get further results linking combinators to relevant theories and propositions.) On these resonances the filters of algebra become the theories of logic. The semantics of [the author et al., Tributes 3, 59–84 (2005; Zbl 1245.03028)] yields here a new and short proof of BBL, which takes account of full Boolean structure by encompassing not only B+ but also its conservative Boolean extension CB [Routley and the author, loc. cit.; the author et al., loc. cit.]
For the entire collection see [Zbl 1273.68035].

MSC:

03B47 Substructural logics (including relevance, entailment, linear logic, Lambek calculus, BCK and BCI logics)
Full Text: DOI

References:

[1] Barendregt, Henk; Coppo, Mario; Dezani-Ciancaglini, Mariangiola, A filter lambda model and the completeness of type assignment, JSL, 48, 931-940 (1983) · Zbl 0545.03004
[2] Castagna, Giuseppe, and Alain Frisch. A gentle introduction to semantic subtyping; Castagna, Giuseppe, and Alain Frisch. A gentle introduction to semantic subtyping · Zbl 1082.68581
[3] Curry, Haskell B., Foundations of Mathematical Logic (1963), McGraw-Hill: McGraw-Hill N.Y. · Zbl 0108.00104
[4] Dezani-Ciancaglini, M.; Frisch, A.; Giovannetti, E.; Motohama, Y., The Relevance of Semantic Subtyping, Electronic Notes in Theoretical Computer Science, 70, 1, 15 (2002) · Zbl 1270.03043
[5] Dezani-Ciancaglini, M.; Meyer, R. K.; Motohama, Y., The semantics of entailment omega, NDJFL, 43, 129-145 (2002) · Zbl 1042.03019
[6] Frisch, Alain; Castagna, Giuseppe; Benzaken, Véronique, Semantic subtyping, (LICS02 (2002), IEEE Computer Society Press), 137-146 · Zbl 1325.68136
[7] Meyer, Robert K., Types and the Boolean system CB+ (1995)
[8] Meyer, Robert K.; Motohama, Yoko; Bono, Viviana, Truth translations of relevant logics, (Brown, B.; Lepage, F., Truth and Probability: Essays in Honour of Hugues Leblanc (2005), College Publications: College Publications King’s College, London), 59-84 · Zbl 1245.03028
[9] Pal, Koushik; Meyer, Robert K., Basic relevant theories for combinators at levels I and II, AJL, 3 (2005), 19 pages · Zbl 1073.03011
[10] Routley, Richard; Meyer, Robert K., The semantics of entailment III, JPL, 1, 192-208 (1972) · Zbl 0317.02019
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.