Transforming Projective Bilexical Dependency Grammars into efficiently-parsable CFGs with Unfold-Fold

Mark Johnson

Transforming Projective Bilexical Dependency Grammars into efficiently-parsable CFGs with Unfold-Fold

Mark Johnson^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

26 Citations (Scopus)

Abstract

This paper shows how to use the Unfold-Fold transformation to transform Projective Bilexical Dependency Grammars (PBDGs) into ambiguity-preserving weakly equivalent Context-Free Grammars (CFGs). These CFGs can be parsed in O(n ³) time using a CKY algorithm with appropriate indexing, rather than the O(n ⁵) time required by a naive encoding. Informally, using the CKY algorithm with such a CFG mimics the steps of the Eisner-Satta O(n ³) PBDG parsing algorithm. This transformation makes all of the techniques developed for CFGs available to PBDGs. We demonstrate this by describing a maximum posterior parse decoder for PBDGs.

Original language	English
Title of host publication	ACL 2007 - Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics
Place of Publication	Stroudsburg, PA
Publisher	Association for Computational Linguistics (ACL)
Pages	168-175
Number of pages	8
ISBN (Print)	9781932432862
Publication status	Published - 2007
Externally published	Yes
Event	45th Annual Meeting of the Association for Computational Linguistics, ACL 2007 - Prague, Czech Republic Duration: 23 Jun 2007 → 30 Jun 2007

Other

Other	45th Annual Meeting of the Association for Computational Linguistics, ACL 2007
Country/Territory	Czech Republic
City	Prague
Period	23/06/07 → 30/06/07

Cite this

@inproceedings{3b97da5cc7d048ddbc34aa686f998e59,

title = "Transforming Projective Bilexical Dependency Grammars into efficiently-parsable CFGs with Unfold-Fold",

abstract = "This paper shows how to use the Unfold-Fold transformation to transform Projective Bilexical Dependency Grammars (PBDGs) into ambiguity-preserving weakly equivalent Context-Free Grammars (CFGs). These CFGs can be parsed in O(n 3) time using a CKY algorithm with appropriate indexing, rather than the O(n 5) time required by a naive encoding. Informally, using the CKY algorithm with such a CFG mimics the steps of the Eisner-Satta O(n 3) PBDG parsing algorithm. This transformation makes all of the techniques developed for CFGs available to PBDGs. We demonstrate this by describing a maximum posterior parse decoder for PBDGs.",

author = "Mark Johnson",

year = "2007",

language = "English",

isbn = "9781932432862",

pages = "168--175",

booktitle = "ACL 2007 - Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics",

publisher = "Association for Computational Linguistics (ACL)",

note = "45th Annual Meeting of the Association for Computational Linguistics, ACL 2007 ; Conference date: 23-06-2007 Through 30-06-2007",

}

Johnson, M 2007, Transforming Projective Bilexical Dependency Grammars into efficiently-parsable CFGs with Unfold-Fold. in ACL 2007 - Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics. Association for Computational Linguistics (ACL), Stroudsburg, PA, pp. 168-175, 45th Annual Meeting of the Association for Computational Linguistics, ACL 2007, Prague, Czech Republic, 23/06/07.

Transforming Projective Bilexical Dependency Grammars into efficiently-parsable CFGs with Unfold-Fold. / Johnson, Mark.
ACL 2007 - Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics. Stroudsburg, PA: Association for Computational Linguistics (ACL), 2007. p. 168-175.

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - Transforming Projective Bilexical Dependency Grammars into efficiently-parsable CFGs with Unfold-Fold

AU - Johnson, Mark

PY - 2007

Y1 - 2007

N2 - This paper shows how to use the Unfold-Fold transformation to transform Projective Bilexical Dependency Grammars (PBDGs) into ambiguity-preserving weakly equivalent Context-Free Grammars (CFGs). These CFGs can be parsed in O(n 3) time using a CKY algorithm with appropriate indexing, rather than the O(n 5) time required by a naive encoding. Informally, using the CKY algorithm with such a CFG mimics the steps of the Eisner-Satta O(n 3) PBDG parsing algorithm. This transformation makes all of the techniques developed for CFGs available to PBDGs. We demonstrate this by describing a maximum posterior parse decoder for PBDGs.

AB - This paper shows how to use the Unfold-Fold transformation to transform Projective Bilexical Dependency Grammars (PBDGs) into ambiguity-preserving weakly equivalent Context-Free Grammars (CFGs). These CFGs can be parsed in O(n 3) time using a CKY algorithm with appropriate indexing, rather than the O(n 5) time required by a naive encoding. Informally, using the CKY algorithm with such a CFG mimics the steps of the Eisner-Satta O(n 3) PBDG parsing algorithm. This transformation makes all of the techniques developed for CFGs available to PBDGs. We demonstrate this by describing a maximum posterior parse decoder for PBDGs.

UR - http://www.scopus.com/inward/record.url?scp=84860503337&partnerID=8YFLogxK

M3 - Conference proceeding contribution

AN - SCOPUS:84860503337

SN - 9781932432862

SP - 168

EP - 175

BT - ACL 2007 - Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics

PB - Association for Computational Linguistics (ACL)

CY - Stroudsburg, PA

T2 - 45th Annual Meeting of the Association for Computational Linguistics, ACL 2007

Y2 - 23 June 2007 through 30 June 2007

ER -

Transforming Projective Bilexical Dependency Grammars into efficiently-parsable CFGs with Unfold-Fold

Abstract

Other

Other files and links

Fingerprint

Cite this