Separating many words by counting occurrences of factors
: Saarela A.
: Piotrek Hofman, Michał Skrzypczak
: International Conference on Developments in Language Theory
Publisher: Springer Verlag
: 2019
: Lecture Notes in Computer Science
: Developments in Language Theory: 23rd International Conference, DLT 2019, Warsaw, Poland, August 5–9, 2019, Proceedings
: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
: Theoretical Computer Science and General Issues
: 11647
: 251
: 264
: 978-3-030-24885-7
: 978-3-030-24886-4
DOI: https://doi.org/10.1007/978-3-030-24886-4_19
: 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.
