{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:25:31Z","timestamp":1740108331769,"version":"3.37.3"},"reference-count":56,"publisher":"Springer Science and Business Media LLC","issue":"2-3","license":[{"start":{"date-parts":[[2021,7,25]],"date-time":"2021-07-25T00:00:00Z","timestamp":1627171200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,7,25]],"date-time":"2021-07-25T00:00:00Z","timestamp":1627171200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2022,6]]},"DOI":"10.1007\/s00236-021-00407-9","type":"journal-article","created":{"date-parts":[[2021,7,25]],"date-time":"2021-07-25T04:02:31Z","timestamp":1627185751000},"page":"245-281","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Regular numeral systems for data structures"],"prefix":"10.1007","volume":"59","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6549-908X","authenticated-orcid":false,"given":"Amr","family":"Elmasry","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jyrki","family":"Katajainen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,7,25]]},"reference":[{"key":"407_CR1","volume-title":"Compilers: Principles, Techniques, & Tools","author":"AV Aho","year":"2007","unstructured":"Aho, A.V., Lam, M.S., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques, & Tools, 2nd edn. Pearson Education Inc, London (2007)","edition":"2"},{"doi-asserted-by":"crossref","unstructured":"Avizienis, A.: Signed-digit numbe[r] representations for fast parallel arithmetic. IRE Trans. Electron. Comput EC\u201310(3), 389\u2013400 (1961)","key":"407_CR2","DOI":"10.1109\/TEC.1961.5219227"},{"issue":"9","key":"407_CR3","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1145\/360336.360343","volume":"19","author":"JR Bitner","year":"1976","unstructured":"Bitner, J.R., Ehrlich, G., Reingold, E.M.: Efficient generation of the binary reflected Gray code and its applications. Commun. ACM 19(9), 517\u2013521 (1976)","journal-title":"Commun. ACM"},{"issue":"12","key":"407_CR4","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/355588.355589","volume":"7","author":"J Boothroyd","year":"1964","unstructured":"Boothroyd, J.: Algorithm 246: Graycode. Commun. ACM 7(12), 701 (1964)","journal-title":"Commun. ACM"},{"doi-asserted-by":"crossref","unstructured":"Bose, P., Carmi, P., Jansens, D., Maheshwari, A., Morin, P,, Smid, M.: Improved methods for generating quasi-Gray codes. In: 12th Scandinavian Symposium and Workshops on Algorithm Theory, Volume 6139 of Lecture Notes in Computer Science, pp. 224\u2013235. Springer (2010)","key":"407_CR5","DOI":"10.1007\/978-3-642-13731-0_22"},{"doi-asserted-by":"crossref","unstructured":"Brodal, G.: Fast meldable priority queues. In: 4th International Workshop on Algorithms and Data Structures, volume 955 of Lecture Notes in Computer Science, pp. 282\u2013290. Springer (1995)","key":"407_CR6","DOI":"10.1007\/3-540-60220-8_70"},{"unstructured":"Brodal, G.: Worst-case efficient priority queues. In: 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 52\u201358. SIAM (1996)","key":"407_CR7"},{"doi-asserted-by":"crossref","unstructured":"Brodal, G., Greve, M., Pandey, V., Rao, S.S.: Integer representations towards efficient counting in the bit probe model. In: 8th Annual Conference on Theory and Applications of Models of Computation, Volume 6648 of Lecture Notes in Computer Science, pp. 206\u2013217. Springer (2011)","key":"407_CR8","DOI":"10.1007\/978-3-642-20877-5_22"},{"issue":"3","key":"407_CR9","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1137\/0207026","volume":"7","author":"MR Brown","year":"1978","unstructured":"Brown, M.R.: Implementation and analysis of binomial queue algorithms. SIAM J. Comput. 7(3), 298\u2013319 (1978)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Carlsson, S., Munro, J.I., Poblete, P.V.: An implicit binomial queue with constant insertion time. In: 1st Scandinavian Workshop on Algorithm Theory, Volume 318 of Lecture Notes in Computer Science, pp. 1\u201313. Springer (1988)","key":"407_CR10","DOI":"10.1007\/3-540-19487-8_1"},{"unstructured":"Clancy, M.J., Knuth, D.E.: A programming and problem-solving seminar. Technical report STAN-CS-77-606, Computer Science Department, Stanford University (1977)","key":"407_CR11"},{"unstructured":"Collignon, E.: Note sur l\u2019arithm\u00e9tique binaire. Journal de Math\u00e9matiques \u00c9l\u00e9mentaires, 21, 101\u2013106, 126\u2013131, 148\u2013151, 171\u2013174 (1897)","key":"407_CR12"},{"key":"407_CR13","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press, Cambridge (2009)","edition":"3"},{"issue":"11","key":"407_CR14","doi-asserted-by":"publisher","first-page":"1343","DOI":"10.1145\/50087.50096","volume":"31","author":"JR Driscoll","year":"1988","unstructured":"Driscoll, J.R., Gabow, H.N., Shrairman, R., Tarjan, R.E.: Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation. Commun. ACM 31(11), 1343\u20131354 (1988)","journal-title":"Commun. ACM"},{"issue":"3","key":"407_CR15","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1007\/BF01990520","volume":"33","author":"D Ronald","year":"1993","unstructured":"Ronald, D.: Dutton. Weak-heap sort. BIT 33(3), 372\u2013381 (1993)","journal-title":"BIT"},{"key":"407_CR16","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/j.jda.2012.04.010","volume":"16","author":"S Edelkamp","year":"2012","unstructured":"Edelkamp, S., Elmasry, A., Katajainen, J.: The weak-heap data structure: variants and applications. J. Discrete Algorithms 16, 187\u2013205 (2012)","journal-title":"J. Discrete Algorithms"},{"unstructured":"Edelkamp, S., Elmasry, A., Katajainen, J.: The weak-heap family of priority queues in theory and praxis. In: 18th Computing: The Australasian Theory Symposium, Volume 128 of Conferences in Research and Practice in Information Technology, pp. 103\u2013112. Australian Computer Society, Inc. (2012)","key":"407_CR17"},{"issue":"6","key":"407_CR18","doi-asserted-by":"publisher","first-page":"1455","DOI":"10.1142\/S0129054106004510","volume":"17","author":"A Elmasry","year":"2006","unstructured":"Elmasry, A.: A priority queue with the working-set property. Int. J. Found. Comput. Sci. 17(6), 1455\u20131465 (2006)","journal-title":"Int. J. Found. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Elmasry, A., Jensen, C., Katajainen, J.: Multipartite priority queues. ACM Trans. Algorithms, 5(1):Acticle 14 (2008)","key":"407_CR19","DOI":"10.1145\/1435375.1435389"},{"issue":"4","key":"407_CR20","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s00607-008-0019-2","volume":"83","author":"A Elmasry","year":"2008","unstructured":"Elmasry, A., Jensen, C., Katajainen, J.: Two new methods for constructing double-ended priority queues from priority queues. Computing 83(4), 193\u2013204 (2008)","journal-title":"Computing"},{"issue":"3","key":"407_CR21","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s00236-008-0070-7","volume":"45","author":"A Elmasry","year":"2008","unstructured":"Elmasry, A., Jensen, C., Katajainen, J.: Two-tier relaxed heaps. Acta Inform. 45(3), 193\u2013210 (2008)","journal-title":"Acta Inform."},{"doi-asserted-by":"crossref","unstructured":"Elmasry, A., Jensen, C., Katajainen, J.: The magic of a number system. In: 5th International Conference on Fun with Algorithms, Volume 6099 of Lecture Notes in Computer Science, pp. 156\u2013165. Springer (2010)","key":"407_CR22","DOI":"10.1007\/978-3-642-13122-6_17"},{"doi-asserted-by":"crossref","unstructured":"Elmasry, A., Jensen, C., Katajainen, J.: Strictly-regular number system and data structures. In: 12th Scandinavian Symposium and Workshops on Algorithm Theory, Volume 6139 of Lecture Notes in Computer Science, pp. 26\u201337. Springer (2010)","key":"407_CR23","DOI":"10.1007\/978-3-642-13731-0_4"},{"issue":"1","key":"407_CR24","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/s00224-011-9357-0","volume":"50","author":"A Elmasry","year":"2012","unstructured":"Elmasry, A., Jensen, C., Katajainen, J.: Two skew-binary numeral systems and one application. Theory Comput. Syst. 50(1), 185\u2013211 (2012)","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"407_CR25","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1051\/ita\/2017010","volume":"51","author":"A Elmasry","year":"2017","unstructured":"Elmasry, A., Jensen, C., Katajainen, J.: Bipartite binomial heaps. RAIRO Theor. Inform. Appl. 51(3), 121\u2013133 (2017)","journal-title":"RAIRO Theor. Inform. Appl."},{"issue":"5","key":"407_CR26","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/s00236-019-00335-9","volume":"56","author":"A Elmasry","year":"2019","unstructured":"Elmasry, A., Kahla, M., Ahdy, F., Hashem, M.: Red-black trees with constant update time. Acta Inform. 56(5), 391\u2013404 (2019)","journal-title":"Acta Inform."},{"doi-asserted-by":"crossref","unstructured":"Elmasry, A., Katajainen, J.: Worst-case optimal priority queues via extended regular counters. In: 7th International Computer Science Symposium in Russia, Volume 7353 of Lecture Notes in Computer Science, pp. 130\u2013142. Springer (2012)","key":"407_CR27","DOI":"10.1007\/978-3-642-30642-6_13"},{"doi-asserted-by":"crossref","unstructured":"Elmasry, A., Katajainen, J.: Fat heaps without regular counters. Discrete Math. Algorithms Appl., 5(2) (2013)","key":"407_CR28","DOI":"10.1142\/S1793830913600069"},{"doi-asserted-by":"crossref","unstructured":"Elmasry, A., Katajainen, J.: In-place binary counters. In: 38th International Symposium on Mathematical Foundations of Computer Science, Volume 8087 of Lecture Notes in Computer Science, pp. 349\u2013360. Springer (2013)","key":"407_CR29","DOI":"10.1007\/978-3-642-40313-2_32"},{"unstructured":"Glaser, A.: History of Binary and Other Nondecimal Numeration. Tomash Publishers, revised edition (1981)","key":"407_CR30"},{"unstructured":"Gray, F.: Pulse code communications. U.S. Patent 2632058 (1953)","key":"407_CR31"},{"doi-asserted-by":"crossref","unstructured":"Guibas, L.J., McCreight, E.M., Plass, M.F., Roberts, J.R.: A new representation for linear lists. In: 9th Annual ACM Symposium on Theory of Computing, pp. 49\u201360. ACM (1977)","key":"407_CR32","DOI":"10.1145\/800105.803395"},{"doi-asserted-by":"crossref","unstructured":"Guibas, L.J., Sedgewick, R.: A dichromatic framework for balanced trees. In: 19th Annual Symposium on Foundations of Computer Science, pp. 8\u201321. IEEE (1978)","key":"407_CR33","DOI":"10.1109\/SFCS.1978.3"},{"doi-asserted-by":"crossref","unstructured":"Hagerup, T.: Sorting and searching on the word RAM. In: 15th Annual Symposium on Theoretical Aspects of Computer Science, Volume 1373 of Lecture Notes in Computer Science, pp. 366\u2013398. Springer (1998)","key":"407_CR34","DOI":"10.1007\/BFb0028575"},{"issue":"2","key":"407_CR35","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1016\/0020-0190(81)90030-2","volume":"13","author":"R Hood","year":"1981","unstructured":"Hood, R., Melville, R.: Real-time queue operations in Pure LISP. Inf. Process. Lett. 13(2), 50\u201354 (1981)","journal-title":"Inf. Process. Lett."},{"doi-asserted-by":"crossref","unstructured":"Kaplan, H., Shafrir, N., Tarjan, R.E.: Meldable heaps and Boolean union-find. In: 34th Annual ACM Symposium on Theory of Computing, pp. 573\u2013582. ACM (2002)","key":"407_CR36","DOI":"10.1145\/509907.509990"},{"doi-asserted-by":"crossref","unstructured":"Kaplan, H., Tarjan, R.E.: Purely functional representations of catenable sorted lists. In:28th Annual ACM Symposium on Theory of Computing, pp. 202\u2013211. ACM (1996)","key":"407_CR37","DOI":"10.1145\/237814.237865"},{"unstructured":"Kaplan, H., Tarjan, R.E.: New heap data structures. Technical Report TR-597-99, Department of Computer Science, Princeton University (1999)","key":"407_CR38"},{"issue":"5","key":"407_CR39","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1145\/324133.324139","volume":"46","author":"H Kaplan","year":"1999","unstructured":"Kaplan, H., Tarjan, R.E.: Purely functional, real-time deques with catenation. J. ACM 46(5), 577\u2013603 (1999)","journal-title":"J. ACM"},{"doi-asserted-by":"crossref","unstructured":"Katajainen, J.: Worst-case-efficient dynamic arrays in practice. In: 15th International Symposium on Experimental Algorithms, Volume 9685 of Lecture Notes in Computer Science, pp. 167\u2013183. Springer (2016)","key":"407_CR40","DOI":"10.1007\/978-3-319-38851-9_12"},{"doi-asserted-by":"crossref","unstructured":"Katajainen, J.M., Bjarke, B.: Experiences with the design and implementation of space-efficient deques. In: 5th International Workshop on Algorithm Engineering, Volume 2141 of Lecture Notes in Computer Science, pp. 39\u201350. Springer (2001)","key":"407_CR41","DOI":"10.1007\/3-540-44688-5_4"},{"key":"407_CR42","volume-title":"The C Programming Language","author":"BW Kernighan","year":"1988","unstructured":"Kernighan, B.W., Ritchie, D.M.: The C Programming Language, 2nd edn. Prentice Hall PTR, Hoboken (1988)","edition":"2"},{"key":"407_CR43","volume-title":"Sorting and Searching, Volume 3 of The Art of Computer Programming","author":"DE Knuth","year":"1998","unstructured":"Knuth, D.E.: Sorting and Searching, Volume 3 of The Art of Computer Programming, 2nd edn. Addison Wesley, Longman (1998)","edition":"2"},{"key":"407_CR44","volume-title":"Combinatorial Algorithms: Part 1, Volume 4A of The Art of Computer Programming","author":"DE Knuth","year":"2011","unstructured":"Knuth, D.E.: Combinatorial Algorithms: Part 1, Volume 4A of The Art of Computer Programming. Addison-Wesley, Longman (2011)"},{"key":"407_CR45","volume-title":"Computer Arithmetic Algorithms","author":"I Koren","year":"2002","unstructured":"Koren, I.: Computer Arithmetic Algorithms, 2nd edn. A. K. Peters, Ltd, Natick (2002)","edition":"2"},{"unstructured":"Mehta, H., Owens, R.M., Irwin, M.J.: Some issues in Gray code addressing. In: 6th Great Lakes Symposium on VLSI, pp. 178\u2013181. IEEE Computer Society (1996)","key":"407_CR46"},{"unstructured":"Metze, G., Robertson, J.E.: Elimination of carry propagation in digital computers. In: International Conference on Information Processing, pp. 389\u2013396. UNESCO (1960)","key":"407_CR47"},{"issue":"5","key":"407_CR48","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/0020-0190(83)90106-0","volume":"17","author":"EW Myers","year":"1983","unstructured":"Myers, E.W.: An applicative random-access stack. Inf. Process. Lett. 17(5), 241\u2013248 (1983)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"407_CR49","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1017\/S0956796800001489","volume":"5","author":"C Okasaki","year":"1995","unstructured":"Okasaki, C.: Simple and efficient purely functional queues and deques. J. Funct. Program. 5(4), 583\u2013592 (1995)","journal-title":"J. Funct. Program."},{"key":"407_CR50","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511530104","volume-title":"Purely Functional Data Structures","author":"C Okasaki","year":"1998","unstructured":"Okasaki, C.: Purely Functional Data Structures. Cambridge University Press, Cambridge (1998)"},{"issue":"5","key":"407_CR51","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1017\/S0956796897002852","volume":"7","author":"ME O\u2019Neill","year":"1997","unstructured":"O\u2019Neill, M.E., Burton, F.W.: A new method for functional arrays. J. Funct. Program. 7(5), 487\u2013513 (1997)","journal-title":"J. Funct. Program."},{"issue":"1","key":"407_CR52","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1109\/12.46283","volume":"39","author":"B Parhami","year":"1990","unstructured":"Parhami, B.: Generalized signed-digit number systems: a unifying framework for redundant number representations. IEEE Trans. Comput. 39(1), 89\u201398 (1990)","journal-title":"IEEE Trans. Comput."},{"key":"407_CR53","volume-title":"Computer Arithmetic: Algorithms and Hardware Designs","author":"B Parhami","year":"2009","unstructured":"Parhami, B.: Computer Arithmetic: Algorithms and Hardware Designs, 2nd edn. Oxford University Press, Oxford (2009)","edition":"2"},{"issue":"1","key":"407_CR54","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/s00453-008-9247-2","volume":"56","author":"MZ Rahman","year":"2010","unstructured":"Rahman, M.Z., Munro, J.I.: Integer representation and counting in the bit probe model. Algorithmica 56(1), 105\u2013127 (2010)","journal-title":"Algorithmica"},{"issue":"4","key":"407_CR55","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1145\/359460.359478","volume":"21","author":"J Vuillemin","year":"1978","unstructured":"Vuillemin, J.: A data structure for manipulating priority queues. Commun. ACM 21(4), 309\u2013315 (1978)","journal-title":"Commun. ACM"},{"issue":"6","key":"407_CR56","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1145\/512274.512284","volume":"7","author":"JWJ Williams","year":"1964","unstructured":"Williams, J.W.J.: Algorithm 232: heapsort. Commun. ACM 7(6), 347\u2013348 (1964)","journal-title":"Commun. ACM"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-021-00407-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-021-00407-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-021-00407-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,14]],"date-time":"2022-05-14T09:09:48Z","timestamp":1652519388000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-021-00407-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,25]]},"references-count":56,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["407"],"URL":"https:\/\/doi.org\/10.1007\/s00236-021-00407-9","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"type":"print","value":"0001-5903"},{"type":"electronic","value":"1432-0525"}],"subject":[],"published":{"date-parts":[[2021,7,25]]},"assertion":[{"value":"14 June 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 July 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}