{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,2]],"date-time":"2024-07-02T11:37:48Z","timestamp":1719920268959},"reference-count":36,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2023,9,1]],"date-time":"2023-09-01T00:00:00Z","timestamp":1693526400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2023,9,1]],"date-time":"2023-09-01T00:00:00Z","timestamp":1693526400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2023,9,1]],"date-time":"2023-09-01T00:00:00Z","timestamp":1693526400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2023,9,1]],"date-time":"2023-09-01T00:00:00Z","timestamp":1693526400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2023,9,1]],"date-time":"2023-09-01T00:00:00Z","timestamp":1693526400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2023,9,1]],"date-time":"2023-09-01T00:00:00Z","timestamp":1693526400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"funder":[{"DOI":"10.13039\/501100001352","name":"National University of Singapore","doi-asserted-by":"publisher","award":["C252-000-087-001"],"id":[{"id":"10.13039\/501100001352","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","award":["MOE2019-T2-2-121 \/ R146-000-304-112"],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[2023,9]]},"DOI":"10.1016\/j.jcss.2023.04.003","type":"journal-article","created":{"date-parts":[[2023,4,12]],"date-time":"2023-04-12T15:05:56Z","timestamp":1681311956000},"page":"135-156","update-policy":"http:\/\/dx.doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":2,"special_numbering":"C","title":["Addition machines, automatic functions and open problems of Floyd and Knuth"],"prefix":"10.1016","volume":"136","author":[{"given":"Sanjay","family":"Jain","sequence":"first","affiliation":[]},{"given":"Xiaodong","family":"Jia","sequence":"additional","affiliation":[]},{"given":"Ammar Fathin","family":"Sabili","sequence":"additional","affiliation":[]},{"given":"Frank","family":"Stephan","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.jcss.2023.04.003_br0010","series-title":"Forty-Ninth Annual IEEE Symposium on Foundations of Computer Science","first-page":"67","article-title":"Arithmetic circuits: a chasm at depth four","author":"Agrawal","year":"2008"},{"issue":"4","key":"10.1016\/j.jcss.2023.04.003_br0020","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1145\/792538.792540","article-title":"Primality and identity testing via Chinese Remaindering","volume":"50","author":"Agrawal","year":"2003","journal-title":"J. ACM"},{"issue":"3","key":"10.1016\/j.jcss.2023.04.003_br0030","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1007\/BF02366518","article-title":"Fibonacci linear forms and parallel arithmetic algorithms for large numbers","volume":"31","author":"Anisimov","year":"1995","journal-title":"Cybern. Syst. Anal."},{"issue":"4","key":"10.1016\/j.jcss.2023.04.003_br0040","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1007\/BF02835848","article-title":"Fast direct computation of modular reduction","volume":"35","author":"Anisimov","year":"1999","journal-title":"Cybern. Syst. Anal."},{"issue":"5","key":"10.1016\/j.jcss.2023.04.003_br0050","doi-asserted-by":"crossref","first-page":"659","DOI":"10.1007\/s10559-017-9967-x","article-title":"Trusted computing with addition machines I","volume":"53","author":"Anisimov","year":"2017","journal-title":"Cybern. Syst. Anal."},{"issue":"1","key":"10.1016\/j.jcss.2023.04.003_br0060","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10559-018-0002-7","article-title":"Trusted computing with addition machines II","volume":"54","author":"Anisimov","year":"2018","journal-title":"Cybern. Syst. Anal."},{"key":"10.1016\/j.jcss.2023.04.003_br0070","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1007\/s00224-004-1133-y","article-title":"Finite presentations of infinite structures: automata and interpretations","volume":"37","author":"Blumensath","year":"2004","journal-title":"Theory Comput. Syst."},{"key":"10.1016\/j.jcss.2023.04.003_br0080","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1002\/malq.19600060105","article-title":"Weak second-order arithmetic and finite automata","volume":"6","author":"B\u00fcchi","year":"1960","journal-title":"Z. Math. Log. Grundl. Math."},{"key":"10.1016\/j.jcss.2023.04.003_br0090","first-page":"1","article-title":"On a decision method in restricted second order arithmetic","volume":"vol. 44","author":"B\u00fcchi","year":"1966"},{"issue":"3","key":"10.1016\/j.jcss.2023.04.003_br0100","article-title":"Automatic functions, linear time and learning","volume":"9","author":"Case","year":"2013","journal-title":"Log. Methods Comput. Sci."},{"issue":"2","key":"10.1016\/j.jcss.2023.04.003_br0110","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1007\/BF01746527","article-title":"On the base-dependence of sets of numbers, recognizable by finite automata","volume":"3","author":"Cobham","year":"1969","journal-title":"Math. Syst. Theory"},{"key":"10.1016\/j.jcss.2023.04.003_br0120","series-title":"Introduction to Algorithms","author":"Cormen","year":"2009"},{"issue":"2","key":"10.1016\/j.jcss.2023.04.003_br0130","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1137\/0219022","article-title":"Addition machines","volume":"19","author":"Floyd","year":"1990","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.jcss.2023.04.003_br0140","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1016\/j.tcs.2022.04.038","article-title":"A computation model with automatic functions as primitive operations","volume":"924","author":"Gao","year":"2022","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.jcss.2023.04.003_br0150","series-title":"LICS 2020: Thirty-Fifth Annual ACM\/IEEE Symposium on Logic in Computer Science","first-page":"21","article-title":"Automatic structures: twenty years later","author":"Gr\u00e4del","year":"2020"},{"issue":"2","key":"10.1016\/j.jcss.2023.04.003_br0160","doi-asserted-by":"crossref","first-page":"563","DOI":"10.4007\/annals.2021.193.2.4","article-title":"Integer multiplication in time O(nlog\u2061n)","volume":"193","author":"Harvey","year":"2021","journal-title":"Ann. Math."},{"key":"10.1016\/j.jcss.2023.04.003_br0170","series-title":"On Asymptotic Notation with Multiple Variables","author":"Howell","year":"2008"},{"key":"10.1016\/j.jcss.2023.04.003_br0180","series-title":"Algorithms: a top-down approach","author":"Howell","year":"2012"},{"key":"10.1016\/j.jcss.2023.04.003_br0190","series-title":"Th\u00e9ories d\u00e9cidables par automate fini","author":"Hodgson","year":"1976"},{"issue":"1","key":"10.1016\/j.jcss.2023.04.003_br0200","first-page":"39","article-title":"D\u00e9cidabilit\u00e9 par automate fini","volume":"7","author":"Hodgson","year":"1983","journal-title":"Ann. Sci. Math. Qu\u00e9."},{"issue":"4","key":"10.1016\/j.jcss.2023.04.003_br0210","doi-asserted-by":"crossref","first-page":"1254","DOI":"10.1007\/s00224-017-9792-7","article-title":"Semiautomatic structures","volume":"61","author":"Jain","year":"2017","journal-title":"Theory Comput. Syst."},{"key":"10.1016\/j.jcss.2023.04.003_br0220","series-title":"Proceedings of Logic Colloquium 2007","first-page":"132","article-title":"Three lectures on automatic structures","volume":"vol. 35","author":"Khoussainov","year":"2010"},{"key":"10.1016\/j.jcss.2023.04.003_br0230","series-title":"Logic and Computational Complexity, International Workshop","first-page":"367","article-title":"Automatic presentations of structures","volume":"vol. 960","author":"Khoussainov","year":"1995"},{"issue":"2","key":"10.1016\/j.jcss.2023.04.003_br0240","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1109\/MAHC.2004.1299661","article-title":"Robert W Floyd, in Memoriam","volume":"26","author":"Knuth","year":"2004","journal-title":"IEEE Ann. Hist. Comput."},{"key":"10.1016\/j.jcss.2023.04.003_br0250","series-title":"Register Machines","author":"Jia","year":"2020"},{"key":"10.1016\/j.jcss.2023.04.003_br0260","series-title":"Fifteenth Annual Symposium on Switching and Automata Theory","first-page":"13","article-title":"On the power of multiplication in random access machines","author":"Hartmanis","year":"1974"},{"issue":"2\u20133","key":"10.1016\/j.jcss.2023.04.003_br0270","first-page":"26","article-title":"Performance analysis of arithmetic algorithms implemented in C++ and Python programming languages","author":"Novokshonov","year":"2018","journal-title":"Probl. Program."},{"issue":"5","key":"10.1016\/j.jcss.2023.04.003_br0280","doi-asserted-by":"crossref","first-page":"825","DOI":"10.1147\/rd.255.0825","article-title":"Algebraic complexity theory","volume":"25","author":"Pippenger","year":"1981","journal-title":"IBM J. Res. Dev."},{"key":"10.1016\/j.jcss.2023.04.003_br0290","doi-asserted-by":"crossref","first-page":"169","DOI":"10.2178\/bsl\/1208442827","article-title":"Automata presenting structures: a survey of the finite string case","volume":"14","author":"Rubin","year":"2008","journal-title":"Bull. Symb. Log."},{"key":"10.1016\/j.jcss.2023.04.003_br0300","series-title":"Turing machines and automatic functions as models of computation","author":"Seah","year":"2012"},{"key":"10.1016\/j.jcss.2023.04.003_br0310","series-title":"Automata, Languages and Programming, Sixth Colloquium","first-page":"520","article-title":"On the power of random access machines","volume":"vol. 71","author":"Sch\u00f6nhage","year":"1979"},{"issue":"2","key":"10.1016\/j.jcss.2023.04.003_br0320","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1007\/BF00967164","article-title":"Presburgerness of predicates regular in two number systems","volume":"18","author":"Semenov","year":"1977","journal-title":"Sib. Math. J."},{"key":"10.1016\/j.jcss.2023.04.003_br0330","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1016\/0022-0000(81)90041-6","article-title":"Division in idealised unit cost RAMs","volume":"22","author":"Simon","year":"1981","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/j.jcss.2023.04.003_br0340","series-title":"Arithmetic versus Boolean operations in idealized register machines","author":"Stockmeyer","year":"1976"},{"issue":"01\u201302","key":"10.1016\/j.jcss.2023.04.003_br0350","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1142\/S0129626494000132","article-title":"Parallel random access machines without Boolean operations","volume":"4","author":"Trahan","year":"1994","journal-title":"Parallel Process. Lett."},{"key":"10.1016\/j.jcss.2023.04.003_br0360","first-page":"179","article-title":"Repr\u00e9sentation des nombres naturels par une somme des nombres de Fibonacii ou de nombres de Lucas","volume":"41","author":"Zeckendorf","year":"1972","journal-title":"Bull. Soc. R. Sci. Li\u00e8ge"}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000023000387?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000023000387?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T01:55:15Z","timestamp":1683942915000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000023000387"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9]]},"references-count":36,"alternative-id":["S0022000023000387"],"URL":"https:\/\/doi.org\/10.1016\/j.jcss.2023.04.003","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[2023,9]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Addition machines, automatic functions and open problems of Floyd and Knuth","name":"articletitle","label":"Article Title"},{"value":"Journal of Computer and System Sciences","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.jcss.2023.04.003","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2023 Elsevier Inc. All rights reserved.","name":"copyright","label":"Copyright"}]}}