Results for 'Marcin Mostowski Jakub Szymanik'

1000+ found
Order:
  1.  72
    Computational Complexity of Some Ramsey Quantifiers in Finite Models.Marcin Mostowski & Jakub Szymanik - 2007 - 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 (...)
    Direct download (2 more)  
    Translate
     
     
    Export citation  
     
    Bookmark   2 citations  
  2.  15
    Computational Complexity of Some Ramsey Quantifiers in Finite Models.Marcin Mostowski Jakub Szymanik & M. Mostowski - 2007 - Bulletin of Symbolic Logic 13:281-282.
  3. Semantic Bounds for Everyday Language.Marcin Mostowski & Jakub Szymanik - 2012 - Semiotica 2012 (188):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 (6 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  4.  33
    Improving Methodology of Quantifier Comprehension Experiments.Jakub Szymanik & Marcin Zajenkowski - 2009 - 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 (...)
    Direct download  
    Translate
     
     
    Export citation  
     
    Bookmark   4 citations  
  5.  54
    A Computational Approach to Quantifiers as an Explanation for Some Language Impairments in Schizophrenia.Marcin Zajenkowski, Rafał Styła & Jakub Szymanik - 2011 - 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.
    Direct download  
    Translate
     
     
    Export citation  
     
    Bookmark   4 citations  
  6. Comprehension of Simple Quantifiers: Empirical Evaluation of a Computational Model.Jakub Szymanik & Marcin Zajenkowski - 2010 - Cognitive Science 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.<br>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 (7 more)  
     
    Export citation  
     
    Bookmark   21 citations  
  7.  48
    Contribution of Working Memory in the Parity and Proportional Judgments.Jakub Szymanik & Marcin Zajenkowski - 2011 - 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 (...)
    Direct download  
    Translate
     
     
    Export citation  
     
    Bookmark   5 citations  
  8.  70
    Quantifiers and Working Memory.Jakub Szymanik & Marcin Zajenkowski - 2010 - 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.
    Direct download  
    Translate
     
     
    Export citation  
     
    Bookmark   2 citations  
  9. Understanding Quantifiers in Language.Jakub Szymanik & Marcin Zajenkowski - 2009 - 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
     
     
    Export citation  
     
    Bookmark  
  10. A Note on Some Neuroimaging Study of Natural Language Quantifiers Comprehension.Jakub Szymanik - 2007 - 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 (...)
    Translate
     
     
    Export citation  
     
    Bookmark   8 citations  
  11.  79
    Interpreting Tractable Versus Intractable Reciprocal Sentences.Oliver Bott, Fabian Schlotterbeck & Jakub Szymanik - forthcoming - In Proceedings of the International Conference on Computational Semantics.
    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, (...)
    Direct download  
    Translate
     
     
    Export citation  
     
    Bookmark   1 citation  
  12.  68
    Tractable Versus Intractable Reciprocal Sentences.Oliver Bott, Fabian Schlotterbeck & Jakub Szymanik - 2011 - 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, (...)
    Direct download  
    Translate
     
     
    Export citation  
     
    Bookmark  
  13.  11
    Decidability Problems in Languages with Henkin Quantifiers.Michał Krynicki & Marcin Mostowski - 1992 - Annals of Pure and Applied Logic 58 (2):149-172.
    Krynicki, M. and M. Mostowski, Decidability problems in languages with Henkin quantifiers, Annals of Pure and Applied Logic 58 149–172.We consider the language L with all Henkin quantifiers Hn defined as follows: Hnx1…xny1…yn φ iff f1…fnx1. ..xn φ, ...,fn). We show that the theory of equality in L is undecidable. The proof of this result goes by interpretation of the word problem for semigroups.Henkin quantifiers are strictly related to the function quantifiers Fn defined as follows: Fnx1…xny1…yn φ iff fx1…xn (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  14.  25
    Degrees of Logics with Henkin Quantifiers in Poor Vocabularies.Marcin Mostowski & Konrad Zdanowski - 2004 - Archive for Mathematical Logic 43 (5):691-702.
    We investigate some logics with Henkin quantifiers. For a given logic L, we consider questions of the form: what is the degree of the set of L–tautologies in a poor vocabulary (monadic or empty)? We prove that the set of tautologies of the logic with all Henkin quantifiers in empty vocabulary L*∅ is of degree 0’. We show that the same holds also for some weaker logics like L ∅(Hω) and L ∅(Eω). We show that each logic of the form (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  15.  37
    Quantifiers and Cognition: Logical and Computational Perspectives.Jakub Szymanik - 2016 - Springer.
    This volume on the semantic complexity of natural language explores the question why some sentences are more difficult than others. While doing so, it lays the groundwork for extending semantic theory with computational and cognitive aspects by combining linguistics and logic with computations and cognition. -/- Quantifier expressions occur whenever we describe the world and communicate about it. Generalized quantifier theory is therefore one of the basic tools of linguistics today, studying the possible meanings and the inferential power of quantifier (...)
    Direct download  
     
    Export citation  
     
    Bookmark   6 citations  
  16.  24
    Learnability and Semantic Universals.Shane Steinert-Threlkeld & Jakub Szymanik - forthcoming - Semantics and Pragmatics.
    One of the great successes of the application of generalized quantifiers to natural language has been the ability to formulate robust semantic universals. When such a universal is attested, the question arises as to the source of the universal. In this paper, we explore the hypothesis that many semantic universals arise because expressions satisfying the universal are easier to learn than those that do not. While the idea that learnability explains universals is not new, explicit accounts of learning that can (...)
    Direct download  
     
    Export citation  
     
    Bookmark   3 citations  
  17.  68
    Quantifiers in TIME and SPACE. Computational Complexity of Generalized Quantifiers in Natural Language.Jakub Szymanik - 2009 - 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. (...)
    Direct download  
    Translate
     
     
    Export citation  
     
    Bookmark   12 citations  
  18. Computational Complexity of Polyadic Lifts of Generalized Quantifiers in Natural Language.Jakub Szymanik - 2010 - 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 (5 more)  
     
    Export citation  
     
    Bookmark   12 citations  
  19.  92
    Tractability and the Computational Mind.Rineke Verbrugge & Jakub Szymanik - 2018 - In Mark Sprevak & Matteo Colombo (eds.), The Routledge Handbook of the Computational Mind. Oxford, UK: pp. 339-353.
    We overview logical and computational explanations of the notion of tractability as applied in cognitive science. We start by introducing the basics of mathematical theories of complexity: computability theory, computational complexity theory, and descriptive complexity theory. Computational philosophy of mind often identifies mental algorithms with computable functions. However, with the development of programming practice it has become apparent that for some computable problems finding effective algorithms is hardly possible. Some problems need too much computational resource, e.g., time or memory, to (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  20. Branching Quantification V. Two-Way Quantification.Nina Gierasimczuk & Jakub Szymanik - 2009 - 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)  
     
    Export citation  
     
    Bookmark   9 citations  
  21.  11
    Parameterized Complexity of Theory of Mind Reasoning in Dynamic Epistemic Logic.Iris van de Pol, Iris van Rooij & Jakub Szymanik - 2018 - Journal of Logic, Language and Information 27 (3):255-294.
    Theory of mind refers to the human capacity for reasoning about others’ mental states based on observations of their actions and unfolding events. This type of reasoning is notorious in the cognitive science literature for its presumed computational intractability. A possible reason could be that it may involve higher-order thinking. To investigate this we formalize theory of mind reasoning as updating of beliefs about beliefs using dynamic epistemic logic, as this formalism allows to parameterize ‘order of thinking.’ We prove that (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  22.  65
    Exploring the Tractability Border in Epistemic Tasks.Cédric Dégremont, Lena Kurzen & Jakub Szymanik - 2014 - Synthese 191 (3):371-408.
    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 (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  23.  11
    Interactive Semantic Alignment Model: Social Influence and Local Transmission Bottleneck.Dariusz Kalociński, Marcin Mostowski & Nina Gierasimczuk - 2018 - Journal of Logic, Language and Information 27 (3):225-253.
    We provide a computational model of semantic alignment among communicating agents constrained by social and cognitive pressures. We use our model to analyze the effects of social stratification and a local transmission bottleneck on the coordination of meaning in isolated dyads. The analysis suggests that the traditional approach to learning—understood as inferring prescribed meaning from observations—can be viewed as a special case of semantic alignment, manifesting itself in the behaviour of socially imbalanced dyads put under mild pressure of a local (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  24.  36
    Invariance Properties of Quantifiers and Multiagent Information Exchange.Nina Gierasimczuk & Jakub Szymanik - 2011 - 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 (...)
    Direct download  
    Translate
     
     
    Export citation  
     
    Bookmark   4 citations  
  25.  10
    Branching Quantification V. Two-Way Quantification: Articles.Nina Gierasimczuk & Jakub Szymanik - 2009 - Journal of Semantics 26 (4):367-392.
    We discuss the thesis formulated by Hintikka 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  
     
    Export citation  
     
    Bookmark   5 citations  
  26.  53
    A Remark on Collective Quantification.Juha Kontinen & Jakub Szymanik - 2008 - 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 (8 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  27.  51
    A Note on a Generalization of the Muddy Children Puzzle.Nina Gierasimczuk & Jakub Szymanik - 2011 - 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 (...)
    Direct download  
    Translate
     
     
    Export citation  
     
    Bookmark   3 citations  
  28.  52
    Computational Semantics for Monadic Quantifiers.Marcin Mostowski - 1998 - Journal of Applied Non--Classical Logics 8 (1-2):107--121.
    The paper gives a survey of known results related to computational devices (finite and push–down automata) recognizing monadic generalized quantifiers in finite models. Some of these results are simple reinterpretations of descriptive—feasible correspondence theorems from finite–model theory. Additionally a new result characterizing monadic quantifiers recognized by push down automata is proven.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  29.  17
    On the Identification of Quantifiers' Witness Sets: A Study of Multi-Quantifier Sentences.Livio Robaldo, Jakub Szymanik & Ben Meijering - 2014 - 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 (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  30.  68
    Hintikka's Thesis Revisited.Nina Gierasimczuk & Jakub Szymanik - 2007 - 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)  
     
    Export citation  
     
    Bookmark   3 citations  
  31.  15
    Computational Semantics for Monadic Quantifiers.Marcin Mostowski - 1998 - Journal of Applied Non-Classical Logics 8 (1-2):107-121.
    ABSTRACT This paper gives a survey of known results related to computational devices recognising monadic generalised quantifiers infinite models. Some of these results are simple reinterpretations of descriptive-feasible correspondence theorems from finite-model theory. Additionally a new result characterizing monadic quantifiers recognized by push down automata is proven.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  32.  14
    Divisibility Quantifiers.Marcin Mostowski - 1991 - Bulletin of the Section of Logic 20 (2):67-70.
  33.  4
    Ease of Learning Explains Semantic Universals.Shane Steinert-Threlkeld & Jakub Szymanik - 2020 - Cognition 195:104076.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  34.  51
    Characterizing Definability of Second-Order Generalized Quantifiers.Juha Kontinen & Jakub Szymanik - 2011 - 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 (...)
    Direct download  
    Translate
     
     
    Export citation  
     
    Bookmark   1 citation  
  35.  14
    Logic and Cognition: Special Issue of Best Papers of the ESSLLI 2012 Workshop.Jakub Szymanik & Rineke Verbrugge - 2013 - 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 (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  36.  30
    Pragmatic Identification of the Witness Sets.Livio Robaldo & Jakub Szymanik - 2012 - 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 (...)
    Direct download  
    Translate
     
     
    Export citation  
     
    Bookmark   1 citation  
  37.  42
    On theTractability of Comparing Informational Structures.Cédric Dégremont, Lena Kurzen & Jakub Szymanik - 2011 - In J. van Eijck & R. Verbrugge (eds.), Proceedings of the Workshop 'Reasoning about other minds: Logical and cognitive perspectives.
  38.  24
    Pure Logic with Branched Quantifiers.Marcin Mostowski - 1989 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 35 (1):45-48.
  39.  84
    Logic in Cognitive Science: Bridging the Gap Between Symbolic and Connectionist Paradigms.Alistair Isaac & Jakub Szymanik - 2010 - 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)  
     
    Export citation  
     
    Bookmark  
  40.  13
    Recursive Complexity of the Carnap First Order Modal Logic C.Amélie Gheerbrant & Marcin Mostowski - 2006 - Mathematical Logic Quarterly 52 (1):87-94.
    We consider first order modal logic C firstly defined by Carnap in “Meaning and Necessity” [1]. We prove elimination of nested modalities for this logic, which gives additionally the Skolem-Löwenheim theorem for C. We also evaluate the degree of unsolvability for C, by showing that it is exactly 0′. We compare this logic with the logics of Henkin quantifiers, Σ11 logic, and SO. We also shortly discuss properties of the logic C in finite models.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  41.  14
    Pure Logic with Branched Quantifiers.Marcin Mostowski - 1989 - Mathematical Logic Quarterly 35 (1):45-48.
  42.  49
    Almost All Complex Quantifiers Are Simple.Jakub Szymanik - 2010 - 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. -/- .
    Direct download  
    Translate
     
     
    Export citation  
     
    Bookmark  
  43. The Computational Complexity of Quantified Reciprocals.Jakub Szymanik - 2009 - 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
     
     
    Export citation  
     
    Bookmark  
  44.  14
    On Representing Semantics in Finite Models.Marcin Mostowski - 2003 - In A. Rojszczak, J. Cachro & G. Kurczewski (eds.), Philosophical Dimensions of Logic and Science. Kluwer Academic Publishers. pp. 15--28.
    Direct download  
     
    Export citation  
     
    Bookmark  
  45.  26
    Books Received. [REVIEW]Janusz Czelakowski, Alasdair Urquhart, Ryszard Wójcicki, Jan Woleński, Andrzej Sendlewski & Marcin Mostowski - 1990 - Studia Logica 49 (1):151-161.
  46. O hipotezie Bar-Hillela.Tadeusz Ciecierski & Jakub Szymanik - 2004 - Studia Semiotyczne 25:201-212.
    Translate
     
     
    Export citation  
     
    Bookmark  
  47. Problemy z formą logiczną.Jakub Szymanik - 2004 - Studia Semiotyczne 25:187-200.
    Translate
     
     
    Export citation  
     
    Bookmark  
  48. Semantyka obliczeniowa dla kwantyfikatorów monadycznych w języku naturalnym.Jakub Szymanik - 2007 - Studia Semiotyczne 26:219-244.
    Translate
     
     
    Export citation  
     
    Bookmark  
  49.  15
    Computational Complexity of the Semantics of Some Natural Language Constructions.Marcin Mostowski & Dominika Wojtyniak - 2004 - Annals of Pure and Applied Logic 127 (1-3):219--227.
    We consider an example of a sentence which according to Hintikka's claim essentially requires for its logical form a Henkin quantifier. We show that if Hintikka is right then recognizing the truth value of the sentence in finite models is an NP-complete problem. We discuss also possible conclusions from this observation.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  50.  15
    On Representing Concepts in Finite Models.Marcin Mostowski - 2001 - Mathematical Logic Quarterly 47 (4):513-523.
    We present a method of transferring Tarski's technique of classifying finite order concepts by means of truth-definitions into finite mode theory. The other considered question is the problem of representability relations on words or natural numbers in finite models. We prove that relations representable in finite models are exactly those which are of degree ≤ o′. Finally, we consider theories of sufficiently large finite models. For a given theory T we define sl as the set of all sentences true in (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
1 — 50 / 1000