Counting distinct squares in partial words
A well known result of Fraenkel and Simpson states that the number of distinct squares in a word of length n is bounded by 2n since at each position there are at most two distinct squares whose last occurrence start. In this paper, we investigate the problem of counting distinct squares in partial w...
Elmentve itt :
| Szerzők: | |
|---|---|
| Testületi szerző: | |
| Dokumentumtípus: | Cikk |
| Megjelent: |
2009
|
| Sorozat: | Acta cybernetica
19 No. 2 |
| Kulcsszavak: | Számítástechnika, Kibernetika |
| Tárgyszavak: | |
| Online Access: | http://acta.bibl.u-szeged.hu/12874 |
| LEADER | 02218nab a2200253 i 4500 | ||
|---|---|---|---|
| 001 | acta12874 | ||
| 005 | 20220617080742.0 | ||
| 008 | 161015s2009 hu o 0|| eng d | ||
| 022 | |a 0324-721X | ||
| 040 | |a SZTE Egyetemi Kiadványok Repozitórium |b hun | ||
| 041 | |a eng | ||
| 100 | 2 | |a Blanchet-Sadri Francine | |
| 245 | 1 | 0 | |a Counting distinct squares in partial words |h [elektronikus dokumentum] / |c Blanchet-Sadri Francine |
| 260 | |c 2009 | ||
| 300 | |a 465-477 | ||
| 490 | 0 | |a Acta cybernetica |v 19 No. 2 | |
| 520 | 3 | |a A well known result of Fraenkel and Simpson states that the number of distinct squares in a word of length n is bounded by 2n since at each position there are at most two distinct squares whose last occurrence start. In this paper, we investigate the problem of counting distinct squares in partial words, or sequences over a finite alphabet that may have some "do not know" symbols or "holes" (a (full) word is just a partial word without holes). A square in a partial word over a given alphabet has the form uu' where u is compatible with u, and consequently, such square is compatible with a number of full words over the alphabet that are squares. We consider the number of distinct full squares compatible with factors in a partial word with h holes of length n over a k-letter alphabet, and show that this number increases polynomially with respect to k in contrast with full words, and give bounds in a number of cases. For partial words with one hole, it turns out that there may be more than two squares that have their last occurrence starting at the same position. We prove that if such is the case, then the hole is in the shortest square. We also construct a partial word with one hole over a k-letter alphabet that has more than k squares whose last occurrence start at position zero. | |
| 650 | 4 | |a Természettudományok | |
| 650 | 4 | |a Számítás- és információtudomány | |
| 695 | |a Számítástechnika, Kibernetika | ||
| 700 | 0 | 1 | |a Mercaş Robert |e aut |
| 700 | 0 | 1 | |a Scott Geoffrey |e aut |
| 710 | |a International Conference on Automata and Formal Languages (12.) (2008) (Szeged) | ||
| 856 | 4 | 0 | |u http://acta.bibl.u-szeged.hu/12874/1/BlanchetSadri_2009_ActaCybernetica.pdf |z Dokumentum-elérés |