{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T21:57:46Z","timestamp":1747173466816,"version":"3.40.5"},"reference-count":34,"publisher":"Cambridge University Press (CUP)","license":[{"start":{"date-parts":[[2023,6,8]],"date-time":"2023-06-08T00:00:00Z","timestamp":1686182400000},"content-version":"unspecified","delay-in-days":158,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["J. Funct. Prog."],"published-print":{"date-parts":[[2023]]},"abstract":"<jats:title>Abstract<\/jats:title>\n\t  <jats:p>In the <jats:italic>cons-free<\/jats:italic> programming paradigm, we eschew constructors and program using only destructors. Cons-free programs in a simple first-order language with string data capture exactly P, the class of polynomial-time relations. By varying the underlying language and considering other data types, we can capture several other complexity classes. However, no cons-free programming language captures any <jats:italic>functional<\/jats:italic> complexity class for fundamental reasons. In this paper, we cleanly extend the cons-free paradigm to encompass functional complexity classes. Namely, we introduce programs with data that can either <jats:italic>only<\/jats:italic> be destructed or <jats:italic>only<\/jats:italic> be constructed, which we enforce by a type system on the program variables. We call the resulting programs <jats:italic>read\/write<\/jats:italic>- (or <jats:italic>RW<\/jats:italic>-)factorizable, show that RW-factorizable string programs capture exactly the class FP of polynomial-time functions, and that tail-recursive RW-factorizable programs capture exactly the class FL of logarithmic-space functions. Finally, we state and solve the nontrivial problem of <jats:italic>syntactic composition<\/jats:italic> of two RW-factorizable programs.<\/jats:p>","DOI":"10.1017\/s0956796823000023","type":"journal-article","created":{"date-parts":[[2023,6,8]],"date-time":"2023-06-08T04:10:45Z","timestamp":1686197445000},"update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Read\/write factorizable programs"],"prefix":"10.1017","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4157-8768","authenticated-orcid":false,"given":"SIDDHARTH","family":"BHASKAR","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3488-9392","authenticated-orcid":false,"given":"JAKOB GRUE","family":"SIMONSEN","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2023,6,8]]},"reference":[{"key":"S0956796823000023_ref14","doi-asserted-by":"publisher","DOI":"10.1145\/321707.321721"},{"key":"S0956796823000023_ref26","doi-asserted-by":"crossref","unstructured":"Kop, C. & Simonsen, J. G. (2017) The power of non-determinism in higher-order implicit complexity - characterising complexity classes using non-deterministic cons-free programming. In Programming Languages and Systems - 26th European Symposium on Programming, ESOP 2017, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Uppsala, Sweden, April 22\u201329, 2017, Proceedings, Yang, H. (ed). Lecture Notes in Computer Science, vol. 10201. Springer, pp. 668\u2013695.","DOI":"10.1007\/978-3-662-54434-1_25"},{"year":"1998","author":"Ben-Amram","key":"S0956796823000023_ref9"},{"key":"S0956796823000023_ref27","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804358"},{"key":"S0956796823000023_ref18","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1998.2700"},{"key":"S0956796823000023_ref25","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.320.5"},{"key":"S0956796823000023_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08918-8_13"},{"key":"S0956796823000023_ref29","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2003.10.018"},{"key":"S0956796823000023_ref34","doi-asserted-by":"publisher","DOI":"10.1017\/9781108234238"},{"key":"S0956796823000023_ref32","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-2566-9_11"},{"key":"S0956796823000023_ref2","unstructured":"Aubert, C. , Seiller, T. , Rubiano, T. & Rusch, N. (2022) mwp-Analysis Improvement and Implementation: Realizing Implicit Computational Complexity. In 7th International Conference on Formal Structures for Computation and Deduction, FSCD 2022, August 2\u20135, 2022, Haifa, Israel, Felty, A. P. (ed). LIPIcs, vol. 228. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp. 26:1\u201326:23."},{"key":"S0956796823000023_ref16","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129521000505"},{"key":"S0956796823000023_ref3","unstructured":"Avanzini, M. , Eguchi, N. & Moser, G. (2011) A path order for rewrite systems that compute exponential time functions. In Proceedings of the 22nd International Conference on Rewriting Techniques and Applications, RTA 2011, May 30\u2013June 1, 2011, Novi Sad, Serbia, Schmidt-Schau\u00df, M. (ed). LIPIcs, vol. 10. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp. 123\u2013138."},{"key":"S0956796823000023_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/11784180_8"},{"key":"S0956796823000023_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00357-0"},{"key":"S0956796823000023_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-019-09530-2"},{"key":"S0956796823000023_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2015.12.007"},{"key":"S0956796823000023_ref8","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129740"},{"key":"S0956796823000023_ref19","volume-title":"Lecture Notes in Computer Science","volume":"36","author":"Greibach","year":"1975"},{"key":"S0956796823000023_ref24","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796800003889"},{"key":"S0956796823000023_ref33","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2011.41"},{"key":"S0956796823000023_ref22","doi-asserted-by":"publisher","DOI":"10.1145\/503272.503297"},{"key":"S0956796823000023_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.03.003"},{"key":"S0956796823000023_ref13","unstructured":"Cobham, A. (1965) The intrinsic computational difficulty of functions. In Logic, Methodology and Philosophy of Science: Proceedings of the 1964 International Congress (Studies in Logic and the Foundations of Mathematics), Bar-Hillel, Y. (ed). North-Holland Publishing, pp. 24\u201330."},{"key":"S0956796823000023_ref7","doi-asserted-by":"publisher","DOI":"10.1145\/3495529"},{"key":"S0956796823000023_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-022-10074-z"},{"key":"S0956796823000023_ref15","unstructured":"Czajka, L. (2018) Term rewriting characterisation of LOGSPACE for finite and infinite data. In 3rd International Conference on Formal Structures for Computation and Deduction, FSCD 2018, July 9\u201312, 2018, Oxford, UK, pp. 13:1\u201313:19."},{"key":"S0956796823000023_ref20","first-page":"1","article-title":"A tier-based typed programming language characterizing Feasible Functionals","volume":"18","author":"Hainry","year":"2022","journal-title":"Log. Methods Comput. Sci."},{"key":"S0956796823000023_ref28","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2021.102723"},{"key":"S0956796823000023_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/CBO9780511629181.011"},{"key":"S0956796823000023_ref21","doi-asserted-by":"publisher","DOI":"10.1145\/346048.346051"},{"key":"S0956796823000023_ref30","unstructured":"Lago, U. D. , Kahle, R. & Oitavem, I. (2021) A recursion-theoretic characterization of the probabilistic class PP. In 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, August 23\u201327, 2021, Tallinn, Estonia , Bonchi, F. & Puglisi, S. J. (eds). LIPIcs, vol. 202. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp. 35:1\u201335:12."},{"key":"S0956796823000023_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.02.007"},{"key":"S0956796823000023_ref31","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.10.009"}],"container-title":["Journal of Functional Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0956796823000023","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,8]],"date-time":"2023-06-08T04:11:01Z","timestamp":1686197461000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0956796823000023\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"references-count":34,"alternative-id":["S0956796823000023"],"URL":"https:\/\/doi.org\/10.1017\/s0956796823000023","relation":{},"ISSN":["0956-7968","1469-7653"],"issn-type":[{"type":"print","value":"0956-7968"},{"type":"electronic","value":"1469-7653"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"\u00a9 The Author(s), 2023. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}],"article-number":"e5"}}