18 found
Order:
  1.  25
    Heikki Mannila and Kari-Jouko Räihä. The Design of Relational Databases. Addison-Wesley Publishing Company, Wokingham, England, and Reading, Mass., Etc., 1992, Vii + 318 Pp. - Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley Publishing Company, Reading, Mass., Etc., 1995, Xviii + 685 Pp. - Paris C. Kanellakis. Elements of Relational Database Theory. Handbook of Theoretical Computer Science, Volume B, Formal Models and Semantics, Edited by Jan van Leeuwen, Elsevier, Amsterdam, Etc., and The MIT Press, Cambridge, Mass., 1990, Pp. 1073–1156. [REVIEW]J. A. Makowsky - 1997 - Journal of Symbolic Logic 62 (1):324-326.
  2.  18
    Jeffrey D. Ullman. Principles of Database Systems. Second Edition. Computer Software Engineering Series. Computer Science Press, Rockville, Md., 1982, Vii + 484 Pp. - David Maier. The Theory of Relational Databases. Computer Science Press, Rockville, Md., 1983, Xv + 637 Pp. - Ashok K. Chandra and David Harel. Computable Queries for Relational Data Bases. Journal of Computer and System Sciences, Vol. 21 , Pp. 156–178. [REVIEW]J. A. Makowsky - 1986 - Journal of Symbolic Logic 51 (4):1079-1084.
  3.  7
    A Logician's View of Graph Polynomials.J. A. Makowsky, E. V. Ravve & T. Kotek - 2019 - Annals of Pure and Applied Logic 170 (9):1030-1069.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  4.  9
    Algorithmic Uses of the Feferman–Vaught Theorem.J. A. Makowsky - 2004 - Annals of Pure and Applied Logic 126 (1-3):159-213.
    The classical Feferman–Vaught Theorem for First Order Logic explains how to compute the truth value of a first order sentence in a generalized product of first order structures by reducing this computation to the computation of truth values of other first order sentences in the factors and evaluation of a monadic second order sentence in the index structure. This technique was later extended by Läuchli, Shelah and Gurevich to monadic second order logic. The technique has wide applications in decidability and (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  5.  7
    Positive Results in Abstract Model Theory: A Theory of Compact Logics.J. A. Makowsky & S. Shelah - 1983 - Annals of Pure and Applied Logic 25 (3):263-299.
    We prove that compactness is equivalent to the amalgamation property, provided the occurrence number of the logic is smaller than the first uncountable measurable cardinal. We also relate compactness to the existence of certain regular ultrafilters related to the logic and develop a general theory of compactness and its consequences. We also prove some combinatorial results of independent interest.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  6.  5
    Jan Paredaens, Paul de Bra, Marc Gyssens, and Dirk van Gucht. The Structure of the Relational Database Model. EATCS Monographs on Theoretical Computer Science, Vol. 17. Springer-Verlag, Berlin, Heidelberg, New York, Etc., 1989, X + 231 Pp. [REVIEW]J. A. Makowsky - 1992 - Journal of Symbolic Logic 57 (2):759-760.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  7.  6
    Arity and Alternation in Second-Order Logic.J. A. Makowsky & Y. B. Pnueli - 1996 - Annals of Pure and Applied Logic 78 (1-3):189-202.
    We investigate the expressive power of second-order logic over finite structures, when two limitations are imposed. Let SAA ) be the set of second-order formulas such that the arity of the relation variables is bounded by k and the number of alternations of second-order quantification is bounded by n . We show that this imposes a proper hierarchy on second-order logic, i.e. for every k , n there are problems not definable in AA but definable in AA for some c (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  8.  44
    On Spectra of Sentences of Monadic Second Order Logic with Counting.E. Fischer & J. A. Makowsky - 2004 - Journal of Symbolic Logic 69 (3):617-640.
    We show that the spectrum of a sentence ϕ in Counting Monadic Second Order Logic (CMSOL) using one binary relation symbol and finitely many unary relation symbols, is ultimately periodic, provided all the models of ϕ are of clique width at most k, for some fixed k. We prove a similar statement for arbitrary finite relational vocabularies τ and a variant of clique width for τ-structures. This includes the cases where the models of ϕ are of tree width at most (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  9.  19
    Completeness Theorems For Modal Model Theory With the Montague-Chang Semantics I.J. A. Makowsky & A. Marcja - 1977 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 23 (7-12):97-104.
  10.  21
    Finitary Sketches.J. Adámek, P. T. Johnstone, J. A. Makowsky & J. Rosický - 1997 - Journal of Symbolic Logic 62 (3):699-707.
    Finitary sketches, i.e., sketches with finite-limit and finite-colimit specifications, are proved to be as strong as geometric sketches, i.e., sketches with finite-limit and arbitrary colimit specifications. Categories sketchable by such sketches are fully characterized in the infinitary first-order logic: they are axiomatizable by σ-coherent theories, i.e., basic theories using finite conjunctions, countable disjunctions, and finite quantifications. The latter result is absolute; the equivalence of geometric and finitary sketches requires (in fact, is equivalent to) the non-existence of measurable cardinals.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  11.  10
    Completeness Theorems For Modal Model Theory With the Montague‐Chang Semantics I.J. A. Makowsky & A. Marcja - 1976 - Mathematical Logic Quarterly 23 (7‐12):97-104.
  12.  15
    Review: Jeffrey D. Ullman, Principles of Database Systems; David Maier, The Theory of Relational Databases; Ashok K. Chandra, David Harel, Computable Queries for Relational Data Bases. [REVIEW]J. A. Makowsky - 1986 - Journal of Symbolic Logic 51 (4):1079-1084.
  13.  14
    Review: Heikki Mannila, Kari-Jouko Raiha, The Design of Relational Databases; Serge Abiteboul, Richard Hull, Victor Vianu, Foundations of Databases; Paris C. Kanellakis, Jan van Leeuwen, Elements of Relational Database Theory. [REVIEW]J. A. Makowsky - 1997 - Journal of Symbolic Logic 62 (1):324-326.
  14.  22
    Vopěnka's Principle and Compact Logics.J. A. Makowsky - 1985 - Journal of Symbolic Logic 50 (1):42-48.
    We study the effects of Vopěnka's principle on properties of model theoretic logics. We show that Vopěnka's principle is equivalent to the assumption that every finitely generated logic has a compact cardinal. We show also that it is equivalent to the assumption that every such logic has a global Hanf number.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark  
  15.  5
    On Spectra of Sentences of Monadic Second Order Logic with Counting. E. Fischer & J. A. Makowsky - 2004 - Journal of Symbolic Logic 69 (3):617-640.
    We show that the spectrum of a sentence φ in Counting Monadic Second Order Logic using one binary relation symbol and finitely many unary relation symbols, is ultimately periodic, provided all the models of φ are of clique width at most k, for some fixed k. We prove a similar statement for arbitrary finite relational vocabularies τ and a variant of clique width for τ-structures. This includes the cases where the models of φ are of tree width at most k. (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  16. Review: Jan Paredaens, Paul De Bra, Marc Gyssens, Dirk Van Gucht, The Structure of the Relational Database Model. [REVIEW]J. A. Makowsky - 1992 - Journal of Symbolic Logic 57 (2):759-760.
  17.  14
    On the Existence of Polynomial Time Algorithms for Interpolation Problems in Propositional Logic.E. Dahlhaus, A. Israeli & J. A. Makowsky - 1988 - Notre Dame Journal of Formal Logic 29 (4):497-509.
  18.  1
    Δ-Logics and Generalized Quantifiers.J. A. Makowsky, Saharon Shelah & Jonathan Stavi - 1985 - Journal of Symbolic Logic 50 (1):241-242.
    Direct download  
     
    Export citation  
     
    Bookmark