{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T09:45:33Z","timestamp":1764841533357},"reference-count":21,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2005,10]]},"abstract":"<jats:p> Language equations with all Boolean operations and concatenation and a particular order on the set of solutions are proved to be equal in expressive power to the first-order Peano arithmetic. In particular, it is shown that the class of sets representable using k variables (for every k \u2265 2) is exactly the k-th level of the arithmetical hierarchy, i.e., the sets definable by recursive predicates with k alternating quantifiers. The property of having an extremal solution is shown to be nonrepresentable in first-order arithmetic. <\/jats:p>","DOI":"10.1142\/s012905410500342x","type":"journal-article","created":{"date-parts":[[2005,10,13]],"date-time":"2005-10-13T11:41:41Z","timestamp":1129203701000},"page":"985-998","source":"Crossref","is-referenced-by-count":1,"title":["A CHARACTERIZATION OF THE ARITHMETICAL HIERARCHY BY LANGUAGE EQUATIONS"],"prefix":"10.1142","volume":"16","author":[{"given":"ALEXANDER","family":"OKHOTIN","sequence":"first","affiliation":[{"name":"School of Computing, Queen's University, Kingston, Ontario, Canada"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59136-5_3"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80027-9"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)72023-8"},{"key":"rf4","volume-title":"Regular Algebra and Finite Machines","author":"Conway J. H.","year":"1971"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1145\/321127.321132"},{"key":"rf7","first-page":"22","volume":"3","author":"Gruska J.","journal-title":"Kybernetika"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(69)90055-2"},{"key":"rf9","series-title":"Proceedings of Symposia in Applied Mathematics","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1090\/psapm\/019\/0235938","volume":"19","author":"Hartmanis J.","year":"1967"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(84)90015-X"},{"key":"rf12","volume-title":"Descriptive complexity","author":"Immerman N.","year":"1998"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.2307\/2695103"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-2156-2"},{"key":"rf15","first-page":"519","volume":"6","author":"Okhotin A.","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1023\/A:1020213411126"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2004004"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2004.03.006"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.03.002"},{"key":"rf22","volume-title":"Theory of Recursive Functions and Effective Computability","author":"Rogers H.","year":"1967"},{"key":"rf23","first-page":"1","volume":"14","author":"Rounds W. C.","journal-title":"Computational Linguistics"},{"key":"rf24","volume-title":"Theory of Automata","author":"Salomaa A.","year":"1969"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59136-5_2"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012905410500342X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:41:27Z","timestamp":1565138487000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S012905410500342X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,10]]},"references-count":21,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2005,10]]}},"alternative-id":["10.1142\/S012905410500342X"],"URL":"https:\/\/doi.org\/10.1142\/s012905410500342x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,10]]}}}