19 found
Order:
Disambiguations
Marcin Mostowski [16]M. Mostowski [11]
  1. 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  
  2.  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  
  3. The Logic of Divisibility.M. Mostowski - unknown
  4.  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  
  5.  71
    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 computational (...)
    Direct download (2 more)  
    Translate
     
     
    Export citation  
     
    Bookmark   2 citations  
  6.  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  
  7.  14
    Divisibility Quantifiers.Marcin Mostowski - 1991 - Bulletin of the Section of Logic 20 (2):67-70.
  8.  14
    Arithmetic of Divisibility in Finite Models.A. E. Wasilewska & M. Mostowski - 2004 - 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  
     
    Bookmark   2 citations  
  9.  24
    Pure Logic with Branched Quantifiers.Marcin Mostowski - 1989 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 35 (1):45-48.
  10.  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  
  11.  13
    Pure Logic with Branched Quantifiers.Marcin Mostowski - 1989 - Mathematical Logic Quarterly 35 (1):45-48.
  12.  10
    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 φ,...,f). (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  13.  24
    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  
  14.  15
    Computational Complexity of Some Ramsey Quantifiers in Finite Models.Marcin Mostowski Jakub Szymanik & M. Mostowski - 2007 - Bulletin of Symbolic Logic 13:281-282.
  15.  25
    Books Received. [REVIEW]Janusz Czelakowski, Alasdair Urquhart, Ryszard Wójcicki, Jan Woleński, Andrzej Sendlewski & Marcin Mostowski - 1990 - Studia Logica 49 (1):151-161.
  16.  13
    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  
  17. 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]X. Li, M. Mostowski, K. Zdanowski, Mr Burke & M. Kada - 2004 - Archive for Mathematical Logic 43 (5):720.
  18.  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  
  19.  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