Insertion-Deletion Networks

Word networks - collections of words of a common length that can be joined by single-letter substitutions, such as the sequence BANKER-BANTER-BATTER-BETTER-SETTER-SETTEE-SETTLE linking BANKER and SETTLE - were studied in some detail in the May and August 1973 issues of Word Ways. Non-repeating sequences from word networks, commonly called word ladders and doublets, have a long history; Lewis Carroll, among others, challenged readers to join two specified words by a ladder. However, word networks have one serious flaw: they do not allow one to incorporate words of different lengths. This can be rectified by the concept of an insertion-deletion network, in which a word of n letters is linked to a word of n-1 letters if the first can be converted to the second by the deletion of a single letter. (In the reverse direction, the linage is called the insertion of a letter in a word to form another word.) Extremely complex insertion-deletion networks containing many loops and branches can be constructed; by examining them, one can easily ascertain whether or not one word can be reached from another by successive insertions and deletions. Further, one can calculate the minimum number of such steps required