Paper: Implicit definability on finite structures and unambiguous computations (at LICS 1990)
Authors: Kolaitis, P.G.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 = {Kolaitis, P.G.},
title = {Implicit definability on finite structures and unambiguous computations },
booktitle = {Proceedings of the Fifth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1990},
year = 1990,
editor = {John Mitchell},
month = {June},
pages = {168--180},
location = {Philadelphia, PA, USA},
publisher = {IEEE Computer Society Press}
}