A4 Article in conference proceedings

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


Abstract

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.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.




Last updated on 2021-24-06 at 10:59