Deciding WQO for factorial languages

Aistis Atminas, Vadim V. Lozin, Mikhail Moshkov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


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. © 2013 Springer-Verlag Berlin Heidelberg.
Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783642370632
StatePublished - Apr 5 2013

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Deciding WQO for factorial languages'. Together they form a unique fingerprint.

Cite this