Abstract
We discuss the relationship between a categorial system (PPTS) based on partial proof trees (PPTs) as the building blocks of the system, resource sensitive logics and the nature of syntactic constraints. PPTS incorporates some of the key insights of lexicalized tree adjoining grammar, namely the notion of an extended domain of locality and the consequent factoring of recursion from the domain of dependencies. PPTS therefore inherits the linguistic and computational properties of that system. We discuss the relationship between PPTS, natural deduction, and linear logic proof-nets, and argue that a natural deduction system rather than a proof-net system is more appropriate for the construction of the PPTs. We also show how the use of PPTs allows us to ‘localize’ the management of resources, thereby freeing us from this management as the PPTs are combined.
We would like to thank the following people for their valuable comments that helped us improve our paper both in its content and presentation: Christophe Fouqueré, Mark Johnson, Alain Lecomte, Dale Miller, Michael Moortgat, Glyn Morrill, Richard Oehrle, Christian Retoré, Ed Stabler and Mark Steedman. This work was partially supported by NSF grant SBR8920230 and ARO grant DAAH04-94-G-0426.
Preview
Unable to display preview. Download preview PDF.
References
M. Abrusci. Phase semantics and sequent calculus for pure noncommutative classical linear prepositional logic. In The Journal of Symbolic Logic, 56(4):1403–1451, 1991.
M. Abrusci, Ch. Fouqueré, J. Vauzeilles. Tree adjoining grammar and non-commutative linear logic. In this volume, 1997.
G. Barry, M. Hepple, N. Leslie, G. Morrill. Proof figures and structural operators for categorial grammar. In Proceedings of the Fifth Conference of the European Chapter of the Association for Computational Linguistics.
Jacques Garrigue and Hassan AÏt-Kaci. The typed polymorphic label-selective λ-calculus. POPL 1994.
Jean-Yves Girard. Linear Logic: Its syntax and semantics. In Girard, Lafont, and Regnier, eds., Advances in Linear Logic, Cambridge University Press, Cambridge, England, pp. 1–42.
Mark Johnson. Natural deduction and proof nets intuitionistic linear logic. Manuscript, Brown University. 1996.
Aravind K. Joshi, K. Vijay-Shanker, and David Weir. The convergence of mildly context-sensitive grammar formalisms. In P. Sells, S. Shieber, and T. Wasow, eds., Foundational Issues in Natural Language Processing, Cambridge, MA:MIT Press.
Aravind K. Joshi. TAGs in categorial clothing, presented at the Tree Adjoining Grammar Workshop (TAG+), Institute for Research in Cognitive Science, University of Pennsylvania, Philadelphia, June 1992. A revised version, ‘Unfolded Types', was presented at the Logic and Language Workshop at LSA, Ohio State University, August 1993.
Aravind Joshi and Seth Kulick Partial proof trees as building blocks for a categorial grammar. To appear in Linguistics and Philosophy, 1997.
Aravind K. Joshi and Yves Schabes. Tree adjoining grammars. To appear in Arto Saolmaa and Gzegorz Rosenberg, eds., Handbook of Formal Languages and Automata, Vol. 3, Springer-Verlag, Heidelberg, 1997.
R. Kasper, B. Kiefer, K. Netter, and K. Vijay-Shanker. Compilation of HPSG to TAG. In 30th Annual Meeting of the Association for Computational Linguistics.
Anthony S. Kroch and Aravind K. Joshi. The linguistic relevance of tree adjoining grammars. Technical Report MS-CIS-85-16, Department of Computer and Information Science, University of Pennsylvania, 1985.
Alain Lecomte and Christian Retoré. Words as Modules: a lexicalised grammar in the framework of linear logic proof nets. In Carlos Martin-Vide, editor, Proceedings of the 2nd International Conference on Mathematical Linguistics, John Benjamins Publishing Company, Amsterdam, 1997.
Michael Moortgat. Categorial Investigations: Logical and Linguistic Aspects of the Lambek Calculus Foris, Dordrecht, 1988.
Glyn Morrill. Type-logical grammar. Kluwer, Dordrecht.
Glyn Morrill. Clausal Proofs and Discontinuity In Bulletin of the IGPL, Vol. 3, No. 2,3, pp. 403–427. 1995.
Christian Retoré. Calcul de Lambek et logique linéaire. Traitement Automatique des Langues 37(2):39–70.
Dirk Roorda. Resource Logics: proof-theoretical investigations, Ph.D. dissertation, Universiteit van Amsterdam. 1991.
K. Vijay-Shanker. 1992. Using descriptions of trees in a tree adjoining grammar. Computational Linguistics, 18(4):481–517.
The XTAG-Group. A lexicalized tree adjoining grammar for english. Technical Report IRCS 95-03, University of Pennsylvania. 1995.
D.N. Yetter. Quantales and (noncommutative) linear logic. In Journal of Symbolic Logic 55, pp. 41–64.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Joshi, A.K., Kulick, S. (1997). Partial proof trees, resource sensitive logics and syntactic constraints. In: Retoré, C. (eds) Logical Aspects of Computational Linguistics. LACL 1996. Lecture Notes in Computer Science, vol 1328. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0052149
Download citation
DOI: https://doi.org/10.1007/BFb0052149
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63700-4
Online ISBN: 978-3-540-69631-5
eBook Packages: Springer Book Archive