18 found
Order:
Disambiguations:
Marcin Mostowski [16]M. Mostowski [11]
  1.  98
    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)  
     
    Export citation  
     
    My bibliography   3 citations  
  2. M. Mostowski (forthcoming). The Logic of Divisibility. Journal of Symbolic Logic.
     
    Export citation  
     
    My bibliography   2 citations  
  3.  53
    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
      Direct download (3 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  4.  39
    Marcin Mostowski (1998). Computational Semantics for Monadic Quantifiers. 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 (4 more)  
     
    Export citation  
     
    My bibliography   4 citations  
  5.  8
    Marcin Mostowski (1991). Divisibility Quantifiers. Bulletin of the Section of Logic 20 (2):67-70.
    Direct download  
     
    Export citation  
     
    My bibliography   4 citations  
  6.  2
    A. E. Wasilewska & M. Mostowski (2004). Arithmetic of Divisibility in Finite Models. Mathematical Logic Quarterly 50 (2):169.
    We prove that the finite-model version of arithmetic with the divisibility relation is undecidable . Additionally we prove FM-representability theorem for this class of finite models. This means that a relation R on natural numbers can be described correctly on each input on almost all finite divisibility models if and only if R is of degree ≤0′. We obtain these results by interpreting addition and multiplication on initial segments of finite models with divisibility only.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  7.  15
    Marcin Mostowski & Konrad Zdanowski (2004). Degrees of Logics with Henkin Quantifiers in Poor Vocabularies. 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 (4 more)  
     
    Export citation  
     
    My bibliography  
  8.  9
    Marcin Mostowski Jakub Szymanik & M. Mostowski (2007). Computational Complexity of Some Ramsey Quantifiers in Finite Models. Bulletin of Symbolic Logic 13:281-282.
    Direct download  
     
    Export citation  
     
    My bibliography  
  9.  1
    Marcin Mostowski & Jakub Szymanik (2012). Semantic Bounds for Everyday Language. Semiotica 2012 (188).
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  10.  4
    Marcin Mostowski (1989). Pure Logic with Branched Quantifiers. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 35 (1):45-48.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  11.  9
    Marcin Mostowski (2003). On Representing Semantics in Finite Models. In A. Rojszczak, J. Cachro & G. Kurczewski (eds.), Philosophical Dimensions of Logic and Science. Kluwer Academic Publishers 15--28.
    Direct download  
     
    Export citation  
     
    My bibliography  
  12.  2
    Marcin Mostowski (1998). Computational Semantics for Monadic Quantifiers. Journal of Applied Non-Classical Logics 8 (1-2):107-121.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  13.  4
    Amélie Gheerbrant & Marcin Mostowski (2006). Recursive Complexity of the Carnap First Order Modal Logic C. 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.
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  14.  5
    Michał Krynicki & Marcin Mostowski (1992). Decidability Problems in Languages with Henkin Quantifiers. 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 φ,...,f). (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  15.  1
    Marcin Mostowski (1989). Pure Logic with Branched Quantifiers. Mathematical Logic Quarterly 35 (1):45-48.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  16.  16
    Janusz Czelakowski, Alasdair Urquhart, Ryszard Wójcicki, Jan Woleński, Andrzej Sendlewski & Marcin Mostowski (1990). Books Received. [REVIEW] Studia Logica 49 (1):151-161.
  17. X. Li, M. Mostowski, K. Zdanowski, Mr Burke & M. Kada (2004). M. RUBIN On La Ia Complete Extensions of Complete Theories of Boolean Algebras 571 A. ROStANOWSKI• S. SHELAH Sweet & Sour and Other Flavours of Ccc Forcing. [REVIEW] Archive for Mathematical Logic 43 (5):720.
     
    Export citation  
     
    My bibliography  
  18.  9
    Marcin Mostowski & Dominika Wojtyniak (2004). Computational Complexity of the Semantics of Some Natural Language Constructions. 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  
     
    My bibliography   6 citations