{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,18]],"date-time":"2024-10-18T23:10:31Z","timestamp":1729293031234,"version":"3.27.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,4,20]],"date-time":"2023-04-20T00:00:00Z","timestamp":1681948800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,4,20]],"date-time":"2023-04-20T00:00:00Z","timestamp":1681948800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["New Gener. Comput."],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Introduction<\/jats:title><jats:p>This paper focuses on cognitive computing approaches to identifying the basic-level in a hierarchical structure. In particular, it provides asymptotic time complexities of the identification of the basic-level for five basic-levelness measures, i.e., feature-possession, category utility, category attentional slip, category\u2019s cue validity with global threshold, category\u2019s cue validity with feature-possession.<\/jats:p><\/jats:sec><jats:sec><jats:title>Methods<\/jats:title><jats:p>Asymptotic time complexities were analytically determined for each basic-levelness measure separately.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>First, the time complexity of auxiliary measures (i.e., utilized by basic-levelness measures) was determined. Second, the time complexity of the identification of the basic-level was determined. Finally, an optimization of the identification was proposed.<\/jats:p><\/jats:sec><jats:sec><jats:title>Conclusions<\/jats:title><jats:p>The identification of the basic-level requires polynomial time. In particular, category attentional slip and category\u2019s cue validity with feature-possession require an additional iteration through all objects, which increase the time complexity.<\/jats:p><\/jats:sec>","DOI":"10.1007\/s00354-023-00216-3","type":"journal-article","created":{"date-parts":[[2023,4,20]],"date-time":"2023-04-20T19:33:54Z","timestamp":1682019234000},"page":"445-473","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Asymptotic Time Complexity of Identification of Basic-level"],"prefix":"10.1007","volume":"41","author":[{"given":"Mariusz","family":"Mulka","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,4,20]]},"reference":[{"issue":"3","key":"216_CR1","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1016\/0010-0285(76)90013-X","volume":"8","author":"E Rosch","year":"1976","unstructured":"Rosch, E., Mervis, C.B., Gray, W.D., Johnson, D.M., Boyes-Braem, P.: Basic objects in natural categories. Cogn. Psychol. 8(3), 382\u2013439 (1976). https:\/\/doi.org\/10.1016\/0010-0285(76)90013-X","journal-title":"Cogn. Psychol."},{"doi-asserted-by":"crossref","unstructured":"Taylor, J.: Ten Lectures on Applied Cognitive Linguistics. Brill, Leiden (2018). https:\/\/brill.com\/view\/title\/34998","key":"216_CR2","DOI":"10.1163\/9789004347564"},{"doi-asserted-by":"crossref","unstructured":"Rosch E.: Principles of categorization. In: Rosch, E., Lloyd, B.B. (eds.) Cognition and Categorization, pp. 27\u201348, Erlbaum, Hillsdale, NJ (1978)","key":"216_CR3","DOI":"10.4324\/9781032633275-4"},{"issue":"7","key":"216_CR4","doi-asserted-by":"publisher","first-page":"1427","DOI":"10.1162\/jocn\\_a_00790","volume":"27","author":"MC Iordan","year":"2015","unstructured":"Iordan, M.C., Greene, M.R., Beck, D.M., Fei-Fei, L.: Basic level category structure emerges gradually across human ventral visual cortex. J. Cogn. Neurosci. 27(7), 1427\u20131446 (2015). https:\/\/doi.org\/10.1162\/jocn_a_00790. (PMID:25811711)","journal-title":"J. Cogn. Neurosci."},{"issue":"1","key":"216_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0022-5371(82)90412-1","volume":"21","author":"GL Murphy","year":"1982","unstructured":"Murphy, G.L., Smith, E.E.: Basic-level superiority in picture categorization. J Verbal Learn Verbal Behav 21(1), 1\u201320 (1982). https:\/\/doi.org\/10.1016\/S0022-5371(82)90412-1","journal-title":"J Verbal Learn Verbal Behav"},{"issue":"6","key":"216_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1371\/journal.pone.0005927","volume":"4","author":"MJM Mac\u00e9","year":"2009","unstructured":"Mac\u00e9, M.J.M., Joubert, O.R., Nespoulous, J.L., Fabre-Thorpe, M.: The time-course of visual categorizations: you spot the animal faster than the bird. PLoS One 4(6), 1\u201312 (2009). https:\/\/doi.org\/10.1371\/journal.pone.0005927","journal-title":"PLoS One"},{"issue":"2","key":"216_CR7","doi-asserted-by":"publisher","first-page":"603","DOI":"10.1111\/coin.12167","volume":"34","author":"A Gkiokas","year":"2018","unstructured":"Gkiokas, A., Cristea, A.I.: Cognitive agents and machine learning by example: representation with conceptual graphs. Comput. Intell. 34(2), 603\u2013634 (2018). https:\/\/doi.org\/10.1111\/coin.12167","journal-title":"Comput. Intell."},{"key":"216_CR8","doi-asserted-by":"publisher","DOI":"10.7312\/kell16856","volume-title":"Smart Machines: IBM\u2019s Watson and the Era of Cognitive Computing","author":"JE Kelly","year":"2013","unstructured":"Kelly, J.E., Hamm, S.: Smart Machines: IBM\u2019s Watson and the Era of Cognitive Computing. Columbia University Press, Columbia (2013). https:\/\/doi.org\/10.7312\/kell16856"},{"issue":"3","key":"216_CR9","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1037\/0033-2909.94.3.423","volume":"94","author":"GV Jones","year":"1983","unstructured":"Jones, G.V.: Identifying basic categories. Psychol. Bull. 94(3), 423\u2013428 (1983). https:\/\/doi.org\/10.1037\/0033-2909.94.3.423","journal-title":"Psychol. Bull."},{"doi-asserted-by":"crossref","unstructured":"Corter, J.E., Gluck, M.A.: Explaining basic categories: feature predictability and information. Psychol. Bull. 111(2), 291\u2013303 (1992). http:\/\/content.apa.org.arugula.cc.columbia.edu:2048\/journals\/bul\/111\/2\/291","key":"216_CR10","DOI":"10.1037\/0033-2909.111.2.291"},{"unstructured":"Gosselin, F., Schyns, P.: Debunking the Basic Level, pp. 277\u2013282. Lawrence Erlbaum Associates (1997). Cognitive Science Society (US) Conference\/\/Proceedings. https:\/\/books.google.pl\/books?id=sQyJiDk45HEC","key":"216_CR11"},{"doi-asserted-by":"publisher","unstructured":"Katarzyniak, R.P., Lorkiewicz, W., Mulka, M., Krejcar, O.: Towards basic level categories in cognitive agents. In: 2017 13th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD), pp. 384\u2013391. (2017). https:\/\/doi.org\/10.1109\/FSKD.2016.7603370","key":"216_CR12","DOI":"10.1109\/FSKD.2016.7603370"},{"doi-asserted-by":"publisher","unstructured":"Mulka, M., Lorkiewicz, W.A.: Measures for extracting basic-level categories. In: Li, W., Li, Q., Wang, L. (Eds.) 11th International Congress on Image and Signal Processing, BioMedical Engineering and Informatics, CISP-BMEI 2018, Beijing, China, October 13\u201315, pp. 1\u20136, 2018. IEEE (2018). https:\/\/doi.org\/10.1109\/CISP-BMEI.2018.8633202","key":"216_CR13","DOI":"10.1109\/CISP-BMEI.2018.8633202"},{"key":"216_CR14","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.neucom.2016.02.070","volume":"208","author":"Y Cai","year":"2016","unstructured":"Cai, Y., Chen, W.H., Leung, H.F., Li, Q., Xie, H., Lau, R.Y., Min, H., Wang, F.L.: Context-aware ontologies generation with basic level concepts from collaborative tags. Neurocomputing 208, 25\u201338 (2016). https:\/\/doi.org\/10.1016\/j.neucom.2016.02.070. (SI: BridgingSemantic)","journal-title":"Neurocomputing"},{"doi-asserted-by":"publisher","unstructured":"Li, J., Du, Q., Cai, Y., Wu, J., Ren, D.: Detecting basic level categories by term weighting and feature entropy. In: IEEE International Conference on Big Data and Smart Computing, BigComp 2019, Kyoto, Japan, February 27\u2013March 2, 2019, pp. 1\u20136. IEEE (2019). https:\/\/doi.org\/10.1109\/BIGCOMP.2019.8679496","key":"216_CR15","DOI":"10.1109\/BIGCOMP.2019.8679496"},{"key":"216_CR16","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-030-32456-8_25","volume-title":"Advances in Natural Computation, Fuzzy Systems and Knowledge Discovery","author":"M Mulka","year":"2020","unstructured":"Mulka, M., Lorkiewicz, W., Katarzyniak, R.P.: Extraction of basic-level categories using dendrogram and multidendrogram. In: Liu, Y., Wang, L., Zhao, L., Yu, Z. (eds.) Advances in Natural Computation, Fuzzy Systems and Knowledge Discovery, pp. 235\u2013243. Springer International Publishing, Cham (2020)"},{"issue":"1","key":"216_CR17","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/BF01890115","volume":"1","author":"WHE Day","year":"1984","unstructured":"Day, W.H.E., Edelsbrunner, H.: Efficient algorithms for agglomerative hierarchical clustering methods. J. Classif. 1(1), 7\u201324 (1984). https:\/\/doi.org\/10.1007\/BF01890115","journal-title":"J. Classif."},{"key":"216_CR18","doi-asserted-by":"publisher","first-page":"664","DOI":"10.1016\/j.neucom.2017.06.053.","volume":"267","author":"A Saxena","year":"2017","unstructured":"Saxena, A., Prasad, M., Gupta, A., Bharill, N., Patel, O.P., Tiwari, A., Er, M.J., Ding, W., Lin, C.T.: A review of clustering techniques and developments. Neurocomputing 267, 664\u2013681 (2017). https:\/\/doi.org\/10.1016\/j.neucom.2017.06.053. (www.sciencedirect.com\/science\/article\/pii\/S0925231217311815)","journal-title":"Neurocomputing"},{"issue":"2","key":"216_CR19","first-page":"135","volume":"191","author":"J Hoffmann","year":"1983","unstructured":"Hoffmann, J., Ziessler, C.: Objektidentifikation in k\u00fcnstlichen Begriffshierarchien [Object identification in artificial conceptual hierarchies]. Z. Psychol. 191(2), 135\u2013167 (1983)","journal-title":"Z. Psychol."},{"issue":"5","key":"216_CR20","doi-asserted-by":"publisher","first-page":"423","DOI":"10.3758\/BF03199563","volume":"19","author":"GL Murphy","year":"1991","unstructured":"Murphy, G.L.: Parts in object concepts: experiments with artificial categories. Mem Cognit 19(5), 423\u2013438 (1991). https:\/\/doi.org\/10.3758\/BF03199563","journal-title":"Mem Cognit"},{"key":"216_CR21","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1016\/0010-0285(91)90016-H","volume":"23","author":"JW Tanaka","year":"1991","unstructured":"Tanaka, J.W., Taylor, M.: Object categories and expertise: is the basic-level in the eye of the beholder? Cogn. Psychol. 23, 457\u2013482 (1991). https:\/\/doi.org\/10.1016\/0010-0285(91)90016-H","journal-title":"Cogn. Psychol."},{"issue":"2","key":"216_CR22","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1037\/0096-3445.113.2.169","volume":"113","author":"B Tversky","year":"1984","unstructured":"Tversky, B., Hemenway, K.: Objects, parts, and categories. J. Exp. Psychol. Gen. 113(2), 169\u2013193 (1984). https:\/\/doi.org\/10.1037\/0096-3445.113.2.169","journal-title":"J. Exp. Psychol. Gen."},{"key":"216_CR23","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1016\/j.procs.2020.06.032","volume":"173","author":"S Singh","year":"2020","unstructured":"Singh, S., Srivastava, S.: Review of clustering techniques in control system. Procedia Comput. Sci. 173, 272\u2013280 (2020). https:\/\/doi.org\/10.1016\/j.procs.2020.06.032","journal-title":"Procedia Comput. Sci."},{"unstructured":"Lakoff, G.: Women, Fire, and Dangerous Things: What Categories Reveal about the Mind. University of Chicago Press, Chicago (1987). https:\/\/books.google.pl\/books?id=s4eqhnb2VugC","key":"216_CR24"},{"doi-asserted-by":"crossref","unstructured":"Everitt, B., Landau, S., Leese, M., Stahl, D.: Cluster Analysis. Wiley Series in Probability and Statistics. Wiley (2011). https:\/\/books.google.pl\/books?id=w3bE1kqd-48C","key":"216_CR25","DOI":"10.1002\/9780470977811"},{"issue":"1","key":"216_CR26","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s00357-008-9004-x","volume":"25","author":"A Fern\u00e1ndez","year":"2008","unstructured":"Fern\u00e1ndez, A., G\u00f3mez, S.: Solving non-uniqueness in agglomerative hierarchical clustering using multidendrograms. J. Classif. 25(1), 43\u201365 (2008). https:\/\/doi.org\/10.1007\/s00357-008-9004-x","journal-title":"J. Classif."}],"container-title":["New Generation Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00354-023-00216-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00354-023-00216-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00354-023-00216-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,18]],"date-time":"2024-10-18T22:40:16Z","timestamp":1729291216000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00354-023-00216-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,20]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["216"],"URL":"https:\/\/doi.org\/10.1007\/s00354-023-00216-3","relation":{},"ISSN":["0288-3635","1882-7055"],"issn-type":[{"type":"print","value":"0288-3635"},{"type":"electronic","value":"1882-7055"}],"subject":[],"published":{"date-parts":[[2023,4,20]]},"assertion":[{"value":"31 August 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 March 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 April 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author declares that he has no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}