Grammatical structures and logical deductions

Wojciech Buszkowski



The three essays presented here concern natural connections between grammatical derivations and structures provided by certain standard grammar formalisms, on the one hand, and deductions in logical systems, on the other hand. In the first essay we analyse the adequacy of Polish notation for higher-order languages. The Ajdukiewicz algorithm (Ajdukiewicz 1935) is discussed in terms of generalized MP-deductions. We exhibit a failure in Ajdukiewicz’s original version of the algorithm and give a correct one; we prove that generalized MP-deductions have the frontier property, which is essential for the plausibility of Polish notation. The second essay deals with logical systems corresponding to different grammar formalisms, as e.g. Finite State Acceptors, Context-Free Grammars, Categorial Grammars, and others. We show how can logical methods be used to establish certain linguistically significant properties of formal grammars. The third essay discusses the interplay between Natural Deduction proofs in grammar oriented logics and semantic structures expressible by typed lambda terms and combinators.

Full Text:



A. E. Ades and Mark J. Steedman, On the Order of Words, Linguistics and Philosophy 4 (1982), 517–558.

K. Ajdukiewicz, Die syntaktische Konnextität, Studia Philosophica 1 (1935), 1–27.

Y. Bar-Hillel, C. Gaifman and E. Shamir, On categorial and phrase structure grammars, Bull. Research Council Israel F 9 (1960), 155–166.

J. van Benthem, Essays in Logical Semantics, D. Reidel, Dordrecht, 1986.

J. van Benthem, The Lambek Calculus, in: [38].

J. van Benthem, Language in Action. Categories, Lambdas and Dynamic Logic, North-Holland, Amsterdam, 1991.

W. Buszkowski, Completeness Results for Lambek Syntactic Calculus, Zeitschrift für mathematische Logik und Grundlagen der Mathematik 32, (1986), 13–28.

W. Buszkowski, The logic of types, in: J. T. Srzednicki (ed.), Initiatives in Logic, Nijhoff, Dordrecht, 1987.

W. Buszkowski, Generative Power of Categorial Grammars, in: [38].

W. Buszkowski, The Ajdukiewicz Calculus and Polish Notation, in Polish, in: J. Pogonowski (ed.), Eufonia i Logos, The Book devoted to Professors Maria Steffen-Batogowa and Tadeusz Batóg, Adam Mickiewicz University Press, Poznań, 1995.

W. Buszkowski, W. Marciszewski and J. van Benthem (eds.), Categorial Grammar, J. Benjamins, Amsterdam, 1988.

J. M. Cohen, The equivalence of two concepts of categorial grammar, Information and Control 10 (1967), 475–484.

M. J. Cresswell, Logics and Languages, Methuen, London, 1974.

H. B. Curry, Some Logical Aspects of Grammatical Structure, in: R. Jakobson (ed.), Structure of Language and Its Mathematical Aspects, AMS, Providence, 1961.

H. B. Curry and R. Feys, Combinatory Logic, I, North Holland, Amsterdam, 1958.

K. Doˇ sen and P. Schroeder-Heister (eds.), Substructural Logics, Oxford University Press, Oxford, 1993.

D. Gallin, Intensional and Higher-order Modal Logic, North Holland, Amsterdam, 1975.

D. Gabbay, Labelled Deductive Systems I, CIS-München, Munich, 1991.

G. Gazdar and C. Mellish, Natural Language Processing in Prolog. An Introduction to Computational Linguistics, Addison-Wesley, Workingham, 1989.

P. T. Geach, A program for syntax, Synthese 22 (1968), 3–17; reprinted in [11].

J. Y. Girard, Linear Logic, Theoretical Computer Science 50 (1987), 1–102.

J. Y. Girard with P. Taylor and Y. Lafont, Proofs and Types, Cambridge University Press, Cambridge, 1989.

H. Hendriks, Studied Flexibility, Ph. D. Thesis, University of Utrecht, 1993.

H. Hiż, Grammar Logicism, The Monist 51, (1967), 110–127; reprinted in [11].

H. Hiż, On the Abstractness of Individuals, in: M. Munity (ed.), Identity and Individuals, New York University Press, 1971.

M. Kanazawa, The Lambek Calculus Enriched with Additional Connectives, Journal of Logic, Language and Information 1.2 (1992), 141–171.

E. L. Keenan and L. M. Faltz, Boolean Semantics for Natural Language, D. Reidel, Dordrecht, 1985.

J. Lambek, The mathematics of sentence structure, American Mathematical Monthly 65 (1958), 155–170.

J. Lambek, On categorial and categorical grammars, in: [38].

J. Lambek, Logics without structural rules, in: [16].

J. Lambek, From Categorial Grammar to Bilinear Logic, in [16].

J. Lambek and P. J. Scott, Introduction to higher order categorical logic, Cambridge University Press, Cambridge, 1986.

H. Leiss and M. Emms, Second-order Lambek Calculus and Cut Elimination, DYANA Reports, 1993.

D. Lewis, General Semantics, in: D. Davidson and G. Harman (eds.), Semantics of Natural Language, D. Reidel, Dordrecht, 1972.

R. Montague, Formal Philosophy, (ed. by R. Thomason), Yale University Press, New Haven, 1974.

M. Moortgat, Categorial Investigations: Logical and Linguistic Aspects of the Lambek Calculus, Foris, Dordrecht, 1988.

M. Moortgat, Residuation in Mixed Lambek Systems, manuscript, University of Utrecht, 1994.

R. T. Oehrle, E. Bach and D. Wheeler (eds.), Categorial Grammars and Natural Language Structures, D. Reidel, Dordrecht, 1988.

H. Ono and Y. Komori, Logics without the contraction rule, Journal of Symbolic Logic 50 (1985), 169–201.

B. Partee, Montague Grammar and Transformational Grammar, Linguistic Inquiry 6 (1975).

F. C. Pereira and S. M. Shieber, Prolog and Natural Language Analysis, CSLI Lecture Notes, 10, Chicago University Press, Stanford, 1987.

V. Sanchez Valenzia, Studies on Natural Logic and Categorial Grammar, Ph. D. Thesis, University of Amsterdam, 1991.

V. Sanchez Valenzia, Natural Logic: Parsing Driven Inference, to appear.

S. K. Shaumyan, Applicational Grammar as a Semantic Theory of Natural Language, Edinburgh University Press, Edinburgh, 1977.

M. Steedman, Combinators and grammars, in: [38].

M. Steedman, Categorial grammar. Tutorial overview, Lingua 90 (1993), 221-258.

P. Suppes, Logical inference in English, Studia Logica 38 (1979), 375–391.

A. Szabolcsi, ECP in Categorial Grammar, Max Planck Institute, Nijmegen, 1983.

H. Uszkoreit, Categorial Unification Grammar, Proc. 11th International Conference on Computational Linguistics, Bonn, 1986.

H. Wansing, The Logic of Information Structures, Ph. D. Thesis, University of Amsterdam, 1992.

D. N. Yetter, Quantales and (Non-Commutative) Linear Logic, The Journal of Symbolic Logic 55 (1990), 41–64.

W. Zielonka, Axiomatizability of Ajdukiewicz-Lambek calculus by means of cancellation schemes, Zeitschrift für mathematische Logik und Grundlagen der Mathematik 27 (1981), 215–224.

F. Zwarts, Categoriale grammatica en algebraische semantiek, Ph. D. Thesis, University of Groningen, 1986.

ISSN: 1425-3305 (print version)

ISSN: 2300-9802 (electronic version)

Partnerzy platformy czasopism