𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Completeness Results for Recursive Data Bases

✍ Scribed by Tirza Hirst; David Harel

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
767 KB
Volume
52
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

We consider infinite recursive (i.e., computable) relational data bases. Since the set of computable queries on such data bases is not closed under even simple relational operations, one must either make do with a very modest class of queries or considerably restrict the class of allowed data bases. We define two query languages, one for each of these possibilities, and prove their completeness. The first is the language of quantifier-free first-order logic, which is shown to be complete for the non-restricted case. The second is an appropriately modified version of Chandra and Harel's language QL, which is proved complete for the case of ``highly symmetric'' data bases, i.e., ones whose set of automorphisms is of finite index for each tuple width. We also address the related notion of BP-completeness.

πŸ“œ SIMILAR VOLUMES

Completeness results for graph isomorphi
Completeness results for graph isomorphism
✍ Birgit Jenner; Johannes KΓΆbler; Pierre McKenzie; Jacobo TorΓ‘n πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 239 KB

We prove that the graph isomorphism problem restricted to trees and to colored graphs with color multiplicities 2 and 3 is many-one complete for several complexity classes within NC 2 . In particular we show that tree isomorphism, when trees are encoded as strings, is NC 1 -hard under AC 0 -reductio

A Completeness Theorem for Certain Class
A Completeness Theorem for Certain Classes of Recursive Infinitary Formulas
✍ Christopher J. Ash; Julia F. Knight πŸ“‚ Article πŸ“… 1994 πŸ› John Wiley and Sons 🌐 English βš– 494 KB πŸ‘ 1 views

## Abstract We consider the following generalization of the notion of a structure recursive relative to a set __X.__ A relational structure __A__ is said to be a Ξ“(__X__)‐structure if for each relation symbol __R__, the interpretation of __R__ in __A__ is βˆ‘ relative to __X__, where Ξ² = Ξ“(__R__). We

Some APX-completeness results for cubic
Some APX-completeness results for cubic graphs
✍ Paola Alimonti; Viggo Kann πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 122 KB

Four fundamental graph problems, Minimum vertex cover, Maximum independent set, Minimum dominating set and Maximum cut, are shown to be APX-complete even for cubic graphs. Therefore, unless P = NP, these problems do not admit any polynomial time approximation scheme on input graphs of degree bounded