cjerdonek authored on Nov. 2, 2020, 6:38 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 (1) the 1-letter suffix "b" isn't a prefix, and (2) any suffix with at least two letters must end in "bb," and 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. |
