Characteristic Boolean families of structural queries #
queryFamily is the characteristic family of the existing binary
queryLanguage, at every input length. It rejects all strings that are not
structure encodings. The definition uses classical decidability of a general
query; membership in a circuit class will be proved separately from a logical
definability witness.
noncomputable def
Complexity.DescriptiveComplexity.queryFamily
{V : Vocabulary}
(Q : BooleanQuery V)
:
The characteristic Boolean-function family of an encoded structural query.