{"id":"W1081471053","doi":"10.1016/j.ic.2017.09.002","title":"On the complexity and decidability of some problems involving shuffle","year":2017,"lang":"en","type":"article","venue":"Information and Computation","topic":"semigroups and automata theory","field":"Computer Science","cited_by":7,"is_retracted":false,"has_abstract":false,"ca_institutions":"University of Saskatchewan","funders":"Natural Sciences and Engineering Research Council of Canada; National Science Foundation","keywords":"Nondeterministic algorithm; Decidability; Combinatorics; Pushdown automaton; Discrete mathematics; Mathematics; Closure (psychology); Time complexity; Bounded function; Decision problem; Finite-state machine; Algorithm","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":"codex-gemma-dda1882f352a","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.0004158218,0.00005167598,0.00006769312,0.00003490858,0.0003555002,0.0003492913,0.0002139822,0.0000208734,0.000002050717],"category_scores_gemma":[0.00009031818,0.00003581506,0.00001297519,0.00003025816,0.0001500959,0.001777563,0.0001377477,0.00004613544,0.000004374806],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.000008142951,"about_ca_system_score_gemma":0.00001305182,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.00004172675,"about_ca_topic_score_gemma":0.000003600874,"domain_scores_codex":[0.9995474,0.000030029,0.0001772922,0.00006649044,0.0001180304,0.00006077079],"domain_scores_gemma":[0.9993551,0.0001286566,0.0002190018,0.000217297,0.00005647665,0.00002351134],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"theoretical_or_conceptual","study_design_gemma":"simulation_or_modeling","study_design_scores_codex":[0.000003266417,0.00001056714,0.0005937556,0.00003214375,0.000003258444,4.317162e-8,0.001717682,0.0002550382,0.00003105854,0.9221118,0.00007686875,0.07516451],"study_design_scores_gemma":[0.0001578217,0.00003438874,0.07885462,0.00002332062,0.000001039453,0.000001771306,0.0000743226,0.548423,0.0001572566,0.3721476,0.00008139492,0.00004350164],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":null,"genre_codex":"empirical","genre_gemma":"empirical","genre_scores_codex":[0.8176817,0.00003040041,0.1793655,0.001727515,0.00008238194,0.0001785771,0.000002326312,0.00004108577,0.0008904658],"genre_scores_gemma":[0.9975939,0.000009149767,0.001975805,0.0004041606,0.000006616274,0.000004692487,0.000002713879,9.301972e-7,0.000002081397],"genre_candidate":"empirical","genre_consensus":"empirical","teacher_disagreement_score":0.5499642,"threshold_uncertainty_score":0.3368224,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.04185534428189584,"score_gpt":0.2631921773337993,"score_spread":0.2213368330519034,"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."}}