Haifa Logic Seminar

Location

Time

Program Spring 1997

• March 6, 1997:
  Organizational Meeting
  Fairwell party for Eric Rosen

  ---

• March 13, 1997:
  J.A. Makowsky
  On Computationally Sound Proofs (1st lecture)
  Paper by S. Micali

  ---

• March 27, 1997:
  M. de Rougemont(Paris)
  Average complexity of graph reliability

  ---

• April 1, 1997: Exceptional: Fishbach 413, 14:30
  R. Fagin (IBM Research)
  Finite-Model Theory - a Personal Perspective

  ---

• April 1, 1997: Exceptional: Haifa University, Eshkol 1420, 16:30
  E. Hrushovski (The Hebrew University)
  A Lefschetz principle with Frobenius maps

  ---

• April 3, 1997:
  K. Peterzil
  O-minimal structures: A Survey with focus on geometric model theory
  Lecture also given at the Workshop on Model Theory of Analytic Functions at the Fields Institute for Research in Mathematical Sciences, March 17-21, 1997 in Toronto.

  ---

• April 10, 1997:
  E. Kushilevitz
  On Interactive Proofs: A Tutorial
  Background to Computationally Sound Proofs by S. Micali.

  ---

• April 17, 1997:
  No seminar session
  

  ---

  PESSACH VACATION April 18- April 28

  ---

• May 1, 1997
  J.A. Makowsky
  On the Consequence Problem of formulas arising in Database Theory, 1977-1997. Has the last word been said ?
  Papers of Chandra-Lewis-Makowsky (1980), Beeri-Vardi (1980), Chandra-Vardi (1983), Mitchell (1983), Herrmann (1995).
  

  ---

• May 8, 1997 NEW:
  J.A. Makowsky
  Continuation: On the Consequence Problem of formulas arising in Database Theory, 1977-1997. Has the last word been said ?
  see previous week
  

  ---

• May 15, 1997 NEW:
  Michael Kaminski
  Open Default Theories
  after M. Kaminski, J.A. Makowsky and M. Tiomkin, Extensions for open default theories via the domain closure assumption. (Extended Abstract) Proceedings of the 5th European Workshop on Logics in AI - JELIA'96, Evora, Portugal, September 30th - October 4th 1996.
  

  ---

• May 22, 1997 NEW:
  Yuri Gurevich
  Choiceless Polynomial Time
  We give the richest (to date) Polynomial Time Logic. Paper in preparation with Andreas Blass and Saharon Shelah Choice-less Polynomial Time
  Abstract: A central open question in finite model theory is whether there exists a logic that captures polynomial time (without presuming the presence of a linear order). Earlier, one of us conjectured the negative answer for the question. The question of how much of polynomial time can be captured led to a quest for stronger and stronger PTime logics. All these logics avoid arbitrary choice. Here we attempt to capture the choice-less fragment of PTime. Our logic (formalized by means of abstract state machines (formerly called evolving algebras) with set-theoretic underlying structures) is more expressive than other PTime logics in the literature. The only difficult theorem shows that the logic does not capture all PTime.
  
  

  ---

• May 29, 1997 NEW:
  Michael Kaminski
  Open Default Theories (continuation)
  

  ---

• June 5, 1997 NEW:
  David Buchman
  The Algebra of Modal Logic
  (after P. Blackburn, M. de Rijke and Y. Venema)

  ---

  Shavuoth, Chag Sameach

  ---

• June 19 (or 26), 1997 NEW:
  David Buchman (continuation)
  The Algebra of Modal Logic

  ---

  End of Semester, Seminar resumes in October 1997

  ---

Previous programs

Program Winter/Spring 1996-97

• October 20, 1996:
  E. Ravve
  Partially Selfconsistent Problems for Frege Systems
  (papers by S. Cook and S. Buss)

  ---

• October 27, 1996
  Continuation from October 20.

  ---

• November 3, 1996
  V. Harnik
  The analogy between primitive recursive and polynomial time computable
  (Papers by Cobham, Cook and S. Buss)

  ---

• November 10, 1996
  K. Peterzil
  New Results on O-minimality
  (Recent paper by Wilkie)

  ---

• November 17, 1996
  K. Peterzil
  Continuation from November 3, 1996

  ---

• November 24, 1996
  K. Peterzil
  Continuation from November 17, 1996

  ---

• December 1, 1996
  J. A. Makowsky
  On invariantly definable relations.
  (Draft paper by E. Rosen and J.A. Makowsky)

  ---

  Chanukkah break

  No seminar on December 8 and December 15

  ---

• December 22, 1996
  J. A. Makowsky
  On invariantly definable relations
  Repetition and continuation (selfcontained)

  ---

• December 29, 1996
  J. A. Makowsky
  Definable sets in arithmetic without multiplication
  For details see proposed topics below.

  ---

• January 5, 1996
  Peter Komjath (Budapest)
  On partition relations

  ---

• January 12, 1997
  Eric Rosen
  Finite models, stability and Ramsey's theorem
  (Paper of R. Grosberg and D. Ensley)

  ---

  Semester break

  No seminar till resumption of the Spring Semester

  Seminar resumes on March 6, 1997 with regular meetings on THURSDAYS at 10:00-12:00 at the usual place: Technion, Fishbach Building, room 461.

  ---

• March 6, 1997
  To be announced

  ---

• March 13, 1997
  To be announced

Proposed topics

• Speakers: J.A. Makowsky and N.N.
  Definable sets in arithmetic without multiplication
  This topic links automata theory, number theory and first order and second order definability theory.
  References:
  1. P.T. Bateman, C.G. Jokusch and A. Woods, Decidability and undecidability of theories with a predicate for the primes, JSL 58.2 (1994), pp. 672ff
  2. R. Villemaire, The theory of (N, +, V_k, V_l ) is undecidable, Theoretical Computer Science 106 (1992) pp. 337-349.
  3. C. Michaux and R. Villemaire, Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems, APAL 77 (1995) pp. 251-277
• Speakers: E. Rosen, S. Ben-David
  Definability, Indiscernibles and VC-dimension (papers by Grossberg, Shelah, Turan et al.)
• Speaker: N.N.
  0-1 Laws for various Logics