TY - GEN
T1 - Deciding Atomicity of Subword-Closed Languages
AU - Atminas, Aistis
AU - Lozin, Vadim
N1 - Publisher Copyright:
© 2022, Springer Nature Switzerland AG.
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 - http://www.scopus.com/inward/record.url?scp=85130242254&partnerID=8YFLogxK
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 -