Abstract
Reversibility of logic grammars in natural language processing is desirable for both theoretical and practical reasons. This paper addresses this topic in describing a new approach to automated inversion of logic grammars: the Direct Inversion Approach (dia). A logic grammar is inverted by automatically altering the order of literals in the grammar and reformulating certain recursive procedures at compile time. The inversion process results in a new executable grammar, which is evaluated top-down and left-to-right (using a standard Prolog interpreter), but not left-to-right with respect to the original grammar. Thedia improves upon related approaches not only in being fully automated and computationally tractable, but also with respect to the class of grammars it is able to invert and the performance of the new executable grammar produced.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Dymetman, M. and Isabelle, P., “Reversible Logic Grammars for Machine Translation,” inProceedings of the 2nd International Conference on Theoretical and Methodological Issues in Machine Translation of Natural Languages, Pittsburgh, PA, 1988.
Dymetman, M., Isabelle, P., and Perrault, F., “A Symmetrical Approach to Parsing and Generation,” inProceedings of COLING-92, Helsinki, Finland, 1990.
Dymetman, M., “A Generalized Greibach Normal Form for Definite Clause Grammars,” inProceedings of COLING-92, Nantes, France, 1992.
Gerdemann, D., “Parsing and Generation of Unification Grammars,”Ph.D dissertation, published asBeckman Institute Cognitive Science Technical Report, CS-91-06, University of Illinois, 1991.
Gerdemann, D. and Hinrichs, E., “Functor-Driven Natural Language Generation with Categorical-Unification Grammar,” inProceedings of COLING-90, Helsinki, Finland, 1990.
Hinrichs, E., Meurers, D., and Nakazawa, T., “Partial-VP and Split-NP Topicalization in German: An HPSG Analysis and Its Implementation,”Arbeitspapiere des Sonderforschungsbereichs 340 “Sprachtheoretische Grundlagen für die Computerlinguistik”, 1994.
Linden, E. van der and Minnen, G., “Algorithms for Generation in Lambek Theorem Proving,” inProceedings of the 28th ACL, Pittsburgh, PA, 1990.
Martinovié, M. and Strzalkowski, T., “Comparing Two Grammar-based Generation Algorithms: A Case Study,” inProceedings of the 30th ACL, Newark, DE, 1992.
Minnen, G. and Gerdemann, D., “Direct Automated Inversion of Logic Grammars,”Arbeitspapiere des Sonderforschungsbereichs 340 “Sprachtheoretische Grundlagen für die Computerlinguistik,” 1993. (url:http://www.sfs.nphil.uni-tuebingen.de/≈minnen)
Minnen, G., Gerdemann, D., and Götz, T., “Off-line Optimization for Early-style HPSG-Processing.” inProceedings of the 7th EACL, Dublin, Ireland, 1995. (url: http://www.sfs.nphil.uni-tuebingen.de/≈minnenl)
Peng, P. and Strzalkowski, T., “An Implementation of a Reversible Grammar,” inProceedings of the 8th Canadian Conference on Artificial Intelligence, Ottawa, Canada, 1990.
Pereira, F. and Shieber, S.,Prolog and Natural Language Analysis, Volume 10 of CSLI Lecture Notes, Stanford, CA, 1987.
O’Keefe, R.,The Craft of Prolog, MIT Press, Cambridge, MA, 1990.
Sterling, L. and Shapiro, E.,The Art of Prolog, MIT Press, Cambridge, MA, 1986.
Shieber, S., “A Uniform Architecture for Parsing and Generation,” inProceedings of COLING-88, Budapest, Hungary, 1988.
Shieber, S., Van Noord, G., Moore, R. and Pereira, F., “Semantic Head-Driven Generation,”Computational Linguistics, 16, 1, 1990.
Shoham, Y. and McDermott, D., “Directed Relations and Inversion of Prolog Programs,” inProceedings of the International Conference of Fifth Generation Computer Systems, Institute for New Generation Computer Technology, Tokyo, Japan, 1984.
Strzalkowski, T., “How to Invert a Parser into an Efficient Generator: An Algorithm for Logic Grammars,” inProceedings of COLING-90, Helsinki, Finland, 1990.
Strzalkowski, T., “Reversible Logic Grammars for Natural Language Parsing and Generation,”Computational Intelligence, 6, 3, 1990.
Strzalkowski, T., “A General Computational Method for Grammar Inversion,” inProceedings Reversible Grammar Workshop, Berkeley, CA, 1991.
Strzalkowski, T. and Peng, P., “Automated Inversion of Logic Grammars for Generation,” inProceedings of the 28th ACL, Pittsburgh, PA, 1990.
Ullman, J., “Implementation of Logical Query Languages for Databases,”ACM Transactions on Database Systems, 10, 3, 1985.
Author information
Authors and Affiliations
Corresponding author
Additional information
The presented research was sponsored by Teilprojekt B4 “Constraints on Grammar for Efficient Generation” of the Sonderforschungsbereich 340 of the Deutsche Forschungsgemeinschaft.
Guido Minnen: He received his M.A. degree in Language and Literature (specialization Computational Linguistics) in 1986 from Tilburg University, The Netherlands. Currently, he is a researcher in Sonderforschungsbereich 340 at the University of Tübingen, Germany. His main research interest is the use of off-line compilation techniques to support efficient reversible natural language processing.
Dale Gerdemann, Ph.D: He is an Assistant Professor in the Department of Linguistics, University of Tübingen, Germany. He received his B.A. from the University of Illinois, his M.A. from Colorado State University in 1981 and his Ph.D. from the University of Illinois in 1991. His present interests are parsing with typed feature structures and transformations of logic grammars.
Erhard W. Hinrichs: He is a Professor of General and Computational Linguistics at the University of Tübingen, Germany. He received his Ph.D. in linguistics from the Ohio State University in 1985. Previously he was a research scientist at Bolt Beranek and Newman Laboratories (Cambridge, USA), an Assistant Professor in the Department of Linguistics at the University of Illinois and a Visiting Professor in the Department of Computer Science at the University of the Saarland in Saarbrücken, Germany. His current research interests include unification-based grammar formalisms and their implementation, the semantics of tense and aspect, and machine translation.
About this article
Cite this article
Minnen, G., Gerdemann, D. & Hinrichs, E. Direct automated inversion of logic grammars. New Gener Comput 14, 131–168 (1996). https://doi.org/10.1007/BF03037497
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF03037497