{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T00:41:10Z","timestamp":1760402470671,"version":"build-2065373602"},"reference-count":35,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2020,1,4]],"date-time":"2020-01-04T00:00:00Z","timestamp":1578096000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Opening Foundation of Guangxi Colleges and Universities Key Laboratory of Complex System Optimization and Big Data Processing","award":["2017CSOBDP0103"],"award-info":[{"award-number":["2017CSOBDP0103"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>In this paper, we give a definition for fuzzy Kolmogorov complexity. In the classical setting, the Kolmogorov complexity of a single finite string is the length of the shortest program that produces this string. We define the fuzzy Kolmogorov complexity as the minimum classical description length of a finite-valued fuzzy language through a universal finite-valued fuzzy Turing machine that produces the desired fuzzy language. The classical Kolmogorov complexity is extended to the fuzzy domain retaining classical descriptions. We show that our definition is robust, that is to say, the complexity of a finite-valued fuzzy language does not depend on the underlying finite-valued fuzzy Turing machine.<\/jats:p>","DOI":"10.3390\/e22010066","type":"journal-article","created":{"date-parts":[[2020,1,6]],"date-time":"2020-01-06T03:48:48Z","timestamp":1578282528000},"page":"66","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Fuzzy Kolmogorov Complexity Based on a Classical Description"],"prefix":"10.3390","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2283-9459","authenticated-orcid":false,"given":"Songsong","family":"Dai","sequence":"first","affiliation":[{"name":"School of Electronics and Information Engineering, Taizhou University, Taizhou 318000, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,1,4]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0019-9958(64)90223-2","article-title":"A formal theory of inductive inference, part I","volume":"7","author":"Solomonoff","year":"1964","journal-title":"Inf. Control"},{"key":"ref_2","first-page":"1","article-title":"Three approaches to the quantitative definition of information","volume":"1","author":"Kolmogorov","year":"1965","journal-title":"Probl. Inf. Transm."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1145\/321356.321363","article-title":"On the length of programs for computing finite binary sequences","volume":"13","author":"Chaitin","year":"1966","journal-title":"J. ACM"},{"key":"ref_4","first-page":"230","article-title":"On computable numbers, with an application to the Entscheidungs problem","volume":"42","author":"Turing","year":"1936","journal-title":"Proc. Lond. Math. Soc."},{"key":"ref_5","first-page":"544","article-title":"On computable numbers, with an application to the Entscheidungs problem. A Correction","volume":"43","author":"Turing","year":"1937","journal-title":"Proc. Lond. Math. Soc."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Li, M., and Vit\u00e1nyi, P.M.B. (2008). An Introduction to Kolmogorov Complexity and Its Applications, Springer. [3rd ed.].","DOI":"10.1007\/978-0-387-49820-1"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1007\/s11390-008-9152-9","article-title":"New information distance measure and its application in question answering system","volume":"23","author":"Zhang","year":"2008","journal-title":"J. Comput. Sci. Technol."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/S0304-3975(01)00034-2","article-title":"Combinatorial interpretation of Kolmogorov complexity","volume":"271","author":"Romashchenko","year":"2002","journal-title":"Theor. Comput. Sci."},{"key":"ref_9","unstructured":"Mahmud, M.M., and Ray, S.R. (2007, January 3\u20136). Transfer learning using Kolmogorov complexity: Basic theory and empirical evaluations. Proceedings of the 20th International Conference on Neural Information Processing Systems (NIPS\u201907), Vancouver, BC, Canada."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1093\/bioinformatics\/17.2.149","article-title":"An information-based sequence distance and its application to whole mito chondrial genome phylogeny","volume":"17","author":"Li","year":"2001","journal-title":"Bioinformatics"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1135","DOI":"10.3390\/e17031135","article-title":"Comparing security notions of secret sharing schemes","volume":"17","author":"Dai","year":"2015","journal-title":"Entropy"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Bi, L., Dai, S., and Hu, B. (2017). Normalized unconditional \u03f5-security of private-key encryption. Entropy, 19.","DOI":"10.3390\/e19030100"},{"key":"ref_13","first-page":"97","article-title":"Quantum theory, the Church-Turing principle and the universal quantum computer","volume":"400","author":"Deutsch","year":"1985","journal-title":"Proc. R. Soc. A"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1411","DOI":"10.1137\/S0097539796300921","article-title":"Quantum complexity theory","volume":"26","author":"Bernstein","year":"1997","journal-title":"SIAM J. Comput."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"2464","DOI":"10.1109\/18.945258","article-title":"Quantum Kolmogorov complexity based on classical descriptions","volume":"47","year":"2001","journal-title":"IEEE Trans. Infor. Theory"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1006\/jcss.2001.1765","article-title":"Quantum Kolmogorov complexity","volume":"63","author":"Berthiaume","year":"2001","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1016\/S0019-9958(68)90211-8","article-title":"Fuzzy algorithms","volume":"12","author":"Zadeh","year":"1968","journal-title":"Inf. Control"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1016\/0020-0255(69)90025-5","article-title":"Note on fuzzy languages","volume":"1","author":"Lee","year":"1969","journal-title":"Inf. Sci."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1016\/S0019-9958(70)80032-8","article-title":"Fuzzy algorithms","volume":"17","author":"Santos","year":"1970","journal-title":"Inf. Control"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/j.tcs.2003.12.004","article-title":"Characterizing the super-Turing computing power and efficiency of classical fuzzy Turing machines","volume":"317","author":"Wiedermann","year":"2004","journal-title":"Theor. Comput. Sci."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1072","DOI":"10.1016\/j.fss.2007.10.013","article-title":"On the computing power of fuzzy Turing machines","volume":"159","author":"Bedregal","year":"2008","journal-title":"Fuzzy Sets Syst."},{"key":"ref_22","first-page":"1445","article-title":"Approximation and universality of fuzzy Turing machines","volume":"51","author":"Li","year":"2008","journal-title":"Sci. China Ser. F"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1491","DOI":"10.1109\/TFUZZ.2008.2004990","article-title":"Fuzzy Turing machines: Variants and universality","volume":"16","author":"Li","year":"2008","journal-title":"IEEE Trans. Fuzzy Syst."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"3453","DOI":"10.1016\/j.fss.2009.08.003","article-title":"Lattice-valued fuzzy Turing machines: Computing power universality and efficency","volume":"160","author":"Li","year":"2009","journal-title":"Fuzzy Sets Syst."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1407","DOI":"10.3724\/SP.J.1016.2012.01407","article-title":"Turing machine based on quantum logic and their universality","volume":"35","author":"Li","year":"2012","journal-title":"Chin. J. Comput."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/j.fss.2012.03.001","article-title":"Automata theory based on complete residuated lattice-valued logic: Turing machines","volume":"208","author":"Wu","year":"2012","journal-title":"Fuzzy Sets Syst."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1109\/91.493904","article-title":"Fuzzy logic-computing with words","volume":"4","author":"Zadeh","year":"1996","journal-title":"IEEE Trans. Fuzzy Syst."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"H\u00e1jek, P. (1998). Metamathematics of Fuzzy Logic, Kluwer.","DOI":"10.1007\/978-94-011-5300-3"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/S0019-9958(72)90199-4","article-title":"A definition of non probabilistic entropy in the setting of fuzzy set theory","volume":"20","author":"Luca","year":"1972","journal-title":"Inf. Control"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/S0019-9958(74)80023-9","article-title":"Entropy of L-fuzzy set","volume":"24","author":"Luca","year":"1974","journal-title":"Inf. Control"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/0020-0255(92)90051-9","article-title":"higher order fuzzy entropy and hybrid entropy of a fuzzy set","volume":"61","author":"Pal","year":"1992","journal-title":"Inf. Sci."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1080\/03081077908547452","article-title":"On the measure of fuzziness and negation. Part I: Membership in the unit interval","volume":"5","author":"Yager","year":"1979","journal-title":"Int. J. Gen. Syst."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1016\/S0019-9958(80)90156-4","article-title":"On the measure of fuzziness and negation. Part II: Lattice","volume":"4","author":"Yager","year":"1980","journal-title":"Inf. Control"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"867","DOI":"10.1134\/S1023193518130451","article-title":"The Kolmogorov-Sinai Entropy in the Setting of Fuzzy Sets for Atmospheric Corrosion Image Texture Analysis","volume":"54","author":"Song","year":"2018","journal-title":"Russ. J. Electrochem."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1108\/ACMM-04-2019-2107","article-title":"Measuring the atmospheric corrosion of Q235B and T91 steels using gray value, wavelet analysis and fuzzy Kolmogorov-Sinai entropy","volume":"66","author":"Wang","year":"2019","journal-title":"Anti-Corros. Method Mater."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/22\/1\/66\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T13:42:18Z","timestamp":1760362938000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/22\/1\/66"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,4]]},"references-count":35,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2020,1]]}},"alternative-id":["e22010066"],"URL":"https:\/\/doi.org\/10.3390\/e22010066","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2020,1,4]]}}}