@inproceedings{10.1007/3-540-55808-X_48,
    Abstract = {A language L is said to have a polynomial density if the function pL.(n)={\textbrokenbar}L∩∑n{\textbrokenbar} of L is bounded by a polynomial. We show that the function pR(n) of a regular language R is O(nk), for some k≥0, if and only if R can be represented as a finite union of the regular expressions of the form xy1*z1 ...yt*zt with a nonnegative integer t≤k+1, where x,y1,z1,..., yt, zt are all strings in ∑*.},
    Address = {Berlin, Heidelberg},
    Author = {Szilard, Andrew and Yu, Sheng and Zhang, Kaizhong and Shallit, Jeffrey},
    BookTitle = {Mathematical Foundations of Computer Science 1992},
    Editor = {Havel, Ivan M. and Koubek, V{\'a}clav},
    File = {Characterizing Regular Languages with Polynomial Densities S - zilard1992\_Chapter\_CharacterizingRegularLanguages.pdf},
    ISBN = {978-3-540-47291-9},
    Pages = {494--503},
    Publisher = {Springer Berlin Heidelberg},
    Title = {Characterizing regular languages with polynomial densities},
    Year = {1992},
    date-added = {2021-04-09 14:19:58 +0200},
    date-modified = {2021-04-09 14:19:58 +0200},
    doi = {10.1007/3-540-55808-X_48}
}

@inproceedings{10.1007/3-540-55808-X_48, Abstract = {A language L is said to have a polynomial density if the function pL.(n)={\textbrokenbar}L∩∑n{\textbrokenbar} of L is bounded by a polynomial. We show that the function pR(n) of a regular language R is O(nk), for some k≥0, if and only if R can be represented as a finite union of the regular expressions of the form xy1z1 ...ytzt with a nonnegative integer t≤k+1, where x,y1,z1,..., yt, zt are all strings in ∑*.}, Address = {Berlin, Heidelberg}, Author = {Szilard, Andrew and Yu, Sheng and Zhang, Kaizhong and Shallit, Jeffrey}, BookTitle = {Mathematical Foundations of Computer Science 1992}, Editor = {Havel, Ivan M. and Koubek, V{\'a}clav}, File = {Characterizing Regular Languages with Polynomial Densities S - zilard1992_Chapter_CharacterizingRegularLanguages.pdf}, ISBN = {978-3-540-47291-9}, Pages = {494--503}, Publisher = {Springer Berlin Heidelberg}, Title = {Characterizing regular languages with polynomial densities}, Year = {1992}, date-added = {2021-04-09 14:19:58 +0200}, date-modified = {2021-04-09 14:19:58 +0200}, doi = {10.1007/3-540-55808-X_48} }