Implicit definability on finite structures and unambiguous computations

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 i...

Full description

Saved in:
Bibliographic Details
Main Author: Kolaitis, P.G.
Format: Conference Proceeding
Language:English
Subjects:
Computational complexity
Interpolation
Logic programming
Turing machines
Vocabulary
Citations: Items that cite this one
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 intersection coUP is obtained in terms of it, where UP is the class of NP languages accepted by unambiguous Turing machines.< >
DOI:10.1109/LICS.1990.113743