Paper: More about recursive structures: descriptive complexity and zero-one laws (at LICS 1996)

Authors: Tirza Hirst David Harel

Abstract

This paper continues our work on infinite, recursive structures. We investigate the descriptive complexity of several logics over recursive structures, including first-order, second-order, and fixpoint logic, exhibiting connections between expressibility of a property and its computational complexity. We then address 0-1 laws, proposing a version that applies to recursive structures and using it to prove several non-expressibility results.

BibTeX

  @InProceedings{HirstHarel-Moreaboutrecursives,
    author = 	 {Tirza Hirst and David Harel},
    title = 	 {More about recursive structures: descriptive complexity and zero-one laws},
    booktitle =  {Proceedings of the Eleventh Annual IEEE Symposium on Logic in Computer Science (LICS 1996)},
    year =	 {1996},
    month =	 {July}, 
    pages =      {334--347},
    location =   {New Brunswick, NJ, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }