On normality in shifts of finite type (Q778523)

The contribution discusses an extension of the characterization of normality of infinite sequences in full shifts via non-compressibility by one-to-one finite-state transducers. Roughly speaking a sequence is normal if all subsequences of any given fixed length occur and occur with the same frequency. One-to-one finite-state transducers compute bijective functions that can easily be represented by a finite-state machine with output. The compression rate is defined as usual as the limit of the ratios between the lengths of the images of the finite prefixes of the sequence and the length of the prefixes. A given sequence is incompressible if there exists no one-to-one finite-state transducer that achieves a compression rate strictly below 1 for that sequence. The authors generalize the above-mentioned result to shifts of finite type instead of just full shifts. While full shifts are essentially all the infinite sequences that can be formed given a finite alphabet, a shift of finite type is obtained by declaring a finite set of subsequences, of which each is forbidden to occur anywhere in the sequence. To this end, they first show that various definitions of normality (aligned, strongly aligned, non-aligned) yield the same notion. Next, it is demonstrated that a sequence is compressible in the shift of finite type if and only if it is compressible beyond its relative entropy in the full shift, which is then used to establish the already mentioned main characterization theorem relating normality to incompressibility. The contribution is well written and should be generally understandable to any graduate of computer science or mathematics. It relies on a number of existing results, but full references are provided. The writing is slightly dense, but can be appreciated fully with some effort.