21 found
Order:
  1. On Topological Spaces Equivalent to Ordinals.Jörg Flum & Juan Carlos Martinez - 1988 - Journal of Symbolic Logic 53 (3):785-795.
    Let L be one of the topological languages L t , (L ∞ω ) t and (L κω ) t . We characterize the topological spaces which are models of the L-theory of the class of ordinals equipped with the order topology. The results show that the role played in classical model theory by the property of being well-ordered is taken over in the topological context by the property of being locally compact and scattered.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark  
  2.  10
    On Optimal Inverters.Yijia Chen & Jörg Flum - 2014 - Bulletin of Symbolic Logic 20 (1):1-23.
  3.  9
    Jerome Malitz. Universal Classes in Infinitary Languages. Duke Mathematical Journal, Vol. 36 , Pp. 621–630.Jörg Flum - 1974 - Journal of Symbolic Logic 39 (2):336.
  4.  31
    Strong Isomorphism Reductions in Complexity Theory.Sam Buss, Yijia Chen, Jörg Flum, Sy-David Friedman & Moritz Müller - 2011 - Journal of Symbolic Logic 76 (4):1381-1402.
    We give the first systematic study of strong isomorphism reductions, a notion of reduction more appropriate than polynomial time reduction when, for example, comparing the computational complexity of the isomorphim problem for different classes of structures. We show that the partial ordering of its degrees is quite rich. We analyze its relationship to a further type of reduction between classes of structures based on purely comparing for every n the number of nonisomorphic structures of cardinality at most n in both (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  5.  33
    R. G. Downey and M. R. Fellows. Parameterized Complexity. Monographs in Computer Science. Springer, New York, Berlin, and Heidelberg, 1999, Xv + 533 Pp. [REVIEW]Jörg Flum - 2002 - Bulletin of Symbolic Logic 8 (4):528-529.
  6.  5
    The Parameterized Complexity of Maximality and Minimality Problems.Yijia Chen & Jörg Flum - 2008 - Annals of Pure and Applied Logic 151 (1):22-61.
    Many parameterized problems ask, given an instance and a natural number k as parameter, whether there is a solution of size k. We analyze the relationship between the complexity of such a problem and the corresponding maximality problem asking for a solution of size k maximal with respect to set inclusion. As our results show, many maximality problems increase the parameterized complexity, while “in terms of the W-hierarchy” minimality problems do not increase the complexity. We also address the corresponding construction, (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  7.  31
    Consistency, Optimality, and Incompleteness.Yijia Chen, Jörg Flum & Moritz Müller - 2013 - Annals of Pure and Applied Logic 164 (12):1224-1235.
    Assume that the problem P0 is not solvable in polynomial time. Let T be a first-order theory containing a sufficiently rich part of true arithmetic. We characterize T∪{ConT} as the minimal extension of T proving for some algorithm that it decides P0 as fast as any algorithm B with the property that T proves that B decides P0. Here, ConT claims the consistency of T. As a byproduct, we obtain a version of Gödelʼs Second Incompleteness Theorem. Moreover, we characterize problems (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  8.  36
    A Remark on Infinitary Languages.Jörg Flum - 1971 - Journal of Symbolic Logic 36 (3):461-462.
  9.  19
    On Fixed-Point Logic with Counting.Jörg Flum & Martin Grohe - 2000 - Journal of Symbolic Logic 65 (2):777-787.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  10.  29
    L(Q)-Preservation Theorems.Jörg Flum - 1975 - Journal of Symbolic Logic 40 (3):410-418.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark  
  11.  29
    An Analysis of the W -Hierarchy.Yijia Chen, Jörg Flum & Martin Grohe - 2007 - Journal of Symbolic Logic 72 (2):513 - 534.
    We observe that the W*-hierarchy, a variant (introduced by Downey, Fellows, and Taylor [7]) of the better known W-hierarchy, coincides with the W-hierarchy, though not level wise, but just as a whole hierarchy. More precisely, we prove that W[t] ⊆ W*[t] ⊆ W[2t − 2] for each t ≥ 2. It was known before that W[1] = W*[1] and W[2] = W*[2]. Our second main result is a new logical characterization of the W*-hierarchy in terms of "Fagin-definable problems." As a (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  12.  23
    Pseudo-Finite Homogeneity and Saturation.Jörg Flum & Martin Ziegler - 1999 - Journal of Symbolic Logic 64 (4):1689-1699.
    When analyzing database query languages a roperty, of theories, the pseudo-finite homogeneity property, has been introduced and applied (cf. [3]). We show that a stable theory has the pseudo-finite homogeneity property just in case its expressive power for finite states is bounded. Moreover, we introduce the corresponding pseudo-finite saturation property and show that a theory fails to have the finite cover property if and only if it has the pseudo-finite saturation property.
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark  
  13.  28
    Quantifiers and Congruence Closure.Jörg Flum, Matthias Schiehlen & Jouko Väänänen - 1999 - Studia Logica 62 (3):315-340.
    We prove some results about the limitations of the expressive power of quantifiers on finite structures. We define the concept of a bounded quantifier and prove that every relativizing quantifier which is bounded is already first-order definable (Theorem 3.8). We weaken the concept of congruence closed (see [6]) to weakly congruence closed by restricting to congruence relations where all classes have the same size. Adapting the concept of a thin quantifier (Caicedo [1]) to the framework of finite structures, we define (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark  
  14. Maximale monadische Logiken.Jörg Flum - 1985 - Archive for Mathematical Logic 25 (1):145-152.
    No categories
    Translate
     
     
    Export citation  
     
    Bookmark  
  15.  8
    Hard Instances of Algorithms and Proof Systems.Yijia Chen, Jörg Flum & Moritz Müller - 2012 - In S. Barry Cooper (ed.), How the World Computes. pp. 118--128.
  16.  16
    Review: R. G. Downey, M. R. Fellows, Parameterized Complexity. [REVIEW]Jörg Flum - 2002 - Bulletin of Symbolic Logic 8 (4):528-529.
  17.  16
    On the Complexity of Gödel's Proof Predicate.Yijia Chen & Jörg Flum - 2010 - Journal of Symbolic Logic 75 (1):239-254.
    The undecidability of first-order logic implies that there is no computable bound on the length of shortest proofs of valid sentences of first-order logic. Some valid sentences can only have quite long proofs. How hard is it to prove such "hard" valid sentences? The polynomial time tractability of this problem would imply the fixed-parameter tractability of the parameterized problem that, given a natural number n in unary as input and a first-order sentence φ as parameter, asks whether φ has a (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark  
  18.  7
    Bounded Fixed-Parameter Tractability and Reducibility.Rod Downey, Jörg Flum, Martin Grohe & Mark Weyer - 2007 - Annals of Pure and Applied Logic 148 (1):1-19.
    We study a refined framework of parameterized complexity theory where the parameter dependence of fixed-parameter tractable algorithms is not arbitrary, but restricted by a function in some family . For every family of functions, this yields a notion of -fixed-parameter tractability. If is the class of all polynomially bounded functions, then -fixed-parameter tractability coincides with polynomial time decidability and if is the class of all computable functions, -fixed-parameter tractability coincides with the standard notion of fixed-parameter tractability. There are interesting choices (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  19.  4
    An Extension of the Lemma of Rasiowa and Sikorski.Jörg Flum - 1998 - Mathematical Logic Quarterly 44 (4):509-514.
    We prove an extension of the Lemma of Rasiowa and Sikorski and give some applications. Moreover, we analyze the relationship to corresponding results on the omission of types.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  20.  4
    Model Theory of Topological Structures.Jörg Flum - 1995 - In M. Krynicki, M. Mostowski & L. Szczerba (eds.), Quantifiers: Logics, Models and Computation. Kluwer Academic Publishers. pp. 297--312.
    Direct download  
     
    Export citation  
     
    Bookmark  
  21.  4
    Review: Jerome Malitz, Universal Classes in Infinitary Languages. [REVIEW]Jorg Flum - 1974 - Journal of Symbolic Logic 39 (2):336-336.