Deciding WQO for factorial languages

Aistis Atminas; Vadim Lozin; Mikhail Moshkov

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

Deciding WQO for factorial languages

Aistis Atminas^*, Vadim Lozin, Mikhail Moshkov

^*Corresponding author for this work

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

2 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.

Original language	English
Title of host publication	Language and Automata Theory and Applications - 7th International Conference, LATA 2013, Proceedings
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
Publication status	Published - 2013
Externally published	Yes
Event	7th International Conference on Language and Automata Theory and Applications, LATA 2013 - Bilbao, Spain Duration: 2 Apr 2013 → 5 Apr 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7810 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	7th International Conference on Language and Automata Theory and Applications, LATA 2013
Country/Territory	Spain
City	Bilbao
Period	2/04/13 → 5/04/13

Keywords

factorial language
polynomial-time algorithm
well-quasi-ordering

Access to Document

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

Cite this

Atminas, A., Lozin, V., & Moshkov, M. (2013). Deciding WQO for factorial languages. In Language and Automata Theory and Applications - 7th International Conference, LATA 2013, Proceedings (pp. 68-79). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7810 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-642-37064-9_8

@inproceedings{b319d47fa1f741688ad25fe4940cc276,

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

keywords = "factorial language, polynomial-time algorithm, well-quasi-ordering",

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

year = "2013",

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

language = "English",

isbn = "9783642370632",

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

publisher = "Springer Verlag",

pages = "68--79",

booktitle = "Language and Automata Theory and Applications - 7th International Conference, LATA 2013, Proceedings",

note = "7th International Conference on Language and Automata Theory and Applications, LATA 2013 ; Conference date: 02-04-2013 Through 05-04-2013",

}

Atminas, A, Lozin, V & Moshkov, M 2013, Deciding WQO for factorial languages. in Language and Automata Theory and Applications - 7th International Conference, LATA 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7810 LNCS, Springer Verlag, pp. 68-79, 7th International Conference on Language and Automata Theory and Applications, LATA 2013, Bilbao, Spain, 2/04/13. https://doi.org/10.1007/978-3-642-37064-9_8

Deciding WQO for factorial languages. / Atminas, Aistis; Lozin, Vadim; Moshkov, Mikhail.
Language and Automata Theory and Applications - 7th International Conference, LATA 2013, Proceedings. Springer Verlag, 2013. p. 68-79 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7810 LNCS).

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

TY - GEN

T1 - Deciding WQO for factorial languages

AU - Atminas, Aistis

AU - Lozin, Vadim

AU - Moshkov, Mikhail

PY - 2013

Y1 - 2013

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.

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.

KW - factorial language

KW - polynomial-time algorithm

KW - well-quasi-ordering

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 Proceeding

AN - SCOPUS:84875682760

SN - 9783642370632

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

SP - 68

EP - 79

BT - Language and Automata Theory and Applications - 7th International Conference, LATA 2013, Proceedings

PB - Springer Verlag

T2 - 7th International Conference on Language and Automata Theory and Applications, LATA 2013

Y2 - 2 April 2013 through 5 April 2013

ER -

Atminas A, Lozin V, Moshkov M. Deciding WQO for factorial languages. In Language and Automata Theory and Applications - 7th International Conference, LATA 2013, Proceedings. Springer Verlag. 2013. p. 68-79. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-37064-9_8

Deciding WQO for factorial languages

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Cite this