Capturing CFLs with Tree Adjoining Grammars

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We define a decidable class of TAGs that is strongly equivalent to CFGs and is cubic-time parsable. This class serves to lexicalize CFGs in the same manner as the LCFGs of Schabes and Waters but with considerably less restriction on the form of the grammars. The class provides a normal form for TAGs that generate local sets in much the same way that regular grammars provide a normal form for CFGs that generate regular sets.
8 pages, 3 figures. To appear in proceedings of ACL'94

Keywords

Computation and Language

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/147382

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cmp-lg/9405020
 http://arxiv.org/abs/cmp-lg/9405020
 In Proceedings of ACL-94

Collections

arXiv