{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:10:40Z","timestamp":1760058640021,"version":"build-2065373602"},"reference-count":25,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2025,4,17]],"date-time":"2025-04-17T00:00:00Z","timestamp":1744848000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"King Abdullah University of Science and Technology (KAUST)"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Axioms"],"abstract":"<jats:p>This paper investigates classes of structures and individual structures where programs implementing functions defined everywhere (total programs) are equivalent to finite tree-programs. The programs considered may include cycles and contain at most countably many nodes. The analysis begins with programs where arbitrary terms of a given signature are used in function nodes, and arbitrary formulas of this signature are used in predicate nodes. The results are then extended to programs that closely resemble computation trees: if such a program is a finite tree-program, it can be classified as an ordinary computation tree.<\/jats:p>","DOI":"10.3390\/axioms14040307","type":"journal-article","created":{"date-parts":[[2025,4,17]],"date-time":"2025-04-17T06:53:46Z","timestamp":1744872826000},"page":"307","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["When Every Total Program Is a Finite Tree-Program: A Study of Program-Saturated Classes of Structures"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0085-9483","authenticated-orcid":false,"given":"Mikhail","family":"Moshkov","sequence":"first","affiliation":[{"name":"Computer, Electrical and Mathematical Sciences & Engineering Division, King Abdullah University of Science and Technology (KAUST), Thuwal 23955-6900, Saudi Arabia"}]}],"member":"1968","published-online":{"date-parts":[[2025,4,17]]},"reference":[{"key":"ref_1","unstructured":"Breiman, L., Friedman, J.H., Olshen, R.A., and Stone, C.J. (1984). Classification and Regression Trees, Chapman & Hall\/CRC."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1137\/0205015","article-title":"Multidimensional searching problems","volume":"5","author":"Dobkin","year":"1976","journal-title":"SIAM J. Comput."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1007\/11427834_12","article-title":"Time complexity of decision trees","volume":"Volume 3400","author":"Peters","year":"2005","journal-title":"Transactions on Rough Sets III, Lecture Notes in Computer Science"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1006\/jcss.1997.1495","article-title":"Decision tree complexity and Betti numbers","volume":"55","author":"Yao","year":"1997","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_5","unstructured":"Ben-Or, M. (1983, January 25\u201327). Lower bounds for algebraic computation trees (preliminary report). Proceedings of the the 15th Annual ACM Symposium on Theory of Computing (STOC 1983), Boston, MA, USA."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/s10208-015-9283-7","article-title":"On topological lower bounds for algebraic computation trees","volume":"17","author":"Gabrielov","year":"2017","journal-title":"Found. Comput. Math."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0304-3975(95)00159-X","article-title":"Complexity lower bounds for computation trees with elementary transcendental function gates","volume":"157","author":"Grigoriev","year":"1996","journal-title":"Theor. Comput. Sci."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1016\/j.dam.2022.06.032","article-title":"Rough analysis of computation trees","volume":"321","author":"Moshkov","year":"2022","journal-title":"Discret. Appl. Math."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1007\/3-540-18740-5_69","article-title":"On the programs with finite development","volume":"Volume 278","author":"Budach","year":"1987","journal-title":"Proceedings of the Fundamentals of Computation Theory, International Conference FCT\u201987"},{"key":"ref_10","unstructured":"Bj\u00f6rner, A., Lov\u00e1sz, L., and Yao, A.C. (1992, January 4\u20136). Linear decision trees: Volume estimates and topological bounds. Proceedings of the the 24th Annual ACM Symposium on Theory of Computing (STOC 1992), Victoria, BC, Canada."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1016\/0022-0000(78)90026-0","article-title":"A lower bound of the (1\/2)n2 on linear search programs for the knapsack problem","volume":"16","author":"Dobkin","year":"1978","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0022-0000(79)90054-0","article-title":"On the complexity of computations under varying sets of primitives","volume":"18","author":"Dobkin","year":"1979","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0196-6774(82)90002-5","article-title":"Lower bounds for algebraic decision trees","volume":"3","author":"Steele","year":"1982","journal-title":"J. Algorithms"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0304-3975(94)00082-T","article-title":"Algebraic decision trees and Euler characteristics","volume":"141","author":"Yao","year":"1995","journal-title":"Theor. Comput. Sci."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1145\/828.322450","article-title":"A polynomial linear search algorithm for the n-dimensional knapsack problem","volume":"31","year":"1984","journal-title":"J. ACM"},{"key":"ref_16","first-page":"528","article-title":"On conditional tests","volume":"27","author":"Moshkov","year":"1982","journal-title":"Sov. Phys. Dokl."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"auf der Heide, F.M. (1985, January 21\u201323). Nondeterministic versus probabilistic linear search algorithms. Proceedings of the the 26th Annual Symposium on Foundations of Computer Science (FOCS 1985), Portland, OR, USA.","DOI":"10.1109\/SFCS.1985.38"},{"key":"ref_18","first-page":"523","article-title":"On the relations between the depth of deterministic and nondeterministic acyclic programs in basis {x + y, x \u2212 y, 1; sign(x)}","volume":"Volume 21","author":"Moshkov","year":"1988","journal-title":"Mathematical Problems in Computational Theory"},{"key":"ref_19","first-page":"345","article-title":"Classification of infinite information systems depending on complexity of decision trees and decision rule systems","volume":"54","author":"Moshkov","year":"2003","journal-title":"Fundam. Inform."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Durdymyradov, K., Moshkov, M., and Ostonov, A. (2024). Decision Trees Versus Systems of Decision Rules. A Rough Set Approach, Springer. Studies in Big Data.","DOI":"10.1007\/978-3-031-71586-0"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"201","DOI":"10.3233\/FI-1996-25205","article-title":"Comparative analysis of deterministic and nondeterministic decision tree complexity. Global approach","volume":"25","author":"Moshkov","year":"1996","journal-title":"Fundam. Inform."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Moshkov, M. (2020). Comparative Analysis of Deterministic and Nondeterministic Decision Trees, Springer. Intelligent Systems Reference Library.","DOI":"10.1007\/978-3-030-41728-4"},{"key":"ref_23","unstructured":"Chang, C.C., and Keisler, H.J. (1992). Model Theory, Elsevier. [3rd ed.]. Studies in Logic and the Foundations of Mathematics."},{"key":"ref_24","unstructured":"Kleene, S.C. (1967). Mathematical Logic, Wiley."},{"key":"ref_25","unstructured":"Jech, T. (2002). Set Theory, Springer. [3rd ed.]. Springer Monographs in Mathematics."}],"container-title":["Axioms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2075-1680\/14\/4\/307\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T17:16:12Z","timestamp":1760030172000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2075-1680\/14\/4\/307"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,17]]},"references-count":25,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2025,4]]}},"alternative-id":["axioms14040307"],"URL":"https:\/\/doi.org\/10.3390\/axioms14040307","relation":{},"ISSN":["2075-1680"],"issn-type":[{"type":"electronic","value":"2075-1680"}],"subject":[],"published":{"date-parts":[[2025,4,17]]}}}