{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:44:50Z","timestamp":1740123890952,"version":"3.37.3"},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,8,24]],"date-time":"2021-08-24T00:00:00Z","timestamp":1629763200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,8,24]],"date-time":"2021-08-24T00:00:00Z","timestamp":1629763200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000893","name":"simons foundation","doi-asserted-by":"publisher","award":["704836"],"award-info":[{"award-number":["704836"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[2022,1]]},"DOI":"10.1007\/s10472-021-09769-9","type":"journal-article","created":{"date-parts":[[2021,8,24]],"date-time":"2021-08-24T09:04:20Z","timestamp":1629795860000},"page":"93-105","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["VC-dimensions of nondeterministic finite automata for words of equal length"],"prefix":"10.1007","volume":"90","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6199-1755","authenticated-orcid":false,"given":"Bj\u00f8rn","family":"Kjos-Hanssen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Clyde James","family":"Felix","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sun Young","family":"Kim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ethan","family":"Lamb","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Davin","family":"Takahashi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,8,24]]},"reference":[{"key":"9769_CR1","unstructured":"Gruber, H., Holzer, M.: Results on the average state and transition complexity of finite automata accepting finite languages (extended abstract). In: Leung, H., Pighizzini, G. (eds.) 8th International Workshop on Descriptional Complexity of Formal Systems - DCFS 2006, Las Cruces, New Mexico, USA, June 21 - 23, 2006 Proceedings. New Mexico State University, Las Cruces, New Mexico, USA, pp 267\u2013275 (2006)"},{"issue":"2","key":"9769_CR2","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/j.tcs.2007.07.035","volume":"387","author":"H Gruber","year":"2007","unstructured":"Gruber, H., Holzer, M.: On the average state and transition complexity of finite languages. Theoret. Comput. Sci. 387(2), 155\u2013166 (2007)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"9769_CR3","doi-asserted-by":"publisher","first-page":"3.22, 18","DOI":"10.37236\/4851","volume":"22","author":"KK Hyde","year":"2015","unstructured":"Hyde, K.K., Kjos-Hanssen, B.: Nondeterministic automatic complexity of overlap-free and almost square-free words. Electron. J. Combin. 22(3), 3.22, 18 (2015)","journal-title":"Electron. J. Combin."},{"key":"9769_CR4","unstructured":"OEIS Foundation Inc: The on-line encyclopedia of integer sequences http:\/\/oeis.org\/A005187 (2021)"},{"key":"9769_CR5","doi-asserted-by":"crossref","unstructured":"Ishigami, Y., Sei\u2019ichi, T.: The VC-Dimensions of Finite Automata with N States. In: Algorithmic Learning Theory (Tokyo, 1993), volume 744 of Lecture Notes in Comput Sci, pp 328\u2013341. Springer, Berlin (1993)","DOI":"10.1007\/3-540-57370-4_58"},{"issue":"2","key":"9769_CR6","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0166-218X(96)00025-X","volume":"74","author":"Y Ishigami","year":"1997","unstructured":"Ishigami, Y., Tani, S.: VC-dimensions of finite automata and commutative finite automata with k letters and n states. Discrete Appl. Math. 74(2), 123\u2013134 (1997)","journal-title":"Discrete Appl. Math."},{"key":"9769_CR7","unstructured":"Kjos-Hanssen, B., Takahashi, D.K.: Code for VC-dimensions of finite automata for words of equal length https:\/\/github.com\/bjoernkjoshanssen\/vc (2019)"},{"key":"9769_CR8","doi-asserted-by":"crossref","unstructured":"Romanik, K.: Approximate testing and learnability. In: Proceedings of the Fifth Annual Workshop on Computational Learning Theory, COLT \u201992, pp 327\u2013332. Association for Computing Machinery, New York (1992)","DOI":"10.1145\/130385.130422"},{"issue":"1-2","key":"9769_CR9","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/S0304-3975(96)00241-1","volume":"188","author":"K Romanik","year":"1997","unstructured":"Romanik, K: Approximate testing and its relationship to learning. Theoret. Comput. Sci. 188(1-2), 79\u201399 (1997)","journal-title":"Theoret. Comput. Sci."},{"key":"9769_CR10","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0097-3165(72)90019-2","volume":"13","author":"N Sauer","year":"1972","unstructured":"Sauer, N.: On the density of families of sets. J. Combinatorial Theory Ser. A 13, 145\u2013147 (1972)","journal-title":"J. Combinatorial Theory Ser. A"},{"key":"9769_CR11","unstructured":"Shallit, J., Wang, M.-W.: Automatic complexity of strings. In: 2nd Workshop on Descriptional complexity of automata grammars and related structures (London ON 2000), vol. 6, pp 537\u2013554 (2001)"},{"key":"9769_CR12","doi-asserted-by":"publisher","first-page":"247","DOI":"10.2140\/pjm.1972.41.247","volume":"41","author":"S Shelah","year":"1972","unstructured":"Shelah, S.: A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific J. Math. 41, 247\u2013261 (1972)","journal-title":"Pacific J. Math."}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-021-09769-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10472-021-09769-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-021-09769-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,19]],"date-time":"2022-01-19T00:17:01Z","timestamp":1642551421000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10472-021-09769-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,24]]},"references-count":12,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["9769"],"URL":"https:\/\/doi.org\/10.1007\/s10472-021-09769-9","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"type":"print","value":"1012-2443"},{"type":"electronic","value":"1573-7470"}],"subject":[],"published":{"date-parts":[[2021,8,24]]},"assertion":[{"value":"4 August 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 August 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}