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

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

3 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 language	English (US)
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
State	Published - Aug 8 2017

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: This author gratefully acknowledges support from EPSRC, grant EP/L020408/1. Support of KAUST is gratefully acknowledged.

Access to Document

10.1016/j.ic.2017.08.001

https://repository.kaust.edu.sa/bitstream/10754/625350/1/1-s2.0-S0890540117301396-main.pdf

Cite this

@article{d68cbc15089b401d87ac061533ff1ccd,

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

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

note = "KAUST Repository Item: Exported on 2020-10-01 Acknowledgements: This author gratefully acknowledges support from EPSRC, grant EP/L020408/1. Support of KAUST is gratefully acknowledged.",

year = "2017",

month = aug,

day = "8",

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

language = "English (US)",

volume = "256",

pages = "321--333",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "Elsevier",

}

TY - JOUR

T1 - WQO is Decidable for Factorial Languages

AU - Atminas, Aistis

AU - Lozin, Vadim

AU - Moshkov, Mikhail

N1 - KAUST Repository Item: Exported on 2020-10-01 Acknowledgements: This author gratefully acknowledges support from EPSRC, grant EP/L020408/1. Support of KAUST is gratefully acknowledged.

PY - 2017/8/8

Y1 - 2017/8/8

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.

UR - http://hdl.handle.net/10754/625350

UR - http://www.sciencedirect.com/science/article/pii/S0890540117301396

UR - http://www.scopus.com/inward/record.url?scp=85027401939&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2017.08.001

DO - 10.1016/j.ic.2017.08.001

M3 - Article

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

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this