Computing the partial word avoidability indices of ternary patterns |
| |
Institution: | 1. Department of Computer Science, University of North Carolina, P.O. Box 26170, Greensboro, NC 27402-6170, USA;2. Department of Mathematics, Mathematics Building, University of Maryland, College Park, MD 20742, USA;3. School of Mathematics, Georgia Institute of Technology, 686 Cherry Street, Atlanta, GA 30332-0160, USA |
| |
Abstract: | We study pattern avoidance in the context of partial words. The problem of classifying the avoidable binary patterns has been solved, so we move on to ternary and more general patterns. Our results, which are based on morphisms (iterated or not), determine all the ternary patterns? avoidability indices or at least give bounds for them. |
| |
Keywords: | Combinatorics on words Partial words Pattern avoidance Ternary pattern Avoidability index |
本文献已被 ScienceDirect 等数据库收录! |
|