Lics

IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Tenth Annual IEEE Symposium on

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 Symposium on Logic in Computer Science (LICS 1995)},
    year =	 {1995},
    month =	 {June}, 
    pages =      {324--352},
    location =   {San Diego, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }
   

Last modified: 2017-04-0512:37
Andrzej Murawski