Conditional automatic complexity and its metrics. (English) Zbl 07900282
Wu, Weili (ed.) et al., Computing and combinatorics. 29th international conference, COCOON 2023, Hawaii, HI, USA, December 15–17, 2023. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 14422, 15-28 (2024).
Summary: Li, Chen, Li, Ma, and Vitányi (2004) introduced a similarity metric based on Kolmogorov complexity. It followed work by Shannon in the 1950s on a metric based on entropy. We define two computable similarity metrics, analogous to the Jaccard distance and Normalized Information Distance, based on conditional automatic complexity and show that they satisfy all axioms of metric spaces.
For the entire collection see [Zbl 1543.68018].
For the entire collection see [Zbl 1543.68018].
MSC:
| 68Rxx | Discrete mathematics in relation to computer science |
References:
| [1] | Gács, P.; Tromp, JT; Vitányi, PMB, Algorithmic statistics, IEEE Trans. Inform. Theory, 47, 6, 2443-2463, 2001 · Zbl 1021.94004 · doi:10.1109/18.945257 |
| [2] | Gač, P., The symmetry of algorithmic information, Dokl. Akad. Nauk SSSR, 218, 1265-1267, 1974 |
| [3] | Horibe, Y., A note on entropy metrics, Inf. Control, 22, 403-404, 1973 · Zbl 0254.94021 · doi:10.1016/S0019-9958(73)90554-8 |
| [4] | Hyde, K.K., Kjos-Hanssen, B.: Nondeterministic automatic complexity of overlap-free and almost square-free words. Electron. J. Combin. 22(3), 18 (2015) · Zbl 1334.68173 |
| [5] | Kjos-Hanssen, B.: Automatic complexity of shift register sequences. Discrete Math. 341(9), 2409-2417 (2018). doi:10.1016/j.disc.2018.05.015 · Zbl 1422.94024 |
| [6] | Kjos-Hanssen, B.: Few paths, fewer words: model selection with automatic structure functions. Exp. Math. 28(1), 121-127 (2019). doi:10.1080/10586458.2017.1368048 · Zbl 1419.68057 |
| [7] | Kjos-Hanssen, B.: An incompressibility theorem for automatic complexity. Forum Math. Sigma 9, e62 (2021). doi:10.1017/fms.2021.58 · Zbl 1537.68075 |
| [8] | Kjos-Hanssen, B.: Interpolating between the Jaccard distance and an analogue of the normalized information distance. J. Logic Comput. 32(8), 1611-1623 (2022). doi:10.1093/logcom/exac069. doi:10.1093/logcom/exac069 · Zbl 07638203 |
| [9] | Li, M., Chen, X., Li, X., Ma, B., Vitányi, P.M.B.: The similarity metric. IEEE Trans. Inform. Theory 50(12), 3250-3264 (2004). doi:10.1109/TIT.2004.838101 · Zbl 1316.68052 |
| [10] | Lyndon, RC; Schützenberger, MP, The equation \(a^M=b^Nc^P\) in a free group, Michigan Math. J., 9, 289-298, 1962 · Zbl 0106.02204 · doi:10.1307/mmj/1028998766 |
| [11] | Shallit, J., A Second Course in Formal Languages and Automata Theory, 2008, New York, NY, USA: Cambridge University Press, New York, NY, USA · Zbl 1163.68025 · doi:10.1017/CBO9780511808876 |
| [12] | Shallit, J., Wang, M.W.: Automatic complexity of strings. J. Autom. Lang. Comb. 6(4), 537-554 (2001). 2nd Workshop on Descriptional Complexity of Automata, Grammars and Related Structures, London, ON (2000) · Zbl 1004.68077 |
| [13] | Shannon, C., The lattice theory of information, Trans. IRE Prof. Group Inf. Theory, 1, 1, 105-107, 1953 · Zbl 1116.94305 · doi:10.1109/TIT.1953.1188572 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
