×

Enumeration of strings. (English) Zbl 0603.68074

Combinatorial algorithms on words, Proc. NATO Adv. Res. Workshop, Maratea/Italy 1984, NATO ASI Ser., Ser. F 12, 205-228 (1985).
[For the entire collection see Zbl 0564.00027.]
A survey is presented of some methods and results on counting words that satisfy various restrictions on subwords (i.e., blocks of consecutive symbols). Various applications to comma-free codes, games, pattern matching, and other subjects are indicated. The emphasis is on the unified treatment of those topics through the use of generating functions.

MSC:

68R99 Discrete mathematics in relation to computer science
94A45 Prefix, length-variable, comma-free codes

Citations:

Zbl 0564.00027