On Automatic Families
| dc.contributor.author | JAIN, Sanjay | en_US |
| dc.contributor.author | ONG, Yuh Shin | en_US |
| dc.contributor.author | PU, Shi | en_US |
| dc.contributor.author | STEPHAN, Frank | en_US |
| dc.date.accessioned | 2010-03-30T07:06:23Z | en_US |
| dc.date.accessioned | 2017-01-23T07:00:14Z | |
| dc.date.available | 2010-03-30T07:06:23Z | en_US |
| dc.date.available | 2017-01-23T07:00:14Z | |
| dc.date.issued | 2010-01-19 | en_US |
| dc.description.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. | en_US |
| dc.format.extent | 227084 bytes | en_US |
| dc.format.mimetype | application/pdf | en_US |
| dc.identifier.uri | https://dl.comp.nus.edu.sg/xmlui/handle/1900.100/3112 | en_US |
| dc.language.iso | en_US | en_US |
| dc.relation.ispartofseries | TRB1/10 | en_US |
| dc.title | On Automatic Families | en_US |
| dc.type | Technical Report | en_US |