{"id":"W2063991224","doi":"10.1016/s0304-3975(01)00152-9","title":"Lower bounds for invariant queries in logics with counting","year":2002,"lang":"en","type":"article","venue":"Theoretical Computer Science","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":13,"is_retracted":false,"has_abstract":false,"ca_institutions":"University of Toronto","funders":"","keywords":"Preorder; Unary operation; Locality; Transitive closure; Mathematics; Discrete mathematics; Complexity class; Expressive power; First-order logic; Binary relation; Transitive relation; Second-order logic; Succinctness; Invariant (physics); Proof theory; Combinatorics; Time complexity; Higher-order logic; Computer science; Mathematical proof; Theoretical computer science; Description logic","routes":{"ca_aff":true,"ca_fund":false,"ca_venue":false,"about_ca":false,"invisible_to_affiliation_only":false},"retraction":null,"screen":null,"direct_labels":[],"prediction":{"model_version":"codex-gemma-dda1882f352a","candidate_categories":["sts"],"consensus_categories":[],"category_scores_codex":[0.001288203,0.0001875646,0.0002235077,0.0002189456,0.0004788243,0.0007450954,0.00210011,0.00004729745,0.00004310157],"category_scores_gemma":[0.00008999191,0.0001429042,0.00005112943,0.001570537,0.003058094,0.0008676581,0.0006434604,0.0001987868,0.00001686204],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00005560221,"about_ca_system_score_gemma":0.00006396998,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.000005906596,"about_ca_topic_score_gemma":0.000008119412,"domain_scores_codex":[0.9977304,0.00005072352,0.0002649736,0.000712433,0.0005528211,0.0006886043],"domain_scores_gemma":[0.9985799,0.0003831368,0.00006402614,0.0006532334,0.0001697316,0.000149958],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"theoretical_or_conceptual","study_design_gemma":"simulation_or_modeling","study_design_scores_codex":[0.000008370661,0.00009199732,0.0001333601,0.000007783975,0.000002012054,0.00002195946,0.0005100495,0.0001682751,0.00002886034,0.9841989,0.00004168072,0.01478681],"study_design_scores_gemma":[0.0003097405,0.0003844552,0.0003834156,0.00003971628,0.000001772227,0.0000443123,0.000007756154,0.7501076,0.0002387804,0.2476107,0.000647444,0.0002243097],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.01645259,0.00003394839,0.978158,0.001484414,0.000455545,0.0002259204,0.00000170885,0.0001415761,0.003046289],"genre_scores_gemma":[0.6506544,0.000003277166,0.3486397,0.0006071032,0.00006743072,0.00001264967,2.350457e-7,0.000005075656,0.00001015538],"genre_candidate":"methods","genre_consensus":null,"teacher_disagreement_score":0.7499393,"threshold_uncertainty_score":0.999655,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.02230894930910513,"score_gpt":0.2362898047697848,"score_spread":0.2139808554606797,"validation_status":"score_only:v0-immature-baseline","note":"Baseline scores from an immature model (maturity gate not passed). Scores rank; they never assert a category."}}