Query (complexity): Difference between revisions

Revision as of 03:52, 16 December 2008

Revision as of 12:36, 16 May 2009

Line 1:

In [[descriptive complexity]], a '''query''' is a mapping from structures of one [[vocabularysignature (mathematical logic)|vocabularysignature]] to structures of another vocabulary. [[Neil Immerman]], in his book "Descriptive Complexity", "use[s] the concept of query as the fundamental paradigm of computation" (p. 17).

Given vocabulariessignatures <math>\sigma</math> and <math>\tau</math>, we define the set of [[structure (mathematical logic)|structure]]s on each language, <math>\mbox{STRUC}[\sigma]</math> and <math>\mbox{STRUC}[\tau]</math>. A query is then any mapping

<blockquote>

<math>I : \mbox{STRUC}[\sigma] \to \mbox{STRUC}[\tau]</math>