TY - JOUR
T1 - WQO is Decidable for Factorial Languages
AU - Atminas, Aistis
AU - Lozin, Vadim
AU - Moshkov, Mikhail
N1 - KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: This author gratefully acknowledges support from EPSRC, grant EP/L020408/1. Support of KAUST is gratefully acknowledged.
PY - 2017/8/8
Y1 - 2017/8/8
N2 - 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.
AB - 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.
UR - http://hdl.handle.net/10754/625350
UR - http://www.sciencedirect.com/science/article/pii/S0890540117301396
UR - http://www.scopus.com/inward/record.url?scp=85027401939&partnerID=8YFLogxK
U2 - 10.1016/j.ic.2017.08.001
DO - 10.1016/j.ic.2017.08.001
M3 - Article
SN - 0890-5401
VL - 256
SP - 321
EP - 333
JO - Information and Computation
JF - Information and Computation
ER -