{"id":"W2751513393","doi":"10.2168/lmcs-8(1:27)2012","title":"On the Parameterized Intractability of Monadic Second-Order Logic","year":2012,"lang":"en","type":"article","venue":"Logical Methods in Computer Science","topic":"Formal Methods in Verification","field":"Computer Science","cited_by":7,"is_retracted":false,"has_abstract":true,"ca_institutions":"","funders":"Banff International Research Station for Mathematical Innovation and Discovery; Deutsche Forschungsgemeinschaft","keywords":"Parameterized complexity; Bounded function; Class (philosophy); Hierarchy; Complexity class; Second-order logic; Order (exchange)","routes":{"ca_aff":false,"ca_fund":true,"ca_venue":false,"about_ca":false,"invisible_to_affiliation_only":true},"retraction":null,"screen":null,"direct_labels":[],"prediction":{"model_version":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.00395696,0.001213757,0.001307839,0.001716391,0.002172012,0.004566118,0.002712812,0.001330672,0.003689798],"category_scores_gemma":[0.02130507,0.001129024,0.003016501,0.002593335,0.007208198,0.01353032,0.003335263,0.006819962,0.0003991345],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.005398101,"about_ca_system_score_gemma":0.002526583,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.008637867,"about_ca_topic_score_gemma":0.007941498,"domain_scores_codex":[0.9957485,0.001110031,0.0001883844,0.001094853,0.001060173,0.0007981347],"domain_scores_gemma":[0.954884,0.03696315,0.001685806,0.004930132,0.001061126,0.0004758176],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"theoretical_or_conceptual","study_design_gemma":"theoretical_or_conceptual","study_design_scores_codex":[0.0005281833,0.00009850025,0.001694557,0.0003007515,0.0001113368,0.000284097,0.0006793439,0.08049385,0.005438282,0.8899063,0.001747203,0.01871745],"study_design_scores_gemma":[0.00006266055,0.00004614583,0.000485522,0.00003886914,0.00006976949,0.00008081995,0.00006412778,0.173567,0.003607199,0.8195518,0.002385781,0.00004030104],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.2195215,0.002424702,0.7427453,0.006052517,0.0001679465,0.0001326351,0.0008245007,0.003711592,0.02441938],"genre_scores_gemma":[0.8956671,0.001199184,0.09579303,0.0008038279,0.0002531323,0.0002362031,0.0006707199,0.0006526075,0.004724116],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.008637867,"threshold_uncertainty_score":0.03916609,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.1114300046363616,"score_gpt":0.4035080027453709,"score_spread":0.2920779981090093,"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."}}