{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T06:35:02Z","timestamp":1759991702629},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2008,3,15]],"date-time":"2008-03-15T00:00:00Z","timestamp":1205539200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2009,8]]},"DOI":"10.1007\/s00224-008-9106-1","type":"journal-article","created":{"date-parts":[[2008,3,14]],"date-time":"2008-03-14T10:46:38Z","timestamp":1205491598000},"page":"381-406","source":"Crossref","is-referenced-by-count":9,"title":["Unavoidable Sets of Partial Words"],"prefix":"10.1007","volume":"45","author":[{"given":"F.","family":"Blanchet-Sadri","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"N. C.","family":"Brownstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andy","family":"Kalcic","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Justin","family":"Palumbo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"T.","family":"Weyand","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,3,15]]},"reference":[{"key":"9106_CR1","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1145\/360825.360855","volume":"18","author":"A.V. Aho","year":"1975","unstructured":"Aho, A.V., Corasick, M.J.: Efficient string machines, an aid to bibliographic research. Commun. ACM 18, 333\u2013340 (1975)","journal-title":"Commun. ACM"},{"key":"9106_CR2","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/S0304-3975(98)00255-2","volume":"218","author":"J. Berstel","year":"1999","unstructured":"Berstel, J., Boasson, L.: Partial words and a theorem of Fine and Wilf. Theor. Comput. Sci. 218, 135\u2013141 (1999)","journal-title":"Theor. Comput. Sci."},{"key":"9106_CR3","doi-asserted-by":"crossref","DOI":"10.1201\/9781420060935","volume-title":"Algorithmic Combinatorics on Partial Words","author":"F. Blanchet-Sadri","year":"2007","unstructured":"Blanchet-Sadri, F.: Algorithmic Combinatorics on Partial Words. Chapman & Hall\/CRC Press, Boca Raton (2007)"},{"key":"9106_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1007\/978-3-540-73208-2_12","volume-title":"DLT 2007","author":"F. Blanchet-Sadri","year":"2007","unstructured":"Blanchet-Sadri, F., Brownstein, N.C., Palumbo, J.: Two element unavoidable sets of partial words. In: Harju, T., Karhum\u00e4ki, J., Lepist\u00f6, A. (eds.) DLT 2007, 11th International Conference on Developments in Language Theory, July 3\u20136, 2007, Turku, Finland. Lecture Notes in Computer Science, vol.\u00a04588, pp.\u00a096\u2013107. Springer, Berlin (2007). www.uncg.edu\/mat\/research\/unavoidablesets"},{"key":"9106_CR5","unstructured":"Blanchet-Sadri, F., Jungers, R., Palumbo, J.: Testing avoidability of sets of partial words is hard. Preprint"},{"key":"9106_CR6","doi-asserted-by":"crossref","first-page":"5122","DOI":"10.1109\/TIT.2006.883615","volume":"52","author":"V.D. Blondel","year":"2006","unstructured":"Blondel, V.D., Jungers, R., Protasov, V.: On the complexity of computing the capacity of codes that avoid forbidden difference patterns. IEEE Trans. Inf. Theory 52, 5122\u20135127 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9106_CR7","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/BF01209712","volume":"30","author":"J. Cassaigne","year":"1993","unstructured":"Cassaigne, J.: Unavoidable binary patterns. Acta Inform. 30, 385\u2013395 (1993)","journal-title":"Acta Inform."},{"key":"9106_CR8","series-title":"Technology and Foundations","first-page":"459","volume-title":"IFIP World Computer Congress 1994","author":"J. Cassaigne","year":"1994","unstructured":"Cassaigne, J.: An algorithm to test if a given circular HDOL-language avoids a pattern. In: IFIP World Computer Congress 1994. Technology and Foundations, vol. 1, pp. 459\u2013464. Elsevier, Amsterdam (1994)"},{"key":"9106_CR9","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/0166-218X(84)90014-3","volume":"9","author":"C. Choffrut","year":"1984","unstructured":"Choffrut, C., Culik II, K.: On extendibility of unavoidable sets. Discrete Appl. Math. 9, 125\u2013137 (1984)","journal-title":"Discrete Appl. Math."},{"key":"9106_CR10","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/978-3-642-59136-5_6","volume-title":"Handbook of Formal Languages","author":"C. Choffrut","year":"1997","unstructured":"Choffrut, C., Karhum\u00e4ki, J.: Combinatorics of words. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 1, pp. 329\u2013438. Springer, Berlin (1997). Chap.\u00a06"},{"key":"9106_CR11","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/0304-3975(82)90124-4","volume":"27","author":"A. Ehrenfeucht","year":"1983","unstructured":"Ehrenfeucht, A., Haussler, D., Rozenberg, G.: On regularity of context-free languages. Theor. Comput. Sci. 27, 311\u2013322 (1983)","journal-title":"Theor. Comput. Sci."},{"key":"9106_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1007\/11493785_20","volume-title":"Partial Words for DNA Coding","author":"P. Leupold","year":"2005","unstructured":"Leupold, P.: Partial Words for DNA Coding. Lecture Notes in Computer Science, vol. 3384, pp. 224\u2013234. Springer, Berlin (2005)"},{"key":"9106_CR13","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781107326019","volume-title":"Algebraic Combinatorics on Words","author":"M. Lothaire","year":"2002","unstructured":"Lothaire, M.: Algebraic Combinatorics on Words. Cambridge University Press, Cambridge (2002)"},{"key":"9106_CR14","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1051\/ita\/1995290503391","volume":"29","author":"L. Rosaz","year":"1995","unstructured":"Rosaz, L.: Unavoidable languages, cuts and innocent sets of words. RAIRO Theor. Inform. Appl. 29, 339\u2013382 (1995)","journal-title":"RAIRO Theor. Inform. Appl."},{"key":"9106_CR15","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/S0304-3975(97)00031-5","volume":"201","author":"L. Rosaz","year":"1998","unstructured":"Rosaz, L.: Inventories of unavoidable languages and the word-extension conjecture. Theor. Comput. Sci. 201, 151\u2013170 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"9106_CR16","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/BF01178567","volume":"29","author":"P. Roth","year":"1992","unstructured":"Roth, P.: Every binary pattern of length six is avoidable on the two-letter alphabet. Acta Inform. 29, 95\u2013106 (1992)","journal-title":"Acta Inform."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-008-9106-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-008-9106-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-008-9106-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T07:51:35Z","timestamp":1558684295000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-008-9106-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3,15]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["9106"],"URL":"https:\/\/doi.org\/10.1007\/s00224-008-9106-1","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,3,15]]}}}