On Automatic Families
No Thumbnail Available
Date
2010-01-19
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This paper summarises previous work on automatic families. It then investigates a natural measure which exists inside every automatic family: the size of a regular language in this family is just the length of its index. This measure satisfies various properties similar to those of Kolmogorov complexity. Furthermore, there is a quite natural extension of it to all regular languages such that, for each automatic family, the new general measure differs from that of the least index only by up to a constant. However, this generalisation fails to have several properties similar to Kolmogorov complexity. Furthermore, a characterisation is given regarding when a class of languages is a subclass of an automatic family.