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.


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


Zbl 0564.00027