Advertisement
Published in:
2013 | OriginalPaper | Chapter
Deciding WQO for Factorial Languages
Authors : Aistis Atminas, Vadim Lozin, Mikhail Moshkov
Published in: Language and Automata Theory and Applications
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.