{"id":"W4394944952","doi":"10.1016/j.dam.2024.04.006","title":"Polynomial-time equivalences and refined algorithms for longest common subsequence variants","year":2024,"lang":"en","type":"article","venue":"Discrete Applied Mathematics","topic":"Algorithms and Data Compression","field":"Computer Science","cited_by":1,"is_retracted":false,"has_abstract":false,"ca_institutions":"University of Alberta","funders":"Japan Science and Technology Agency; Japan Society for the Promotion of Science; Core Research for Evolutional Science and Technology; Natural Sciences and Engineering Research Council of Canada","keywords":"Mathematics; Longest common subsequence problem; Longest increasing subsequence; Time complexity; Combinatorics; Subsequence; Algorithm; Discrete mathematics","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.0004348541,0.0002451249,0.000322134,0.00009100889,0.0001900592,0.0006005237,0.0007780984,0.00009578584,0.00001652455],"category_scores_gemma":[0.00002342485,0.0001903022,0.00005941514,0.000242027,0.0001004926,0.0004653013,0.0004814113,0.0001279547,0.00006952506],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00002643221,"about_ca_system_score_gemma":0.00005661816,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.00001206491,"about_ca_topic_score_gemma":0.000001858485,"domain_scores_codex":[0.9984345,0.00001279413,0.0003563419,0.0005572822,0.0002813423,0.0003577585],"domain_scores_gemma":[0.9986965,0.0004065486,0.00009552338,0.0006429831,0.00003018478,0.0001282448],"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.00003129559,0.0001861712,0.000005906486,0.001700721,0.0001488246,0.00007814959,0.004033747,0.00004448352,0.04576051,0.6474236,0.02197656,0.27861],"study_design_scores_gemma":[0.0003993262,0.0001260218,0.00006740561,0.00034722,0.00005304155,0.00006546458,0.0001229341,0.9303618,0.003545255,0.05747971,0.006894796,0.0005370365],"study_design_candidate":"simulation_or_modeling","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"methods","genre_scores_codex":[0.004210085,0.0006920575,0.9894993,0.0007008221,0.0003054445,0.0006078132,0.0001345298,0.0004380202,0.003411965],"genre_scores_gemma":[0.08434637,0.0001269841,0.9142526,0.000153429,0.0002403241,0.0001792023,0.00007130866,0.00004856513,0.0005812355],"genre_candidate":"methods","genre_consensus":"methods","teacher_disagreement_score":0.9303173,"threshold_uncertainty_score":0.7760297,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.02504692977251357,"score_gpt":0.285335616274388,"score_spread":0.2602886865018745,"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."}}