{"id":"W2949340385","doi":"10.48550/arxiv.0907.0159","title":"The computational complexity of universality problems for prefixes, suffixes, factors, and subwords of regular languages","year":2009,"lang":"en","type":"preprint","venue":"ArXiv.org","topic":"semigroups and automata theory","field":"Computer Science","cited_by":3,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Waterloo; University of Winnipeg","funders":"","keywords":"Prefix; Universality (dynamical systems); Mathematics; Computer science; Arithmetic; Linguistics; Philosophy; Physics","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.006878444,0.001328446,0.002455135,0.001760383,0.002379877,0.00899197,0.004023739,0.003245235,0.007834496],"category_scores_gemma":[0.05625873,0.001153635,0.003832265,0.002411638,0.006833097,0.0252539,0.004942908,0.005496498,0.000578251],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.003715353,"about_ca_system_score_gemma":0.00329116,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.003869445,"about_ca_topic_score_gemma":0.003247208,"domain_scores_codex":[0.9884062,0.00391031,0.0009069085,0.003622492,0.001672695,0.001481394],"domain_scores_gemma":[0.8471334,0.1392925,0.004526486,0.005432604,0.00181804,0.001796914],"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.004000761,0.001043,0.03353259,0.002673409,0.0007922662,0.001181802,0.004253296,0.228263,0.007733383,0.5808876,0.01347955,0.1221594],"study_design_scores_gemma":[0.0001653466,0.0001077897,0.001452422,0.00006329975,0.0001191035,0.0002980965,0.0007236937,0.1807232,0.002589815,0.8123775,0.001315396,0.00006430352],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"empirical","genre_gemma":"empirical","genre_scores_codex":[0.7767424,0.001572431,0.1938293,0.01198827,0.0001903943,0.0003330405,0.003419924,0.0009070149,0.01101733],"genre_scores_gemma":[0.9310511,0.0006378082,0.06068523,0.000559842,0.000430089,0.0003066247,0.003276784,0.0002747591,0.002777661],"genre_candidate":"empirical","genre_consensus":"empirical","teacher_disagreement_score":0.00899197,"threshold_uncertainty_score":0.03637713,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.05736920413176716,"score_gpt":0.277646012375562,"score_spread":0.2202768082437949,"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."}}