Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Sets with small generalized Kolmogorov complexity

Autor
Balcazar, J. L.; Book, R.
Tipus d'activitat
Article en revista
Revista
Acta informatica
Data de publicació
1986-06-02
Volum
23
Número
6
Pàgina inicial
679
Pàgina final
688
DOI
https://doi.org/10.1007/BF00264313 Obrir en finestra nova
URL
http://link.springer.com/article/10.1007/BF00264313 Obrir en finestra nova
Resum
We study the class of sets with small generalized Kolmogorov complexity. The following results are established: 1. A set has small generalized Kolmogorov complexity if and only if it is “semi-isomorphic” to a tally set. 2. The class of sets with small generalized Kolmogorov complexity is properly included in the class of “self-p-printable” sets. 3. The class of self-p-printable sets is properly included in the class of sets with “selfproducible circuits”. 4. A set S has self-producib...
Paraules clau
Kolmogorov complexity
Grup de recerca
LARCA - Laboratori d'Algorísmia Relacional, Complexitat i Aprenentatge

Participants