A4 Refereed article in a conference publication
Separating many words by counting occurrences of factors
Authors: Saarela A.
Editors: Piotrek Hofman, Michał Skrzypczak
Conference name: International Conference on Developments in Language Theory
Publisher: Springer Verlag
Publication year: 2019
Journal: Lecture Notes in Computer Science
Book title : Developments in Language Theory: 23rd International Conference, DLT 2019, Warsaw, Poland, August 5–9, 2019, Proceedings
Journal name in source: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Series title: Theoretical Computer Science and General Issues
Volume: 11647
First page : 251
Last page: 264
ISBN: 978-3-030-24885-7
eISBN: 978-3-030-24886-4
DOI: https://doi.org/10.1007/978-3-030-24886-4_19
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/44130548
For a given language L, we study the languages X such that for all distinct words u,v∈L , there exists a word x∈X appearing a different number of times as a factor in u and in v. In particular, we are interested in the following question: For which languages L does there exist a finite language X satisfying the above condition? We answer this question for all regular languages and for all sets of factors of infinite words.
Keywords:
infinite word, k-abelian equivalence, Separating words problem
Downloadable publication This is an electronic reprint of the original article. |  |
