WQO is decidable for factorial languages
Atminas, A.
, Lozin, V. & Moshkov, M.
(2017).
WQO is decidable for factorial languages.
Information and Computation,
https://doi.org/10.1016/j.ic.2017.08.001
, Lozin, V. & Moshkov, M.
(2017).
WQO is decidable for factorial languages.
Information and Computation,
https://doi.org/10.1016/j.ic.2017.08.001
A language is factorial if it is closed under taking factors, i.e. contiguous subwords. Every factorial language can be described by an antidictionary, i.e. a minimal set of forbidden factors. We show that the problem of deciding whether a factorial language given by a finite antidictionary is well-quasi-ordered under the factor containment relation can be solved in polynomial time. We also discuss possible ways to extend our solution to permutations and graphs.