HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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
Document type :
Conference papers
Complete list of metadata
https://hal.inria.fr/inria-00333886
Contributor : Sylvain Salvati Connect in order to contact the contributor
Submitted on : Friday, October 24, 2008 - 12:47:00 PM
Last modification on : Friday, February 4, 2022 - 3:23:39 AM

Identifiers

  • HAL Id : inria-00333886, version 1

Collections

CNRS | INRIA | LABRI | UNIV-BORDEAUX | INRIA2

Citation

Sylvain Salvati. Encoding second order string ACG with Deterministic Tree Walking Transducers.. The 11th conference on Formal Grammar, Paola Monachesi; Gerald Penn; Giorgio Satta; Shuly Wintner, 2006, Malaga, Spain. pp.143-156. ⟨inria-00333886⟩

Export

BibTeX TEI DC DCterms EndNote Datacite

Share

Metrics

Record views

72

 

Contact                    Legal Notice                    Personal Data