WQO is Decidable for Factorial Languages

Aistis Atminas, Vadim Lozin, Mikhail Moshkov

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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.
Original languageEnglish (US)
Pages (from-to)321-333
Number of pages13
JournalInformation and Computation
Volume256
DOIs
StatePublished - Aug 8 2017

Fingerprint

Dive into the research topics of 'WQO is Decidable for Factorial Languages'. Together they form a unique fingerprint.

Cite this