Refereed article in conference proceedings (A4)

Separating many words by counting occurrences of factors

List of Authors: Saarela A.

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)

Title of series: Theoretical Computer Science and General Issues

Volume number: 11647

ISBN: 978-3-030-24885-7

eISBN: 978-3-030-24886-4

DOI: http://dx.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.

Downloadable publication This is an electronic reprint of the original article. |