How many holes can an unbordered partial word contain? (English) Zbl 1234.68327
Dediu, Adrian Horia (ed.) et al., Language and automata theory and applications. Third international conference, LATA 2009, Tarragona, Spain, April 2–8, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-00981-5/pbk). Lecture Notes in Computer Science 5457, 176-187 (2009).
Summary: Partial words are sequences over a finite alphabet that may have some undefined positions, or “holes”, that are denoted by \({\diamond}\)’s. A nonempty partial word is called bordered if one of its proper prefixes is compatible with one of its suffixes (here \({\diamond}\) is compatible with every letter in the alphabet); it is called unbordered otherwise. In this paper, we investigate the problem of computing the maximum number of holes a partial word of a fixed length can have and still fail to be bordered.
For the entire collection see [Zbl 1158.68001].
For the entire collection see [Zbl 1158.68001].
MSC:
| 68R15 | Combinatorics on words |
References:
| [1] | Berstel, J., Boasson, L.: Partial words and a theorem of Fine and Wilf. Theoretical Computer Science 218, 135–141 (1999) · Zbl 0916.68120 · doi:10.1016/S0304-3975(98)00255-2 |
| [2] | Blanchet-Sadri, F.: Algorithmic Combinatorics on Partial Words. Chapman & Hall/CRC Press (2007) · Zbl 1180.68205 · doi:10.1201/9781420060935 |
| [3] | Blanchet-Sadri, F.: Primitive partial words. Discrete Applied Mathematics 148, 195–213 (2005) · Zbl 1101.68643 · doi:10.1016/j.dam.2005.03.001 |
| [4] | Blanchet-Sadri, F., Davis, C., Dodge, J., Mercaş, R., Moorefield, M.: Unbordered partial words. Discrete Applied Mathematics (2008), doi:10.1016/j.dam.2008.04.004 · Zbl 1187.68289 · doi:10.1016/j.dam.2008.04.004 |
| [5] | Blanchet-Sadri, F.: Open problems on partial words. In: Bel-Enguix, G., Jiménez-López, M., Martín-Vide, C. (eds.) New Developments in Formal Languages and Applications, pp. 11–58. Springer, Berlin (2007) · Zbl 1156.68510 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
