bagan2020trichotomy (560B)
1 # bagan2020trichotomy 2 3 Article showing [simple_path_trichotomy] 4 5 ## Intuition of criterion 6 7 "term" = (w+eps) or (A^{\geq k} + eps) 8 with w a fixed word, and A some subalphabet 9 "sequence": concatenation of terms, with fixed words before and after 10 11 tractable class: disjunction of sequences 12 13 tractability is not obvious! intuitively we can "shorten" thanks to the +epsilon 14 15 equivalent reformulation: "closed under skipping" 16 => [algebraic_automata_theory] characterization? cf [martens2023trichotomy] in the case of [trail_trichotomy] 17 18 Up: [academic_paper_list]