Deciding WQO for factorial languages

Aistis Atminas; Vadim V. Lozin; Mikhail Moshkov

doi:10.1007/978-3-642-37064-9-8

Deciding WQO for factorial languages

Aistis Atminas, Vadim V. Lozin, Mikhail Moshkov

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Springer Verlag
Pages	68-79
Number of pages	12
ISBN (Print)	9783642370632
DOIs	https://doi.org/10.1007/978-3-642-37064-9-8
State	Published - Apr 5 2013

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-37064-9-8

Cite this

@inproceedings{d8f2adb33b9041efb186e12b108ff345,

title = "Deciding WQO 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. {\textcopyright} 2013 Springer-Verlag Berlin Heidelberg.",

author = "Aistis Atminas and Lozin, {Vadim V.} and Mikhail Moshkov",

note = "KAUST Repository Item: Exported on 2020-10-01",

year = "2013",

month = apr,

day = "5",

doi = "10.1007/978-3-642-37064-9-8",

language = "English (US)",

isbn = "9783642370632",

pages = "68--79",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

address = "Germany",

}

TY - GEN

T1 - Deciding WQO for factorial languages

AU - Atminas, Aistis

AU - Lozin, Vadim V.

AU - Moshkov, Mikhail

N1 - KAUST Repository Item: Exported on 2020-10-01

PY - 2013/4/5

Y1 - 2013/4/5

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. © 2013 Springer-Verlag Berlin Heidelberg.

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. © 2013 Springer-Verlag Berlin Heidelberg.

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

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

U2 - 10.1007/978-3-642-37064-9-8

DO - 10.1007/978-3-642-37064-9-8

M3 - Conference contribution

SN - 9783642370632

SP - 68

EP - 79

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

PB - Springer Verlag

ER -

Deciding WQO for factorial languages

Abstract

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this