{"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":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.004846189,0.001574366,0.002074632,0.003192864,0.001699426,0.004415307,0.005601281,0.001785594,0.007675613],"category_scores_gemma":[0.03499794,0.001206866,0.002921724,0.005789711,0.003817722,0.01286581,0.005383352,0.007074663,0.002155476],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00261167,"about_ca_system_score_gemma":0.002623929,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.002839254,"about_ca_topic_score_gemma":0.00354229,"domain_scores_codex":[0.9877768,0.002522692,0.001036187,0.003379438,0.004157757,0.001127156],"domain_scores_gemma":[0.9710101,0.01483238,0.001272916,0.009141668,0.003129087,0.0006137774],"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.001176229,0.0003797473,0.001361426,0.0004395547,0.0001522856,0.0002785701,0.0008818,0.0712245,0.008398934,0.6781884,0.007724842,0.2297936],"study_design_scores_gemma":[0.00009617605,0.0001089434,0.0002979966,0.00004316434,0.00007820504,0.0001817699,0.0001401506,0.1490241,0.00552265,0.8384763,0.005986542,0.00004398224],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.02215019,0.0005427484,0.9701413,0.0003706749,0.0001746532,0.0001453934,0.000287787,0.001194587,0.004992673],"genre_scores_gemma":[0.3378974,0.0007961639,0.6481951,0.0004640176,0.0005242222,0.0003917784,0.002422168,0.001389384,0.007919807],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.007675613,"threshold_uncertainty_score":0.0256775,"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."}}