10 found
Sort by:
  1. 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  
  2. 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  
  3. 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)  
     
    My bibliography  
     
    Export citation  
  4. 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)  
     
    My bibliography  
     
    Export citation  
  5. 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 (2 more)  
     
    My bibliography  
     
    Export citation  
  6. 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)  
     
    My bibliography  
     
    Export citation  
  7. 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)  
     
    My bibliography  
     
    Export citation  
  8. Marcin Mostowski (1991). Divisibility Quantifiers. Bulletin of the Section of Logic 20 (2):67-70.
    Direct download  
     
    My bibliography  
     
    Export citation  
  9. Janusz Czelakowski, Alasdair Urquhart, Ryszard Wójcicki, Jan Woleński, Andrzej Sendlewski & Marcin Mostowski (1990). Books Received. [REVIEW] Studia Logica 49 (1):151-161.
  10. Marcin Mostowski (1989). Pure Logic with Branched Quantifiers. Mathematical Logic Quarterly 35 (1):45-48.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation