Abstract
The notion of an unavoidable set of words appears frequently in the fields of mathematics and theoretical computer science, in particular with its connection to the study of combinatorics on words. The theory of unavoidable sets has seen extensive study over the past twenty years. In this paper we extend the definition of unavoidable sets of words to unavoidable sets of partial words. Partial words, or finite sequences that may contain a number of “do not know” symbols or holes, appear in natural ways in several areas of current interest such as molecular biology, data communication, DNA computing, etc. We demonstrate the utility of the notion of unavoidability on partial words by making use of it to identify several new classes of unavoidable sets of full words. Along the way we begin work on classifying the unavoidable sets of partial words of small cardinality. We pose a conjecture, and show that affirmative proof of this conjecture gives a sufficient condition for classifying all the unavoidable sets of partial words of size two. Lastly we give a result which makes the conjecture easy to verify for a significant number of cases.
This material is based upon work supported by the National Science Foundation under Grant No. DMS–0452020. A World Wide Web server interface at www.uncg.edu/mat/research/unavoidablesets has been established for automated use of the program. We thank the referees of preliminary versions of this paper for their very valuable comments and suggestions.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aho, A.V., Corasick, M.J.: Efficient string machines, an aid to bibliographic research. Comm. ACM 18, 333–340 (1975)
Berstel, J., Boasson, L.: Partial words and a theorem of Fine and Wilf. Theoret. Comput. Sci. 218, 135–141 (1999)
Blanchet-Sadri, F.: Codes, orderings, and partial words. Theoret. Comput. Sci. 329, 177–202 (2004)
Blanchet-Sadri, F.: Primitive partial words. Discrete Appl. Math. 148, 195–213 (2005)
Blanchet-Sadri, F., Duncan, S.: Partial Words and the Critical Factorization Theorem. J. Combin. Theory Ser. A 109, 221–245 (2005), http://www.uncg.edu/mat/cft/
Choffrut, C., Culik II, K.: On extendibility of unavoidable sets. Discrete Appl. Math. 9, 125–137 (1984)
Choffrut, C., Karhumäki, J.: Combinatorics of Words. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 1, pp. 329–438. Springer, Heidelberg (1997)
Ehrenfeucht, A., Haussler, D., Rozenberg, G.: On regularity of context-free languages. Theoret. Comput. Sci. 27, 311–322 (1983)
Kolpakov, R., Kucherov, G.: Finding Approximate Repetitions Under Hamming Distance. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol. 2161, pp. 170–181. Springer-Verlag, Heidelberg (2001)
Kolpakov, R., Kucherov, G.: Finding Approximate Repetitions Under Hamming Distance. Theoret. Comput. Sci. 33, 135–156 (2003)
Landau, G., Schmidt, J.: An Algorithm for Approximate Tandem Repeats. In: Apostolico, A., Crochemore, M., Galil, Z., Manber, U. (eds.) Combinatorial Pattern Matching. LNCS, vol. 684, pp. 120–133. Springer-Verlag, Heidelberg (1993)
Landau, G.M., Schmidt, J.P., Sokol, D.: An Algorithm for Approximate Tandem Repeats. J. Comput. Biology 8, 1–18 (2001)
Lothaire, M.: Algebraic Combinatorics on Words. Cambridge University Press, Cambridge (2002)
Rosaz, L.: Inventories of unavoidable languages and the word-extension conjecture. Theoret. Comput. Sci. 201, 151–170 (1998)
Schmidt, J.P.: All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings. SIAM J. Comput. 27, 972–992 (1998)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Blanchet-Sadri, F., Brownstein, N.C., Palumbo, J. (2007). Two Element Unavoidable Sets of Partial Words. In: Harju, T., Karhumäki, J., Lepistö, A. (eds) Developments in Language Theory. DLT 2007. Lecture Notes in Computer Science, vol 4588. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73208-2_12
Download citation
DOI: https://doi.org/10.1007/978-3-540-73208-2_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73207-5
Online ISBN: 978-3-540-73208-2
eBook Packages: Computer ScienceComputer Science (R0)