Skip to Main content Skip to Navigation
Conference papers

The IO and OI hierarchies revisited

Abstract : We study languages of lambda-terms generated by IO and OI unsafe grammars. These languages can be used to model meaning representations in the formal semantics of natural languages following the tradition of Montague. Using techniques pertaining to the denotational semantics of the simply typed lambda-calculus, we show that the emptiness and membership problems for both types of grammars are decidable. In the course of the proof of the decidability results for OI, we identify a decidable variant of the lambda-definability problem, and prove a stronger form of Statman's finite completeness Theorem.
Complete list of metadata

Cited literature [35 references]  Display  Hide  Download
Contributor : Sylvain Salvati Connect in order to contact the contributor
Submitted on : Thursday, April 25, 2013 - 11:48:47 PM
Last modification on : Saturday, June 25, 2022 - 10:33:37 AM
Long-term archiving on: : Monday, April 3, 2017 - 11:53:19 PM


Files produced by the author(s)


  • HAL Id : hal-00818069, version 1



Gregory M. Kobele, Sylvain Salvati. The IO and OI hierarchies revisited. ICALP (2), Jul 2013, Riga, Latvia. ⟨hal-00818069⟩



Record views


Files downloads