Lics

IEEE Symposium on Logic in Computer Science

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

Fifth Annual IEEE Symposium on

Logic in Computer Science (LICS 1990)

Paper: Implicit definability on finite structures and unambiguous computations (at LICS 1990)

Authors: Phokion G. Kolaitis

Abstract

The expressive power and the computational strength of first-order implicit definability on finite structures are studied. It is shown that every fixpoint query is a member of an implicitly definable pair of queries on finite structures. This turns out to be an optimal result, since in addition it is proven that there are natural fixpoint queries that are not implicitly definable on finite structures. First-order implicit definability on ordered finite structures is also investigated, and logical characterization of the complexity class UP∩coUP is obtained in terms of it, where UP is the class of NP languages accepted by unambiguous Turing machines

BibTeX

  @InProceedings{Kolaitis-Implicitdefinabilit,
    author = 	 {Phokion G. Kolaitis},
    title = 	 {Implicit definability on finite structures and unambiguous computations },
    booktitle =  {Proceedings of the Fifth Annual IEEE Symposium on Logic in Computer Science (LICS 1990)},
    year =	 {1990},
    month =	 {June}, 
    pages =      {168--180},
    location =   {Philadelphia, PA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }
   

Last modified: 2018-06-2121:59
Andrzej Murawski