Encoding second order string ACG with Deterministic Tree Walking Transducers.

Sylvain Salvati 1
1 SIGNES - Linguistic signs, grammar and meaning: computational logic for natural language
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
Abstract : We show that the string languages generated by second order string ACGs are exactly the ouput languages of deterministic tree walking transducers. Furthermore this result shows that the hierarchy of languages induced by the order of the lexicons of second order ACGs collapses.
Keywords : formal language abstract categorial grammars lambda calculus linear logic deterministic tree walking transducers
Type de document :
Communication dans un congrès
Shuly Wintner. The 11th conference on Formal Grammar, 2006, Malaga, Spain. CSLI Publications, pp.143-156, 2007, FG Online Proceedings
Liste complète des métadonnées
https://hal.inria.fr/inria-00333886
Contributeur : Sylvain Salvati <>
Soumis le : vendredi 24 octobre 2008 - 12:47:00
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13

Identifiants

  • HAL Id : inria-00333886, version 1

Collections

INRIA | LABRI | UNIV-BORDEAUX

Citation

Sylvain Salvati. Encoding second order string ACG with Deterministic Tree Walking Transducers.. Shuly Wintner. The 11th conference on Formal Grammar, 2006, Malaga, Spain. CSLI Publications, pp.143-156, 2007, FG Online Proceedings. 〈inria-00333886〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

165

Contact


archive-ouverte@inria.fr