{"id":"W2002992445","doi":"10.1016/s0304-3975(02)00830-7","title":"On the complexity of intersecting finite state automata and NL versus NP","year":2003,"lang":"en","type":"article","venue":"Theoretical Computer Science","topic":"semigroups and automata theory","field":"Computer Science","cited_by":25,"is_retracted":false,"has_abstract":false,"ca_institutions":"University of Toronto; McMaster University","funders":"","keywords":"Mathematics; Complexity class; Deterministic finite automaton; DFA minimization; Intersection (aeronautics); Finite-state machine; Class (philosophy); Time complexity; Computational complexity theory; Discrete mathematics; Combinatorics; Algorithm; State (computer science); Automaton; Quantum finite automata; Automata theory; Computer science; Theoretical computer science","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":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.006181912,0.0007846241,0.002143793,0.002401444,0.003149858,0.009043321,0.002921482,0.003630623,0.01254458],"category_scores_gemma":[0.06979717,0.001070202,0.002069983,0.004054841,0.0075029,0.03886214,0.006412383,0.006975885,0.000743101],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00435252,"about_ca_system_score_gemma":0.00243112,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.003531432,"about_ca_topic_score_gemma":0.002717745,"domain_scores_codex":[0.9924451,0.003115583,0.0004849917,0.001082255,0.001992981,0.0008791169],"domain_scores_gemma":[0.8009244,0.1844137,0.00393524,0.00609304,0.002665604,0.001967988],"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.0005070958,0.0001230833,0.003146513,0.0003660442,0.00005955664,0.0001826757,0.001204559,0.03315587,0.0005681468,0.9275469,0.005465308,0.02767429],"study_design_scores_gemma":[0.00001803723,0.00001431336,0.000404748,0.00002868915,0.0000166589,0.00008680062,0.000189442,0.02583776,0.0001960658,0.9718846,0.001307842,0.00001499988],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"empirical","genre_gemma":"empirical","genre_scores_codex":[0.5143796,0.01349984,0.2730136,0.04273329,0.0006362151,0.00020605,0.002412471,0.0008451867,0.1522737],"genre_scores_gemma":[0.9641736,0.002888567,0.02311162,0.0008298843,0.0009390119,0.0001285613,0.001021862,0.000231294,0.006675505],"genre_candidate":"empirical","genre_consensus":"empirical","teacher_disagreement_score":0.01254458,"threshold_uncertainty_score":0.04196578,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.03585890837325412,"score_gpt":0.2605987869236125,"score_spread":0.2247398785503584,"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."}}