{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,15]],"date-time":"2026-06-15T14:43:51Z","timestamp":1781534631627,"version":"3.54.5"},"reference-count":18,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T00:00:00Z","timestamp":1778716800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62293481"],"award-info":[{"award-number":["62293481"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["92467301"],"award-info":[{"award-number":["92467301"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"award":["62293481"],"award-info":[{"award-number":["62293481"]}],"id":[{"id":"https:\/\/ror.org\/01h0zpd94","id-type":"ROR","asserted-by":"publisher"}]},{"award":["92467301"],"award-info":[{"award-number":["92467301"]}],"id":[{"id":"https:\/\/ror.org\/01h0zpd94","id-type":"ROR","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002766","name":"Beijing University of Posts and Telecommunications","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002766","id-type":"DOI","asserted-by":"crossref"}]},{"id":[{"id":"https:\/\/ror.org\/04w9fbh59","id-type":"ROR","asserted-by":"publisher"}]},{"name":"China Mobile Communications Group Co., Ltd. Joint Institute"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Classical Algorithmic Information Theory (AIT) provides a rigorous foundation for information-based similarity measurement, but classical formulations and their compression-based approximations largely operate at the syntactic level, making them sensitive to surface-level variation and insufficient for semantic equivalence. To address this limitation, this paper introduces Semantic Algorithmic Information Theory. The contributions are organized around three core aspects. First, regarding algorithmic extension, we formalize the Semantic Turing Machine System (STMS) to decouple abstract concepts from their diverse syntactic realizations. Within this framework, Semantic Complexity is defined as the minimum program length required to generate some realization in a synonymous set, thereby characterizing compact meaning representation. Second, to enable approximate computation, we move from the ideal, uncomputable semantic information distance to a model-based direct estimator of the Normalized Semantic Information Distance (NSID), which uses neural autoregressive models as conditional probability estimators. Finally, through experimental validation and comparative analysis, we show that the NSID estimator suppresses syntactic variance while preserving semantic structure. Empirical results indicate that NSID provides a practical, computable surrogate for semantic distance and improves upon classical syntactic metrics in evaluating cross-representational equivalence.<\/jats:p>","DOI":"10.3390\/e28050554","type":"journal-article","created":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T16:07:26Z","timestamp":1779206846000},"page":"554","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Semantic Algorithmic Information Theory: From Kolmogorov Complexity to Semantic Equivalence"],"prefix":"10.3390","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-4388-594X","authenticated-orcid":false,"given":"Jiatong","family":"Wu","sequence":"first","affiliation":[{"name":"State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-2853-794X","authenticated-orcid":false,"given":"Sen","family":"Wang","sequence":"additional","affiliation":[{"name":"China Mobile Research Institute, Beijing 100080, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8076-1867","authenticated-orcid":false,"given":"Kai","family":"Niu","sequence":"additional","affiliation":[{"name":"Key Laboratory of Universal Wireless Communications, Ministry of Education, Beijing University of Posts and Telecommunications, Beijing 100876, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-7878-4287","authenticated-orcid":false,"given":"Yifei","family":"She","sequence":"additional","affiliation":[{"name":"Key Laboratory of Universal Wireless Communications, Ministry of Education, Beijing University of Posts and Telecommunications, Beijing 100876, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0269-104X","authenticated-orcid":false,"given":"Ping","family":"Zhang","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2026,5,14]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","article-title":"A mathematical theory of communication","volume":"27","author":"Shannon","year":"1948","journal-title":"Bell Syst. Tech. J."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Li, M., and Vit\u00e1nyi, P. (2008). An Introduction to Kolmogorov Complexity and Its Applications, Springer.","DOI":"10.1007\/978-0-387-49820-1"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"3265","DOI":"10.1109\/TIT.2004.838346","article-title":"Kolmogorov\u2019s structure functions and model selection","volume":"50","author":"Vereshchagin","year":"2004","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1407","DOI":"10.1109\/18.681318","article-title":"Information distance","volume":"44","author":"Bennett","year":"1998","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"3250","DOI":"10.1109\/TIT.2004.838101","article-title":"The similarity metric","volume":"50","author":"Li","year":"2004","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1523","DOI":"10.1109\/TIT.2005.844059","article-title":"Clustering by compression","volume":"51","author":"Cilibrasi","year":"2005","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1602","DOI":"10.1109\/TPAMI.2014.2375175","article-title":"Normalized compression distance of multisets with applications","volume":"37","author":"Cohen","year":"2014","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Coltuc, D., Datcu, M., and Coltuc, D. (2018). On the use of normalized compression distances for image similarity detection. Entropy, 20.","DOI":"10.3390\/e20020099"},{"key":"ref_9","unstructured":"Mao, Y., Liu, P., Cui, T., Liu, C., and You, D. (2025, January 19\u201324). Low-resource fast text classification based on intra-class and inter-class distance calculation. Proceedings of the 31st International Conference on Computational Linguistics, Abu Dhabi, United Arab Emirates."},{"key":"ref_10","unstructured":"Del\u00e9tang, G., Ruoss, A., Duquenne, P.A., Catt, E., Genewein, T., Mattern, C., Grau-Moya, J., Wenliang, L.K., Aitchison, M., and Orseau, L. (2024, January 7\u201311). Language modeling is compression. Proceedings of the Twelfth International Conference on Learning Representations, Vienna, Austria."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"794","DOI":"10.1038\/s42256-025-01033-7","article-title":"Lossless data compression by large models","volume":"7","author":"Li","year":"2025","journal-title":"Nat. Mach. Intell."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Hurwitz, J., Nicholas, C., and Raff, E. (2025). Large Language Models and Normalized Compression Distance: Better Compression Yet Worse Accuracy. ECAI 2025, IOS Press.","DOI":"10.3233\/FAIA251322"},{"key":"ref_13","unstructured":"Vera, H.S., Dua, S., Zhang, B., Salz, D., Mullins, R., Panyam, S.R., Smoot, S., Naim, I., Zou, J., and Chen, F. (2025). Embeddinggemma: Powerful and lightweight text representations. arXiv."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Meister, C., Giulianelli, M., and Pimentel, T. (2024, January 12\u201316). Towards a similarity-adjusted surprisal theory. Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, Miami, FL, USA.","DOI":"10.18653\/v1\/2024.emnlp-main.921"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Giulianelli, M., Wallbridge, S., and Fern\u00e1ndez, R. (2023, January 6\u201310). Information value: Measuring utterance predictability as distance from plausible alternatives. Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, Singapore.","DOI":"10.18653\/v1\/2023.emnlp-main.343"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Niu, K., and Zhang, P. (2025). The Mathematical Theory of Semantic Communication, Springer.","DOI":"10.1007\/978-981-96-5132-0"},{"key":"ref_17","first-page":"7","article-title":"A mathematical theory of semantic communication","volume":"45","author":"Niu","year":"2024","journal-title":"J. Commun."},{"key":"ref_18","unstructured":"NLLB Team, Costa-Juss\u00e0, M.R., Cross, J., \u00c7elebi, O., Elbayad, M., Heafield, K., Heffernan, K., Kalbassi, E., Lam, J., and Licht, D. (2022). No Language Left Behind: Scaling human-centered machine translation. arXiv."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/28\/5\/554\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T04:18:43Z","timestamp":1779250723000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/28\/5\/554"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,14]]},"references-count":18,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2026,5]]}},"alternative-id":["e28050554"],"URL":"https:\/\/doi.org\/10.3390\/e28050554","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,14]]}}}