Publications

Makoto Kanazawa. Formal Grammar: An Introduction. Lecture notes for my course Mathematical Linguistics at SOKENDAI.

Makoto Kanazawa. Second-order abstract categorial grammars. July 28, 2009. 22 pages. (Notes for my first lecture at Sylvain Pogodalla and my ESSLLI 2009 course Advances in Abstract Categorial Grammars: Language Theory and Linguistic Modeling.)

Makoto Kanazawa. 2023. Learning Context-Free Grammars from Positive Data and Membership Queries. In Hansen, H.H., Scedrov, A., de Queiroz, R.J., editors, Logic, Language, Information, and Computation, WoLLIC 2023. Lecture Notes in Computer Science 13923. Cham: Springer. [PDF]

Makoto Kanazawa and Ryo Yoshinaka. 2023. Extending Distributional Learning from Positive Data and Membership Queries. Proceedings of 16th edition of the International Conference on Grammatical Inference, in Proceedings of Machine Learning Research 217, 8-22.

Makoto Kanazawa and Ryo Yoshinaka. 2021. A hierarchy of context-free languages learnable from positive data and membership queries. In Jane Chandlee et al., editors, Proceedings of the Fifteenth International Conference on Grammatical Inference. Proceedings of Machine Learning Research 153, 18-31. Errata.

Makoto Kanazawa. 2019. Ogden's lemma, multiple context-free grammars, and the control language hierarchy. Information and Computation 269, 104449. [PDF]

Makoto Kanazawa and Tobias Kappé. 2019. Decision problems for Clark-congruential languages. In Olgierd Unold, Witold Dyrka, and Wojciech Wieczorek, editors, Proceedings of The 14th International Conference on Grammatical Inference, Proceedings of Machine Learning Research 93, 3-16.

Makoto Kanazawa. 2018. On the recognizing power of the Lambek calculus with brackets. Journal of Logic, Language and Information 27(4), 295-312. Published online: 15 May 2018. [arXiv]

Makoto Kanazawa. 2017. Parsing and generation as Datalog query evaluation. IfCoLog Journal of Logics and Their Applications 4(4), 1103-1211. (Special Issue Dedicated to the Memory of Grigori Mints.) [PDF]

Makoto Kanazawa and Ryo Yoshinaka. 2017. The strong, weak, and very weak finite context and kernel properties. In Frank Drewes, Carlos Martín-Vide, and Bianca Truthe, editors, Language and Automata Theory and Applications: 11th International Conference, LATA 2017, pages 77-88. Lecture Notes in Computer Science 10168. Cham: Springer. [PDF]

Alexander Clark, Makoto Kanazawa, Gregory M. Kobele, and Ryo Yoshinaka. 2016. Distributional Learning of Some Nonlinear Tree Grammars. Fundamenta Informaticae 146(4), 339-377. [PDF]

Makoto Kanazawa and Ryo Yoshinaka. 2016. Distributional learning and context/substructure enumerability in nonlinear tree grammars. In Annie Foret, Glyn Morrill, Reinhard Muskens, Rainer Osswald, and Sylvain Pogodalla, editors, Formal Grammar, FG 2015/2016, pages 94-111. Lecture Notes in Computer Science 9804. Berlin, Heidelberg: Springer. [PDF]

Makoto Kanazawa. 2016. Weak vs. strong finite context and kernel properties. NII Technical Report. NII-2016-006E.

Makoto Kanazawa. 2016. Ogden's lemma, multiple context-free grammars, and the control language hierarchy. In Adrian-Horia Dediu, Jan Janoušek, Carlos Martín-Vide, and Bianca Truthe, editors, Language and Automata Theory and Applications: 10th International Conference, LATA 2016, pages 371-383. Lecture Notes in Computer Science 9618. Cham: Springer. [PDF]

