Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950593 | Information and Computation | 2017 | 13 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Aistis Atminas, Vadim Lozin, Mikhail Moshkov,