Abstract
We present here filtered-popping recursive transition networks (FPRTNs), a special breed of RTNs, and an efficient parsing algorithm based on recursive transition network with string output (RTNSO) which constructs the set of parses of a potentially ambiguous sentence as a FPRTN in polynomial time. By constructing a FPRTN rather than a parse enumeration, we avoid the exponential explosion due to cases where the number of parses increases exponentially w.r.t. the input length. The algorithm is compatible with the grammars that can be manually developed with the Intex and Unitex systems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Woods, W.A.: Transition network grammars for natural language analysis. Commun. ACM 13(10), 591–606 (1970)
Sastre, J.M., Forcada, M.L.: Efficient parsing using recursive transition networks with string output. LNCS (LNAI), vol. 5603. Springer, Heidelberg (in press)
Earley, J.: An efficient context-free parsing algorithm. Commun. ACM 13(2), 94–102 (1970)
Ratnaparkhi, A.: Statistical models for unsupervised prepositional phrase attachment. In: COLING-ACL 1998, Morristown, NJ, USA, ACL, pp. 1079–1085 (1998)
Silberztein, M.D.: Dictionnaires électroniques et analyse automatique de textes. Le système INTEX. Masson, Paris (1993)
Paumier, S.: Unitex 1.2 User Manual. Université de Marne-la-Vallée (2006)
Aycock, J., Horspool, N.: Practical Earley Parsing. The Computer Journal 45(6), 620–630 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sastre-Martínez, J.M. (2009). Efficient Parsing Using Filtered-Popping Recursive Transition Networks. In: Maneth, S. (eds) Implementation and Application of Automata. CIAA 2009. Lecture Notes in Computer Science, vol 5642. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02979-0_28
Download citation
DOI: https://doi.org/10.1007/978-3-642-02979-0_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-02978-3
Online ISBN: 978-3-642-02979-0
eBook Packages: Computer ScienceComputer Science (R0)