cjerdonek authored on Nov. 2, 2020, 6:04 p.m. | | Additions are marked like this |
In mathematics and computer science, a bifix-free word (or "unbordered" or "primary" word) is a word that has no strict prefix that is also a suffix. For example, "abaabb" is a bifix-free word because the only prefix ending in "bb" is the entire word. On the other hand, the word "abaab" is not bifix-free because "ab" is both a prefix and suffix. The phrase "bifix-free" comes from the word "bifix," which refers to a substring that is both a prefix and suffix. Bifix-free words arise, for example, in the context of the Critical Factorization Theorem. The theorem guarantees the existence of what are known as "critical points," and each critical point has a word associated to it (its "repetition word") that is bifix-free. | In mathematics and computer science, a bifix-free word (or "unbordered" or "primary" word) is a word that has no strict prefix that is also a suffix. For example, "abaabb" is a bifix-free word because the only prefix ending in "bb" is the entire word. On the other hand, the word "abaab" is not bifix-free because "ab" is both a prefix and suffix. The phrase "bifix-free" comes from the word "bifix," which refers to a substring that is both a prefix and suffix. Bifix-free words arise, for example, in the context of the Critical Factorization Theorem. The theorem guarantees the existence of what are known as "critical points," and each critical point has a word associated to it (its "repetition word") that is bifix-free. |
