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.
Type de document :
Communication dans un congrès
ICALP (2), Jul 2013, Riga, Latvia. 2013
Liste complète des métadonnées


https://hal.inria.fr/hal-00818069
Contributeur : Sylvain Salvati <>
Soumis le : jeudi 25 avril 2013 - 23:48:47
Dernière modification le : jeudi 10 septembre 2015 - 01:08:56
Document(s) archivé(s) le : lundi 3 avril 2017 - 23:53:19

Fichier

io_and_oi_revisited.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00818069, version 1

Collections

Citation

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

Partager

Métriques

Consultations de
la notice

206

Téléchargements du document

208