Logic in Computer Science (LICS 1995)

Paper: Finitely Monotone Properties (at LICS 1995)

Authors: Alexei P. Stolboushkin

Abstract

A characterization of definability by positive first order formulas in terms of Fraisse-Ehrenfeucht-like games is developed. Using this characterization, an elementary, purely combinatorial, proof of the failure of Lyndon's Lemma (that every monotone first order property is expressible positively) for finite models is given. The proof implies that first order logic is a bad candidate to the role of uniform version of positive Boolean circuits of constant depth and polynomial size. Although Lyndon's Lemma fails for finite models, some similar characterization may be established for finitely monotone properties, and we formulate a particular open problem in this direction.

BibTeX

  @InProceedings{Stolboushkin-FinitelyMonotonePro,
    author = 	 {Alexei P. Stolboushkin},
    title = 	 {Finitely Monotone Properties},
    booktitle =  {Proceedings of the Tenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1995},
    year =	 1995,
    editor =	 {Dexter Kozen},
    month =	 {June}, 
    pages =      {324-352},
    location =   {San Diego, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }