{"id":"W2075877008","doi":"10.1142/s0129054110007386","title":"ON THE NON-DETERMINISTIC COMMUNICATION COMPLEXITY OF REGULAR LANGUAGES","year":2010,"lang":"en","type":"article","venue":"International Journal of Foundations of Computer Science","topic":"semigroups and automata theory","field":"Computer Science","cited_by":2,"is_retracted":false,"has_abstract":true,"ca_institutions":"McGill University","funders":"","keywords":"Communication complexity; Logarithm; Regular language; Time complexity; Constant (computer programming); Cover (algebra); Probabilistic logic; Mathematics; Computer science; Theoretical computer science; Computational complexity theory; Formal language; Range (aeronautics); Discrete mathematics; Algorithm; Automaton; Artificial intelligence; Programming language","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":[],"consensus_categories":[],"category_scores_codex":[0.001534609,0.00007606202,0.0001389161,0.0003149716,0.0001387358,0.000192582,0.004910955,0.00002190434,0.00002674903],"category_scores_gemma":[0.0002843598,0.00005305175,0.0000886628,0.0003573714,0.001153817,0.0007359395,0.0004135148,0.0002017382,0.000004975803],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00002606245,"about_ca_system_score_gemma":0.0002091501,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.00001367865,"about_ca_topic_score_gemma":0.000004679286,"domain_scores_codex":[0.9984205,0.00005770737,0.00047203,0.0001238471,0.0008272695,0.00009866574],"domain_scores_gemma":[0.9967601,0.0005843932,0.0007351503,0.0006684031,0.001205566,0.00004641585],"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.000008019262,0.000137987,0.000104922,0.000002974689,0.00002507528,0.00000329833,0.000620753,0.0003095009,0.02016709,0.9466775,0.000218748,0.03172413],"study_design_scores_gemma":[0.0008393651,0.0005002834,0.06119419,0.0003478669,0.00001907179,0.0004192669,0.0001345739,0.4001558,0.06670451,0.4685923,0.0008282706,0.0002645325],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.458,0.00001011816,0.5371929,0.003080616,0.0009834777,0.00005352204,0.000003556115,0.000008679304,0.0006670704],"genre_scores_gemma":[0.8778037,0.000005081415,0.1219368,0.0001697655,0.00007336384,8.544275e-7,8.767548e-7,0.000002397887,0.00000715517],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.4780852,"threshold_uncertainty_score":0.9125857,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.02129091006112265,"score_gpt":0.3140838002759662,"score_spread":0.2927928902148435,"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."}}