Works by Rosen, Eric (exact spelling)

7 found
Order:
  1.  31
    Modal Logic Over Finite Structures.Eric Rosen - 1997 - Journal of Logic, Language and Information 6 (4):427-439.
    We investigate properties of propositional modal logic over the classof finite structures. In particular, we show that certain knownpreservation theorems remain true over this class. We prove that aclass of finite models is defined by a first-order sentence and closedunder bisimulations if and only if it is definable by a modal formula.We also prove that a class of finite models defined by a modal formulais closed under extensions if and only if it is defined by a -modal formula.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  2.  19
    Undecidability Results on Two-Variable Logics.Erich Grädel, Martin Otto & Eric Rosen - 1999 - Archive for Mathematical Logic 38 (4-5):313-354.
    It is a classical result of Mortimer that $L^2$ , first-order logic with two variables, is decidable for satisfiability. We show that going beyond $L^2$ by adding any one of the following leads to an undecidable logic:– very weak forms of recursion, viz.¶(i) transitive closure operations¶(ii) (restricted) monadic fixed-point operations¶– weak access to cardinalities, through the Härtig (or equicardinality) quantifier¶– a choice construct known as Hilbert's $\epsilon$ -operator.In fact all these extensions of $L^2$ prove to be undecidable both for satisfiability, (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  3.  10
    On Preservation Theorems for Two-Variable Logic.Erich Gradel & Eric Rosen - 1999 - Mathematical Logic Quarterly 45 (3):315-325.
    We show that the existential preservation theorem fails for two-variable first-order logic FO2. It is known that for all k ≥ 3, FOk does not have an existential preservation theorem, so this settles the last open case, answering a question of Andreka, van Benthem, and Németi. In contrast, we prove that the homomorphism preservation theorem holds for FO2.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  4.  70
    An Existential Fragment of Second Order Logic.Eric Rosen - 1999 - Archive for Mathematical Logic 38 (4-5):217-234.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  5.  44
    Some Aspects of Model Theory and Finite Structures.Eric Rosen - 2002 - Bulletin of Symbolic Logic 8 (3):380-403.
  6.  29
    On the First-Order Prefix Hierarchy.Eric Rosen - 2005 - Notre Dame Journal of Formal Logic 46 (2):147-164.
    We investigate the expressive power of fragments of first-order logic that are defined in terms of prefixes. The main result establishes a strict hierarchy among these fragments over the signature consisting of a single binary relation. It implies that for each prefix p, there is a sentence in prenex normal form with prefix p, over a single binary relation, such that for all sentences θ in prenex normal form, if θ is equivalent to , then p can be embedded in (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark  
  7.  14
    SO(∀∃^*) Sentences and Their Asymptotic Probabilities.Eric Rosen & Jerzy Tyszkiewicz - 2000 - Mathematical Logic Quarterly 46 (4):435-452.
    We prove a 0-1 law for the fragment of second order logic SO over parametric classes of finite structures which allow only one unary atomic type. This completes the investigation of 0-1 laws for fragments of second order logic defined in terms of first order quantifier prefixes over, e.g., simple graphs and tournaments. We also prove a low oscillation law, and establish the 0-1 law for Σ14 without any restriction on the number of unary types.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark