Implicit definability on finite structures and unambiguous computations

Author

Kolaitis, Phokion G.

Author_Institution

Comput. & Inf. Sci., California Univ., Santa Cruz, CA, USA

fYear

1990

fDate

4-7 Jun 1990

Firstpage

168

Lastpage

180

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

Keywords

Turing machines; computational complexity; formal languages; NP languages; complexity class; computational strength; expressive power; finite structures; fixpoint query; implicit definability; logical characterization; optimal result; unambiguous Turing machines; unambiguous computations; Computational complexity; Databases; Interpolation; Logic programming; Turing machines; Vocabulary;

fLanguage

English

Publisher

ieee

Conference_Titel

Logic in Computer Science, 1990. LICS '90, Proceedings., Fifth Annual IEEE Symposium on e

Conference_Location

Philadelphia, PA

Print_ISBN

0-8186-2073-0

Type

conf

DOI

10.1109/LICS.1990.113743

Filename

113743