Jakub Szymanik University of Amsterdam
blank
About me
I'm interested in logic, language, computation, and cognitive science.
My works
31 items found.
Sort by:
  1. Livio Robaldo, Jakub Szymanik & Ben Meijering (2014). On the Identification of Quantifiers' Witness Sets: A Study of Multi-Quantifier Sentences. Journal of Logic, Language and Information 23 (1):53-81.
    Natural language sentences that talk about two or more sets of entities can be assigned various readings. The ones in which the sets are independent of one another are particularly challenging from the formal point of view. In this paper we will call them ‘Independent Set (IS) readings’. Cumulative and collective readings are paradigmatic examples of IS readings. Most approaches aiming at representing the meaning of IS readings implement some kind of maximality conditions on the witness sets involved. Two kinds (...)
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  2. Jakub Szymanik & Rineke Verbrugge (2013). Logic and Cognition: Special Issue of Best Papers of the ESSLLI 2012 Workshop. Journal of Logic, Language and Information 22 (4):357-362.
    The explanatory power of logic is vast and therefore it has proved a valuable tool for many disciplines, including the building-blocks of cognitive science, such as philosophy, computer science, mathematics, artificial intelligence, and linguistics. Logic has a great track record in providing interesting insights by means of formalization, and as such it is very useful in disambiguating psychological theories. Logically formalized cognitive theories are not only the source of unequivocal experimental hypotheses, but they also lend themselves naturally to computational modeling. (...)
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  3. Cédric Dégremont, Lena Kurzen & Jakub Szymanik (2012). Exploring the Tractability Border in Epistemic Tasks. Synthese (3):1-38.
    We analyse the computational complexity of comparing informational structures. Intuitively, we study the complexity of deciding queries such as the following: Is Alice’s epistemic information strictly coarser than Bob’s? Do Alice and Bob have the same knowledge about each other’s knowledge? Is it possible to manipulate Alice in a way that she will have the same beliefs as Bob? The results show that these problems lie on both sides of the border between tractability (P) and intractability (NP-hard). In particular, we (...)
    No categories
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  4. Marcin Mostowski & Jakub Szymanik (2012). Semantic Bounds for Everyday Language. Semiotica 188 (1/4):363-372.
    We consider the notion of everyday language. We claim that everyday language is semantically bounded by the properties expressible in the existential fragment of second–order logic. Two arguments for this thesis are formulated. Firstly, we show that so–called Barwise's test of negation normality works properly only when assuming our main thesis. Secondly, we discuss the argument from practical computability for finite universes. Everyday language sentences are directly or indirectly verifiable. We show that in both cases they are bounded by second–order (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  5. Livio Robaldo & Jakub Szymanik, Pragmatic Identification of the Witness Sets. Proceeding of the 8th Conference on Language Resources and Evaluation.
    Among the readings available for NL sentences, those where two or more sets of entities are independent of one another are particularly challenging from both a theoretical and an empirical point of view. Those readings are termed here as ‘Independent Set (IS) readings'. Standard examples of such readings are the well-known Collective and Cumulative Readings. (Robaldo, 2011) proposes a logical framework that can properly represent the meaning of IS readings in terms of a set-Skolemization of the witness sets. One of (...)
    Translate to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  6. Oliver Bott, Fabian Schlotterbeck & Jakub Szymanik (2011). Tractable Versus Intractable Reciprocal Sentences. In J. Bos & S. Pulman (eds.), Proceedings of the International Conference on Computational Semantics 9.
    In three experiments, we investigated the computational complexity of German reciprocal sentences with different quantificational antecedents. Building upon the tractable cognition thesis (van Rooij, 2008) and its application to the verification of quantifiers (Szymanik, 2010) we predicted complexity differences among these sentences. Reciprocals with all-antecedents are expected to preferably receive a strong interpretation (Dalrymple et al., 1998), but reciprocals with proportional or numerical quantifier antecedents should be interpreted weakly. Experiment 1, where participants completed pictures according to their preferred interpretation, provides (...)
    Translate to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  7. Cédric Dégremont, Lena Kurzen & Jakub Szymanik (2011). On theTractability of Comparing Informational Structures. In J. van Eijck & R. Verbrugge (eds.), Proceedings of the Workshop 'Reasoning about other minds: Logical and cognitive perspectives.
  8. Nina Gierasimczuk & Jakub Szymanik (2011). A Note on a Generalization of the Muddy Children Puzzle. In K. Apt (ed.), Proceeding of the 13th Conference on Theoretical Aspects of Rationality and Knowledge. ACM.
    We study a generalization of the Muddy Children puzzle by allowing public announcements with arbitrary generalized quantifiers. We propose a new concise logical modeling of the puzzle based on the number triangle representation of quantifi ers. Our general aim is to discuss the possibility of epistemic modeling that is cut for specifi c informational dynamics. Moreover, we show that the puzzle is solvable for any number of agents if and only if the quanti fier in the announcement is positively active (...)
    Translate to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  9. Nina Gierasimczuk & Jakub Szymanik (2011). Invariance Properties of Quantifiers and Multiagent Information Exchange. In M. Kanazawa (ed.), Proceedings of the 12th Meeting on Mathematics of Language, Lecture Notes in Artificial Intelligence 6878. Springer.
    The paper presents two case studies of multi-agent information exchange involving generalized quantifiers. We focus on scenarios in which agents successfully converge to knowledge on the basis of the information about the knowledge of others, so-called Muddy Children puzzle and Top Hat puzzle. We investigate the relationship between certain invariance properties of quantifiers and the successful convergence to knowledge in such situations. We generalize the scenarios to account for public announcements with arbitrary quantifiers. We show that the Muddy Children puzzle (...)
    Translate to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  10. Juha Kontinen & Jakub Szymanik (2011). Characterizing Definability of Second-Order Generalized Quantifiers. In L. Beklemishev & R. de Queiroz (eds.), Proceedings of the 18th Workshop on Logic, Language, Information and Computation, Lecture Notes in Artificial Intelligence 6642. Springer.
    We study definability of second-order generalized quantifiers. We show that the question whether a second-order generalized quantifier $\sQ_1$ is definable in terms of another quantifier $\sQ_2$, the base logic being monadic second-order logic, reduces to the question if a quantifier $\sQ^{\star}_1$ is definable in $\FO(\sQ^{\star}_2,<,+,\times)$ for certain first-order quantifiers $\sQ^{\star}_1$ and $\sQ^{\star}_2$. We use our characterization to show new definability and non-definability results for second-order generalized quantifiers. In particular, we show that the monadic second-order majority quantifier $\most^1$ is not definable (...)
    Translate to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  11. Jakub Szymanik & Marcin Zajenkowski (2011). Contribution of Working Memory in the Parity and Proportional Judgments. Belgian Journal of Linguistics 25:189-206.
    The paper presents an experimental evidence on differences in the sentence-picture verification under additional memory load between parity and proportional quantifiers. We asked subjects to memorize strings of 4 or 6 digits, then to decide whether a quantifier sentence is true at a given picture, and finally to recall the initially given string of numbers. The results show that: (a) proportional quantifiers are more difficult than parity quantifiers with respect to reaction time and accuracy; (b) maintaining either 4 or 6 (...)
    Translate to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  12. Iris van Rooij, Johan Kwisthout, Mark Blokpoel, Jakub Szymanik, Todd Wareham & Ivan Toni (2011). Intentional Communication: Computationally Easy or Difficult? Frontiers in Human Neuroscience 5.
    Human intentional communication is marked by its flexibility and context sensitivity. Hypothesized brain mechanisms can provide convincing and complete explanations of the human capacity for intentional communication only insofar as they can match the computational power required for displaying that capacity. It is thus of importance for cognitive neuroscience to know how computationally complex intentional communication actually is. Though the subject of considerable debate, the computational complexity of communication remains so far unknown. In this paper we defend the position that (...)
    Direct download (9 more)  
     
    My bibliography  
     
    Export citation  
  13. Marcin Zajenkowski, Rafał Styła & Jakub Szymanik (2011). A Computational Approach to Quantifiers as an Explanation for Some Language Impairments in Schizophrenia. Journal of Communication Disorder 44:2011.
    We compared the processing of natural language quantifiers in a group of patients with schizophrenia and a healthy control group. In both groups, the difficulty of the quantifiers was consistent with computational predictions, and patients with schizophrenia took more time to solve the problems. However, they were significantly less accurate only with proportional quantifiers, like more than half. This can be explained by noting that, according to the complexity perspective, only proportional quantifiers require working memory engagement.
    Translate to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  14. Alistair Isaac & Jakub Szymanik (2010). Logic in Cognitive Science: Bridging the Gap Between Symbolic and Connectionist Paradigms. Journal of the Indian Council of Philosophical Research (2):279-309.
    This paper surveys applications of logical methods in the cognitive sciences. Special attention is paid to non-monotonic logics and complexity theory. We argue that these particular tools have been useful in clarifying the debate between symbolic and connectionist models of cognition.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  15. Jakub Szymanik (2010). Almost All Complex Quantifiers Are Simple. In C. Ebert, G. Jäger, M. Kracht & J. Michaelis (eds.), Mathematics of Language 10/11, Lecture Notes in Computer Science 6149. Springer.
    We prove that PTIME generalized quantifiers are closed under Boolean operations, iteration, cumulation and resumption. -/- .
    Translate to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  16. Jakub Szymanik (2010). Computational Complexity of Polyadic Lifts of Generalized Quantifiers in Natural Language. Linguistics and Philosophy 33 (3):215-250.
    We study the computational complexity of polyadic quantifiers in natural language. This type of quantification is widely used in formal semantics to model the meaning of multi-quantifier sentences. First, we show that the standard constructions that turn simple determiners into complex quantifiers, namely Boolean operations, iteration, cumulation, and resumption, are tractable. Then, we provide an insight into branching operation yielding intractable natural language multi-quantifier expressions. Next, we focus on a linguistic case study. We use computational complexity results to investigate semantic (...)
    Direct download (9 more)  
     
    My bibliography  
     
    Export citation  
  17. Jakub Szymanik & Marcin Zajenkowski (2010). Quantifiers and Working Memory. In Maria Aloni & Katrin Schulz (eds.), Amsterdam Colloquium 2009, LNAI 6042. Springer.
    The paper presents a study examining the role of working<br>memory in quantifier verification. We created situations similar to the<br>span task to compare numerical quantifiers of low and high rank, parity<br>quantifiers and proportional quantifiers. The results enrich and support<br>the data obtained previously in and predictions drawn from a computational<br>model.
    Translate to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  18. Nina Gierasimczuk & Jakub Szymanik (2009). Branching Quantification V. Two-Way Quantification. Journal of Semantics 26 (4):329-366.
    Next SectionWe discuss the thesis formulated by Hintikka (1973) that certain natural language sentences require non-linear quantification to express their meaning. We investigate sentences with combinations of quantifiers similar to Hintikka's examples and propose a novel alternative reading expressible by linear formulae. This interpretation is based on linguistic and logical observations. We report on our experiments showing that people tend to interpret sentences similar to Hintikka sentence in a way consistent with our interpretation.
    Direct download (9 more)  
     
    My bibliography  
     
    Export citation  
  19. Jakub Szymanik (2009). Quantifiers in TIME and SPACE. Computational Complexity of Generalized Quantifiers in Natural Language. Dissertation, University of Amsterdam
    In the dissertation we study the complexity of generalized quantifiers in natural language. Our perspective is interdisciplinary: we combine philosophical insights with theoretical computer science, experimental cognitive science and linguistic theories. -/- In Chapter 1 we argue for identifying a part of meaning, the so-called referential meaning (model-checking), with algorithms. Moreover, we discuss the influence of computational complexity theory on cognitive tasks. We give some arguments to treat as cognitively tractable only those problems which can be computed in polynomial time. (...)
    Translate to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  20. Jakub Szymanik (2009). The Computational Complexity of Quantified Reciprocals. In Peter Bosch, David Gabelaia & Jérôme Lang (eds.), Lecture Notes on Artificial Intelligence 5422, Logic, Language, and Computation 7th International Tbilisi Symposium on Logic, Language, and Computation. Springer.
    We study the computational complexity of reciprocal sentences with quantified antecedents. We observe a computational dichotomy between different interpretations of reciprocity, and shed some light on the status of the so-called Strong Meaning Hypothesis.
    Translate to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  21. Jakub Szymanik & Marcin Zajenkowski (2009). Comprehension of Simple Quantifiers. Empirical Evaluation of a Computational Model. Cognitive Science: A Multidisciplinary Journal 34 (3):521-532.
    We examine the verification of simple quantifiers in natural language from a computational model perspective. We refer to previous neuropsychological investigations of the same problem and suggest extending their experimental setting. Moreover, we give some direct empirical evidence linking computational complexity predictions with cognitive reality.
    In the empirical study we compare time needed for understanding different types of quantifiers. We show that the computational distinction between quantifiers recognized by finite-automata and push-down automata is psychologically relevant. Our research improves upon hypothesis and (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  22. Jakub Szymanik & Marcin Zajenkowski (2009). Improving Methodology of Quantifier Comprehension Experiments. Neuropsychologia 47 (12):2682--2683.
    Szymanik (2007) suggested that the distinction between first-order and higher-order quantifiers does not coincide with the computational resources required to compute the meaning of quantifiers. Cognitive difficulty of quantifier processing might be better assessed on the basis of complexity of the minimal corresponding automata. For example, both logical and numerical quantifiers are first-order. However, computational devices recognizing logical quantifiers have a fixed number of states while the number of states in automata corresponding to numerical quantifiers grows with the rank of (...)
    Translate to English
    | Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  23. Jakub Szymanik & Marcin Zajenkowski (2009). Understanding Quantifiers in Language. In N. A. Taatgen & H. van Rijn (eds.), Proceedings of the 31st Annual Conference of the Cognitive Science Society.
    We compare time needed for understanding different types of quantifiers. We show that the computational distinction between quantifiers recognized by finite-automata and pushdown automata is psychologically relevant. Our research improves upon hypothesis and explanatory power of recent neuroimaging studies as well as provides evidence for the claim that human linguistic abilities are constrained by computational complexity.
    Translate to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  24. Juha Kontinen & Jakub Szymanik (2008). A Remark on Collective Quantification. Journal of Logic, Language and Information 17 (2):131-140.
    We consider collective quantification in natural language. For many years the common strategy in formalizing collective quantification has been to define the meanings of collective determiners, quantifying over collections, using certain type-shifting operations. These type-shifting operations, i.e., lifts, define the collective interpretations of determiners systematically from the standard meanings of quantifiers. All the lifts considered in the literature turn out to be definable in second-order logic. We argue that second-order definable quantifiers are probably not expressive enough to formalize all collective (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  25. Nina Gierasimczuk & Jakub Szymanik (2007). Hintikka's Thesis Revisited. Bulletin of Symbolic Logic 13:273.
    We discuss Hintikka’s Thesis [Hintikka 1973] that there exist natural language sentences which require non–linear quantification to express their logical form.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  26. Marcin Mostowski & Jakub Szymanik (2007). Computational Complexity of Some Ramsey Quantifiers in Finite Models. Bulletin of Symbolic Logic 13:281--282.
    The problem of computational complexity of semantics for some natural language constructions – considered in [M. Mostowski, D. Wojtyniak 2004] – motivates an interest in complexity of Ramsey quantifiers in finite models. In general a sentence with a Ramsey quantifier R of the following form Rx, yH(x, y) is interpreted as ∃A(A is big relatively to the universe ∧A2 ⊆ H). In the paper cited the problem of the complexity of the Hintikka sentence is reduced to the problem of computational (...)
    Translate to English
    | Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  27. J. Szymanik (2007). Computational Semantics for Monadic Quantifiers in Natural Language. Studia Semiotyczne 26:219-244.
    Direct download  
     
    My bibliography  
     
    Export citation  
  28. Jakub Szymanik (2007). A Note on Some Neuroimaging Study of Natural Language Quantifiers Comprehension. Neuropsychologia 45 (9):2158-2160.
    We discuss McMillan et al. (2005) paper devoted to study brain activity during comprehension of sentences with generalized quantifiers. According to the authors their results verify a particular computational model of natural language quantifier comprehension posited by several linguists and logicians (e. g. see van Benthem, 1986). We challenge this statement by invoking the computational difference between first-order quantifiers and divisibility quantifiers (e. g. see Mostowski, 1998). Moreover, we suggest other studies on quantifier comprehension, which can throw more light on (...)
    Translate to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  29. Jakub Szymanik (2007). Semantyka obliczeniowa dla kwantyfikatorów monadycznych w języku naturalnym. Studia Semiotyczne 26:219-244.
    Translate to English
    |
     
    My bibliography  
     
    Export citation  
  30. Tadeusz Ciecierski & Jakub Szymanik (2004). O hipotezie Bar-Hillela. Studia Semiotyczne 25:201-212.
    No categories
    Translate to English
    |
     
    My bibliography  
     
    Export citation  
  31. Jakub Szymanik (2004). Problemy z formą logiczną. Studia Semiotyczne 25:187-200.
    Translate to English
    |
     
    My bibliography  
     
    Export citation  
Is this list right?