WQO is decidable for factorial languages

Aistis Atminas; Vadim Lozin; Mikhail Moshkov

doi:10.1016/j.ic.2017.08.001

WQO is decidable for factorial languages

Aistis Atminas
, Vadim Lozin^*
, Mikhail Moshkov

^*Corresponding author for this work

The London School of Economics and Political Science
University of Warwick
King Abdullah University of Science and Technology

Research output: Contribution to journal › Article › peer-review

6 Citations (Scopus)

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 language	English
Pages (from-to)	321-333
Number of pages	13
Journal	Information and Computation
Volume	256
DOIs	https://doi.org/10.1016/j.ic.2017.08.001
Publication status	Published - Oct 2017
Externally published	Yes

Keywords

Factorial language
Induced subgraph
Permutation
Polynomial-time algorithm
Well-quasi-ordering

Access to Document

10.1016/j.ic.2017.08.001

Cite this

@article{5aa6295707fe448ba8a0dc2ae1c07d60,

title = "WQO is decidable for factorial languages",

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.",

keywords = "Factorial language, Induced subgraph, Permutation, Polynomial-time algorithm, Well-quasi-ordering",

author = "Aistis Atminas and Vadim Lozin and Mikhail Moshkov",

note = "Publisher Copyright: {\textcopyright} 2017 Elsevier Inc.",

year = "2017",

month = oct,

doi = "10.1016/j.ic.2017.08.001",

language = "English",

volume = "256",

pages = "321--333",

journal = "Information and Computation",

issn = "0890-5401",

}

TY - JOUR

T1 - WQO is decidable for factorial languages

AU - Atminas, Aistis

AU - Lozin, Vadim

AU - Moshkov, Mikhail

PY - 2017/10

Y1 - 2017/10

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.

KW - Factorial language

KW - Induced subgraph

KW - Permutation

KW - Polynomial-time algorithm

KW - Well-quasi-ordering

UR - https://www.scopus.com/pages/publications/85027401939

U2 - 10.1016/j.ic.2017.08.001

DO - 10.1016/j.ic.2017.08.001

M3 - Article

AN - SCOPUS:85027401939

SN - 0890-5401

VL - 256

SP - 321

EP - 333

JO - Information and Computation

JF - Information and Computation

ER -

WQO is decidable for factorial languages

Abstract

Keywords

Access to Document

Other files and links

Cite this