Makoto Kanazawa. 2015. Syntactic features for regular constraints and an approximation of directional slashes in abstract categorial grammars. In Yusuke Kubota and Robert Levine, editors, Proceedings for ESSLLI 2015 Workshop `Empirical Advances in Categorial Grammars' (CG 2015), pages 34-70. [PDF]

Makoto Kanazawa and Junri Shimada. 2014. Toward a logic of cumulative quantification. In Valeria de Paiva et al., editors, Joint Proceedings of the Second Workshop on Natural Language and Computer Science (NLCS'14) & 1st International Workshop on Natural Language Services for Reasoners (NLSR 2014), pages 111-124. Center for Informatics and Systems of the University of Coimbra. [PDF]

Makoto Kanazawa. 2014. A generalization of linear indexed grammars equivalent to simple context-free tree grammars. In Glyn Morrill, Reinhard Muskens, Rainer Osswald, and Frank Richter, editors, Formal Grammar, FG 2014, pages 86-103. Lecture Notes in Computer Science 8612. Berlin: Springer. [PDF | unabridged version]

Makoto Kanazawa. 2016. Multidimensional trees and a Chomsky-Schützenberger-Weir representation theorem for simple context-free tree grammars. Journal of Logic and Computation 26(5), 1469-1516. Published online June 30, 2014. [PDF]

Makoto Kanazawa. 2014. Almost affine lambda terms. In Andrzej Indrzejczak, Janusz Kaczmarek, and Michał Zawidzki, editors, Trends in Logic XIII, pages 131-148. Łódź: Łódź University Press. [PDF | unabridged version]

Makoto Kanazawa, Junri Shimada, and Christopher Tancredi. 2014. Singular pronouns bound by plural quantifiers. Reports of the Keio Institute of Cultural and Linguistic Studies 45, 73-123. Keio University.

Makoto Kanazawa, Gregory M. Kobele, Jens Michaelis, Sylvain Salvati, and Ryo Yoshinaka. 2014. The failure of the strong pumping lemma for multiple context-free languages. Theory of Computing Systems 55(1), 250-278. Published online: 30 January, 2014. [PDF]

Makoto Kanazawa. 2013. Monadic quantifiers recognized by deterministic pushdown automata. In Maria Aloni, Michael Franke, and Floris Roelofsen, editors, Proceedings of the 19th Amsterdam Colloquium, pages 139-146. See here for a correct statement of Lemma 3.

Makoto Kanazawa and Sylvain Salvati. 2013. The string-meaning relations definable by Lambek grammars and context-free grammars. In Glyn Morrill and Mark-Jan Nederhof, editors, Formal Grammar, FG 2012/2013, pages 191-208. Lecture Notes in Computer Science 8036. Berlin: Springer. [PDF]

Philippe de Groote and Makoto Kanazawa. 2013. A note on intensionalization. Journal of Logic, Language and Information 22(2), 173-194. Open access. Published online: 10 April 2013. See this [PDF] for a correction of the misprint in lines 4-5 of page 191 of the published version.

Makoto Kanazawa and Sylvain Salvati. 2012. MIX is not a tree-adjoining language. In Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics, pages 664-674. Jeju, Republic of Korea, July 2012. Associated software.

Makoto Kanazawa, Jens Michaelis, Sylvain Salvati, and Ryo Yoshinaka. 2011. Well-nestedness properly subsumes strict derivational minimalism. In Sylvain Pogodalla and Jean-Philippe Prost, editors, Logical Aspects of Computational Linguistics, LACL 2011, pages 112-128. Lecture Notes in Computer Science 6736. Berlin: Springer.

Ryo Yoshinaka and Makoto Kanazawa. 2011. Distributional learning of abstract categorial grammars. In Sylvain Pogodalla and Jean-Philippe Prost, editors, Logical Aspects of Computational Linguistics, LACL 2011, pages 251-266. Lecture Notes in Computer Science 6736. Berlin: Springer.

Makoto Kanazawa and Sylvain Salvati. 2010. The copying power of well-nested multiple context-free grammars. In Adrian-Horia Dediu, Henning Fernau, and Carlos Martín-Vide, editors, Language and Automata Theory and Applications, Fourth International Conference, LATA 2010, pages 344-355. Lecture Notes in Computer Science 6031. Berlin: Springer. [PDF]

Makoto Kanazawa. 2010. Second-order abstract categorial grammars as hyperedge replacement grammars. Journal of Logic, Language and Information 19(2), 137-161. Published online: 18 December 2009. [PDF]

Makoto Kanazawa. 2009. The pumping lemma for well-nested multiple context-free languages. In Volker Diekert and Dirk Nowotka, editors, Developments in Language Theory: 13th International Conference, DLT 2009, pages 312-325. Lecture Notes in Computer Science 5583. Berlin: Springer. [PDF] Errata (December 2, 2009).

Makoto Kanazawa. 2008. A prefix-correct Earley recognizer for multiple context-free grammars. In Proceedings of the Ninth International Workshop on Tree Adjoining Grammars and Related Formalisms, pages 49-56. Tübingen, Germany, June 7-8, 2008.

Makoto Kanazawa and Sylvain Salvati. 2007. Generating control languages with abstract categorial grammars. This version has appeared in the preliminary proceedings of FG-2007: The 12th Conference on Formal Grammar. The final version of the proceedings is to appear as CSLI Online Publications. Errata.

Makoto Kanazawa. 2007. Parsing and generation as Datalog queries. In Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics, pages 176-183. Prague, Czech Republic, June 2007. Association for Computational Linguistics. Errata.

Makoto Kanazawa. 2006. Abstract families of abstract categorial languages. G. Mints and R. de Queiroz, editors, Proceedings of the 13th Workshop on Logic, Language, Information and Computation (WoLLIC 2006). Electronic Notes in Theoretical Computer Science 165, 65-80. [PDF] Errata.

Makoto Kanazawa. 2006. Computing interpolants in implicational logics. Annals of Pure and Applied Logic 142(1-3), 125-201. [PDF]

Makoto Kanazawa and Ryo Yoshinaka. 2005. Lexicalization of second-order ACGs. NII Technical Report. NII-2005-012E. National Institute of Informatics, Tokyo. This corrects an error in our LACL 2005 paper below.

Ryo Yoshinaka and Makoto Kanazawa. 2005. The complexity and generative capacity of lexicalized abstract categorial grammars. In Philippe Blache, Edward Stabler, Joan Busquets, Richard Moot, editors, Logical Aspects of Computational Linguistics, LACL 2005, pp. 330-346. Lecture Notes in Artificial Intelligence 3492. Berlin: Springer.

Makoto Kanazawa, Stefan Kaufmann, and Stanley Peters. 2005. On the lumping semantics of counterfactuals. Journal of Semantics 22(2), 129-151.

Makoto Kanazawa. 2004. Review of Michael R. Brent, ed., Computational Approaches to Langauge Acquisition. Journal of Logic, Language and Information 13, 377-378 (print version); 377-379 (online version).

Makoto Kanazawa. 2003. Computing word meanings by interpolation. [ps | pdf] In Paul Dekker and Robert van Rooy, editors, Proceedings of the Fourteenth Amsterdam Colloquium, pp. 157-162. ILLC/Department of Philosophy, University of Amsterdam. Errata.

Makoto Kanazawa. 2001. Singular donkey pronouns are semantically singular. Linguistics and Philosophy 24(3), 383-403. [PDF] Errata.

Makoto Kanazawa. 2001. Learning word-to-meaning mappings in logical semantics. [ps | pdf | pdf in US Letter Size]. In Robert van Rooy and Martin Stokhof, editors, Proceedings of the Thirteenth Amsterdam Colloquium, December 17-19, 2001, pp. 126-131. ILLC/Department of Philosophy, University of Amsterdam. Errata.

Makoto Kanazawa. 1999. Lambek calculus: Recognizing power and complexity. In Jelle Gerbrandy, Maarten Marx, Maarten de Rijke, and Yde Venema, editors, JFAK. Essays Dedicated to Johan van Benthem on the Occasion of his 50th Birthday. Vossiuspers, Amsterdam University Press.

Mary Dalrymple, Makoto Kanazawa, Yookyung Kim, Sam Mchombo, and Stanley Peters. 1998. Reciprocal expressions and the concept of reciprocity. Linguistics and Philosophy 21(2), 159-210.

Makoto Kanazawa. 1998. Learnable Classes of Categorial Grammars. Studies in Logic, Language and Information. Stanford, Calif.: CSLI Publications. Errata.

Makoto Kanazawa, Christopher Piñón, and Henriette de Swart, eds. 1996. Quantifiers, Deduction, and Context. Stanford, Calif.: CSLI Publications.

Makoto Kanazawa. 1996. Identification in the limit of categorial grammars. Journal of Logic, Language and Information 5(2), 115-155.

Dick de Jongh and Makoto Kanazawa. 1996. Angluin's theorem for indexed families of r.e. sets and applications. In Proceedings of the Ninth Annual Conference on Computational Learning Theory, ACM Press. (A slightly longer version [PDF].)

Makoto Kanazawa. 1994. Completeness and decidability of the mixed style of inference with composition. In Paul Dekker and Martin Stokhof, eds., Proceedings of the Ninth Amsterdam Colloquium, pp. 377-390.

Makoto Kanazawa. 1994. Weak vs. strong readings of donkey sentences and monotonicity inference in a dynamic setting. Linguistics and Philosophy 17(2), 109-158. Errata.

Makoto Kanazawa. 1994. Dynamic generalized quantifiers and monotonicity. In Makoto Kanazawa and Christopher J. Piñón, editors, Dynamics, Polarity, and Quantification, Stanford, Calif.: CSLI Publications. Distributed by Cambridge University Press.

Makoto Kanazawa. 1994. Learnable Classes of Categorial Grammars. Ph.D. Dissertation, Department of Linguistics, Stanford University. Made available as ILLC dissertation series 1994-8, Institute for Logic, Language and Computation, University of Amsterdam. (Published as Kanazawa 1998.)

Makoto Kanazawa. 1994. Comments on Inference systems for update semantics by Willem Groeneveld and Frank Veltman. In R. Cooper and J. Groenendijk, editors., Integrating Semantic Theories II, DYANA report R2.1B, Amsterdam, pp. 281-287.

Mary Dalrymple, Makoto Kanazawa, Sam Mchombo, and Stanley Peters. 1994. What do reciprocals mean? In Mandy Harvey and Lynn Santelmann, eds., Proceedings from Semantics and Linguistic Theory IV, pp. 61-78, Ithaca, NY: Cornell University.

Makoto Kanazawa. 1994. A note on language classes with finite elasticity. Report CS-R9471, CWI, Amsterdam.

Makoto Kanazawa. 1992. The Lambek calculus enriched with additional connectives. Journal of Logic, Language, and Information 1(2), 141-171.