Query (complexity): Difference between revisions

Revision as of 02:18, 26 August 2009

Revision as of 20:27, 21 December 2017

Line 1:

In [[descriptive complexity]], a '''query''' is a mapping from structures of one [[signature (logic)|signature]] to structures of another vocabulary. [[Neil Immerman]], in his book "Descriptive Complexity"<ref>{{Cite book|url=https://www.worldcat.org/oclc/853271745|title=Descriptive Complexity|last=Neil.|first=Immerman,|date=1999|publisher=Springer New York|isbn=9781461205395|___location=New York, NY|oclc=853271745}}</ref>, "use[s] the concept of query as the fundamental paradigm of computation" (p. 17).

Given signatures <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