{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:32:13Z","timestamp":1740133933213,"version":"3.37.3"},"reference-count":22,"publisher":"World Scientific Pub Co Pte Ltd","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2019,4]]},"abstract":"<jats:p> We prove that one can construct various kinds of automata over finite words for which some elementary properties are actually independent from strong set theories like [Formula: see text] [Formula: see text] \u201cThere exist (at least) [Formula: see text] inaccessible cardinals\u201d, for integers [Formula: see text]. In particular, we prove independence results for languages of finite words generated by context-free grammars, or accepted by 2-tape or 1-counter automata. Moreover we get some independence results for weighted automata and for some related finitely generated subsemigroups of the set [Formula: see text] of 3-3 matrices with integer entries. Some of these latter results are independence results from the Peano axiomatic system PA. <\/jats:p>","DOI":"10.1142\/s012905411950014x","type":"journal-article","created":{"date-parts":[[2019,4,30]],"date-time":"2019-04-30T04:19:39Z","timestamp":1556597979000},"page":"449-467","source":"Crossref","is-referenced-by-count":0,"title":["Incompleteness Theorems, Large Cardinals, and Automata Over Finite Words"],"prefix":"10.1142","volume":"30","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6461-2941","authenticated-orcid":false,"given":"Olivier","family":"Finkel","sequence":"first","affiliation":[{"name":"Institut de Math\u00e9matiques de Jussieu \u2013 Paris Rive Gauche, CNRS et Universit\u00e9 Paris Diderot, UFR de Math\u00e9matiques case 7012, 75205 Paris Cedex 13, France"}]}],"member":"219","published-online":{"date-parts":[[2019,4,30]]},"reference":[{"key":"S012905411950014XBIB001","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-663-09367-1"},{"key":"S012905411950014XBIB002","doi-asserted-by":"publisher","DOI":"10.1007\/BF03024483"},{"key":"S012905411950014XBIB003","series-title":"Studies in Logic and the Foundations of Mathematics","doi-asserted-by":"crossref","DOI":"10.1016\/S0049-237X(08)71789-0","volume-title":"Set Theory. An Introduction to Large Cardinals","volume":"76","author":"Drake F. R.","year":"1974"},{"key":"S012905411950014XBIB004","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2355-7"},{"key":"S012905411950014XBIB005","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2003013"},{"issue":"4","key":"S012905411950014XBIB006","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2168\/LMCS-5(4:4)2009","volume":"5","author":"Finkel O.","year":"2009","journal-title":"Logical Methods in Computer Science"},{"key":"S012905411950014XBIB007","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/2011113"},{"key":"S012905411950014XBIB010","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511974236.021"},{"key":"S012905411950014XBIB011","doi-asserted-by":"publisher","DOI":"10.1007\/BF01565428"},{"volume-title":"On Formally Undecidable Propositions of Principia Mathematica and Related Systems.","year":"1963","author":"G\u00f6del K.","key":"S012905411950014XBIB012"},{"key":"S012905411950014XBIB013","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.2001.11919796"},{"key":"S012905411950014XBIB015","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90026-2"},{"key":"S012905411950014XBIB016","series-title":"Addison-Wesley Series in Computer Science","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft J. E.","year":"2001"},{"key":"S012905411950014XBIB017","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-02171-3"},{"key":"S012905411950014XBIB018","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744294"},{"volume-title":"Set Theory","year":"2002","author":"Jech T.","key":"S012905411950014XBIB019"},{"key":"S012905411950014XBIB020","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90013-1"},{"key":"S012905411950014XBIB021","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-13167-1"},{"key":"S012905411950014XBIB022","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(87)90074-1"},{"key":"S012905411950014XBIB023","series-title":"Studies in Logic and the Foundations of Mathematics","volume-title":"Set Theory","volume":"102","author":"Kunen K.","year":"1980"},{"key":"S012905411950014XBIB024","doi-asserted-by":"publisher","DOI":"10.3406\/intel.2009.1734"},{"key":"S012905411950014XBIB025","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8622-1"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012905411950014X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T15:50:08Z","timestamp":1565106608000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S012905411950014X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4]]},"references-count":22,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2019,4,30]]},"published-print":{"date-parts":[[2019,4]]}},"alternative-id":["10.1142\/S012905411950014X"],"URL":"https:\/\/doi.org\/10.1142\/s012905411950014x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2019,4]]}}}