uva.nl
ILLC

Master of Logic / ILLC

Submit Coordinated Project

1st Semester 2006/07: Generalized Quantifiers: Their complexity and difficulty

Instructors
Jakub Szymanik.

If you are interested in this project, please contact Jakub Szymanik by e-mail.
ECTS
6
Description
We start with introduction into the generalized quantifiers (GQs) theory. Then we will discuss correspondence between GQs and automata theory. Mainly, we will show that exactly quantifiers definable in divisibility logic are recognized by finite automata [M. Mostowski]. We will also discuss more complex monadic quantifiers, especially we will show that Push-Down automata accepts exactly semilinear quantifiers of type (1) [J. van Benthem]. We will also discuss some connections of these results with neurological data on natural language processing and the learning theory for GQs.

In the second part, we will introduce branching quantifiers. Then we will present some results on their computational complexity, namely show that Henkin quantifiers and proportional branching quantifiers define NP--complete classes of finite models [M.Mostowski]&[M. Sevenster]. We will also try to think of the sources of such complexity by looking on some type of Ramsey quantifiers. And finally, we will show the application of this theory in the philosophy of language, discussing so-called Hintikka's Thesis that there exists natural language sentences for which we need branching operation to express their logical form.

In the first two weeks I will cover the folllowing topics (according to the literature given in brackets) in the introductory lectures (some homeworks are possible). After that, the students will work on individual topics for final papers.
  1. What are Generalized Quantifiers? (see Westerståhl and Stanley, 2006, chap. 0, 1.3, 2.2-2.4), (Krynicki and Mostowski, 1995b).
  2. Monadic quantifiers (see Westerståhl and Stanley, 2006, chap. 3.1-3.3, 4.1, 4.7-4.8).
  3. Crash course in automata theory (see Hopcroft et al., 2000, chap. 1.5, 2.2, 4.1, 6.1-6.2, 6.4, 7.2).
  4. Monadic quantifiers recognizable by finite automata (van Benthem, 1986), (Mostowski, 1998).
  5. Quantifiers accepted by Push-Down Automata (van Benthem, 1986), (Mostowski, 1998).
  6. Neuroimaging studies on quantifier comprehension (McMillan et al., 2005), (McMillan et al., 2006), (Clark and Grossman, 2006), (Szymanik, 2006).
  7. Branching quantifiers (see Westerst°ahl and Stanley, 2006, chap. 2.5), (Krynicki and Mostowski, 1995a).
  8. Some results on the computational complexity of branching quantifiers in finite models (see Sevenster, 2006, chap. 5), (Mostowski and Wojtyniak, 2004).
  9. Hintikka's Thesis (Barwise, 1979).
References
  • Barwise, J. (1979). On branching quantifiers in English. Journal of Philosophical Logic, 8:47-80.
  • Clark, R. and Grossman, M. (2006). Number sense and quantifier interpretation. Submitted.
  • Hopcroft, J., Motwani, R., and Ullman, J. (2000). Introduction to Automata Theory, Languages and Computation. Addison Wesley.
  • Krynicki, M. and Mostowski, M. (1995a). Henkin quantifiers. In Krynicki, M., Mostowski, M., and Szczerba, L., editors, Quantifiers: Logics, Models and Computation, pages 193-263. Kluwer Academic Publishers.
  • Krynicki, M. and Mostowski, M. (1995b). Quantifiers, some problems and ideas. In Krynicki, M., Mostowski, M., and Szczerba, L., editors, Quantifiers: Logics, Models and Computation, pages 1-21. Kluwer Academic Publishers.
  • McMillan, C., Clark, R., Moore, P., Devita, C., and Grossman, M. (2005). Neural basis for generalized quantifiers comprehension. Neuropsychologia, 43:1729-1737.
  • McMillan, C., Clark, R., Moore, P., and Grossman, M. (2006). Quantifiers comprehension in corticobasal degeneration. Brain and Cognition, 65:250-260.
  • Mostowski, M. (1998). Computational semantics for monadic quantifiers. Journal of applied Non?Classical Logics, 8:107-121.
  • Mostowski, M. and Wojtyniak, D. (2004). Computational complexity of the semantics of some natural language constructions. Annals of Pure and Applied Logic, 127:219-227.
  • Sevenster, M. (2006). Branching Imperfect Information. Logic, Language, and Computation. PhD thesis, Institute for Logic, Language, and Computation.
  • Szymanik, J. (2006). A comment on a neuroimaging study of natural language quantifier comprehension. Neuropsychologia, To appear.
  • van Benthem, J. (1986). Essays in logical semantics. Reidel.
  • Westerståhl, D. and Stanley, P. (2006). Quantifiers in Language And Logic. Oxford University Press, Oxford.

Back