Browsing by Author "PU, Shi"

Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    On Automatic Families
    (2010-01-19) JAIN, Sanjay; ONG, Yuh Shin; PU, Shi; STEPHAN, Frank
    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.