{"id":"W4360604354","doi":"10.1016/j.ic.2023.105027","title":"New characterizations of exponential, elementary, and non-elementary time-bounded Turing machines","year":2023,"lang":"en","type":"article","venue":"Information and Computation","topic":"semigroups and automata theory","field":"Computer Science","cited_by":0,"is_retracted":false,"has_abstract":false,"ca_institutions":"University of Saskatchewan","funders":"Natural Sciences and Engineering Research Council of Canada","keywords":"Decidability; Computer science; Turing machine; Pushdown automaton; Bounded function; Deterministic pushdown automaton; Deterministic context-free grammar; Model checking; Embedded pushdown automaton; Class (philosophy); Reachability problem; Automaton; Discrete mathematics; Theoretical computer science; Mathematics; Algorithm; Rule-based machine translation; Automata theory; Context-free grammar; Artificial intelligence","routes":{"ca_aff":true,"ca_fund":true,"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.002123869,0.001021607,0.000984007,0.002459088,0.001548272,0.005320337,0.002698212,0.00200661,0.008445926],"category_scores_gemma":[0.01363318,0.0006506051,0.001270237,0.001692909,0.004989819,0.01170127,0.003817073,0.004898237,0.001048953],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.001580213,"about_ca_system_score_gemma":0.0009120948,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.0002397682,"about_ca_topic_score_gemma":0.0002987148,"domain_scores_codex":[0.99793,0.0004191752,0.0001862893,0.0005677236,0.0005535425,0.00034323],"domain_scores_gemma":[0.9826775,0.01142474,0.001327999,0.001633036,0.001672435,0.001264325],"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.0001174989,0.00005297636,0.0008032043,0.00008443176,0.00000958374,0.0001252746,0.0004877771,0.001682495,0.002566686,0.9855827,0.001282359,0.007204984],"study_design_scores_gemma":[0.00002700602,0.00004072557,0.0006907785,0.00004137913,0.00002042745,0.0003277112,0.0002714803,0.02742838,0.002505861,0.9629916,0.005624455,0.00003012421],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.3045437,0.003439364,0.6232257,0.003419158,0.0005267215,0.0001736488,0.0008945234,0.001189582,0.06258758],"genre_scores_gemma":[0.9304532,0.0007635949,0.05366581,0.0005058518,0.0007305216,0.0002835983,0.0007781396,0.0003148144,0.01250447],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.008445926,"threshold_uncertainty_score":0.02825439,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.007063848050454864,"score_gpt":0.230268096332771,"score_spread":0.2232042482823161,"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."}}