Deciding Atomicity of Subword-Closed Languages

Aistis Atminas; Vadim Lozin

doi:10.1007/978-3-031-05578-2_5

Deciding Atomicity of Subword-Closed Languages

Aistis Atminas^*
, Vadim Lozin

^*Corresponding author for this work

University of Warwick

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

4 Citations (Scopus)

Abstract

We study languages closed under non-contiguous (scattered) subword containment order. Any subword-closed language L can be uniquely described by its anti-dictionary, i.e. the set of minimal words that do not belong to L. A language L is said to be atomic if it cannot be presented as the union of two subword-closed languages different from L. In this work, we provide a decision procedure which, given a language over a finite alphabet defined by its anti-dictionary, decides whether it is atomic or not.

Original language	English
Title of host publication	Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings
Editors	Volker Diekert, Mikhail Volkov
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	69-77
Number of pages	9
ISBN (Print)	9783031055775
DOIs	https://doi.org/10.1007/978-3-031-05578-2_5
Publication status	Published - 2022
Event	26th International Conference on Developments in Language Theory, DLT 2022 - Tampa, United States Duration: 9 May 2022 → 13 May 2022

Publication series

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

Conference

Conference	26th International Conference on Developments in Language Theory, DLT 2022
Country/Territory	United States
City	Tampa
Period	9/05/22 → 13/05/22

Keywords

Decidability
Joint embedding property
Subword-closed language

Access to Document

10.1007/978-3-031-05578-2_5

Cite this

Atminas, A., & Lozin, V. (2022). Deciding Atomicity of Subword-Closed Languages. In V. Diekert, & M. Volkov (Eds.), Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings (pp. 69-77). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13257 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-05578-2_5

Atminas, Aistis ; Lozin, Vadim. / Deciding Atomicity of Subword-Closed Languages. Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings. editor / Volker Diekert ; Mikhail Volkov. Springer Science and Business Media Deutschland GmbH, 2022. pp. 69-77 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{85f877c3235d45d28d8201077da8a43d,

title = "Deciding Atomicity of Subword-Closed Languages",

abstract = "We study languages closed under non-contiguous (scattered) subword containment order. Any subword-closed language L can be uniquely described by its anti-dictionary, i.e. the set of minimal words that do not belong to L. A language L is said to be atomic if it cannot be presented as the union of two subword-closed languages different from L. In this work, we provide a decision procedure which, given a language over a finite alphabet defined by its anti-dictionary, decides whether it is atomic or not.",

keywords = "Decidability, Joint embedding property, Subword-closed language",

author = "Aistis Atminas and Vadim Lozin",

note = "Publisher Copyright: {\textcopyright} 2022, Springer Nature Switzerland AG.; 26th International Conference on Developments in Language Theory, DLT 2022 ; Conference date: 09-05-2022 Through 13-05-2022",

year = "2022",

doi = "10.1007/978-3-031-05578-2\_5",

language = "English",

isbn = "9783031055775",

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

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "69--77",

editor = "Volker Diekert and Mikhail Volkov",

booktitle = "Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings",

}

Atminas, A & Lozin, V 2022, Deciding Atomicity of Subword-Closed Languages. in V Diekert & M Volkov (eds), Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13257 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 69-77, 26th International Conference on Developments in Language Theory, DLT 2022, Tampa, United States, 9/05/22. https://doi.org/10.1007/978-3-031-05578-2_5

Deciding Atomicity of Subword-Closed Languages. / Atminas, Aistis; Lozin, Vadim.
Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings. ed. / Volker Diekert; Mikhail Volkov. Springer Science and Business Media Deutschland GmbH, 2022. p. 69-77 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13257 LNCS).

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

TY - GEN

T1 - Deciding Atomicity of Subword-Closed Languages

AU - Atminas, Aistis

AU - Lozin, Vadim

PY - 2022

Y1 - 2022

N2 - We study languages closed under non-contiguous (scattered) subword containment order. Any subword-closed language L can be uniquely described by its anti-dictionary, i.e. the set of minimal words that do not belong to L. A language L is said to be atomic if it cannot be presented as the union of two subword-closed languages different from L. In this work, we provide a decision procedure which, given a language over a finite alphabet defined by its anti-dictionary, decides whether it is atomic or not.

AB - We study languages closed under non-contiguous (scattered) subword containment order. Any subword-closed language L can be uniquely described by its anti-dictionary, i.e. the set of minimal words that do not belong to L. A language L is said to be atomic if it cannot be presented as the union of two subword-closed languages different from L. In this work, we provide a decision procedure which, given a language over a finite alphabet defined by its anti-dictionary, decides whether it is atomic or not.

KW - Decidability

KW - Joint embedding property

KW - Subword-closed language

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

U2 - 10.1007/978-3-031-05578-2_5

DO - 10.1007/978-3-031-05578-2_5

M3 - Conference Proceeding

AN - SCOPUS:85130242254

SN - 9783031055775

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

SP - 69

EP - 77

BT - Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings

A2 - Diekert, Volker

A2 - Volkov, Mikhail

PB - Springer Science and Business Media Deutschland GmbH

T2 - 26th International Conference on Developments in Language Theory, DLT 2022

Y2 - 9 May 2022 through 13 May 2022

ER -

Atminas A, Lozin V. Deciding Atomicity of Subword-Closed Languages. In Diekert V, Volkov M, editors, Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings. Springer Science and Business Media Deutschland GmbH. 2022. p. 69-77. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-05578-2_5