Deciding WQO for factorial languages

Aistis Atminas, Vadim V. Lozin, Mikhail Moshkov

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

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. © 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
Pages68-79
Number of pages12
ISBN (Print)9783642370632
DOIs
StatePublished - Apr 5 2013

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

Cite this