{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T13:43:12Z","timestamp":1773322992614,"version":"3.50.1"},"reference-count":55,"publisher":"Oxford University Press (OUP)","issue":"3","license":[{"start":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T00:00:00Z","timestamp":1773187200000},"content-version":"vor","delay-in-days":2,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026,3,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>We investigate the expressive power of neural networks from the point of view of descriptive complexity. We study neural networks that use floating-point numbers and piecewise polynomial activation functions from two perspectives: (i) the general scenario where neural networks run for an unlimited number of computation steps and have unrestricted topologies, and (ii) classical feedforward neural networks that have the topology of layered acyclic graphs and run for only a constant number of computation steps. We characterize these neural networks via Boolean networks formalized via a recursive rule-based logic. In particular, we show that the sizes of the neural networks and the corresponding Boolean rule formulae are polynomially related. In fact, in the translation from Boolean rules to neural networks, the blow-up is only linear. Our translations result in a time delay, defined as the number of computation steps that the output-object of the translation (e.g. a neural network or Boolean rule formula) uses to simulate a single computation step of the input-object. In the translation from neural networks to Boolean rules, the time delay of the resulting formula is polylogarithmic in the size of the neural network. In the converse translation, the time delay of the neural network is linear in the formula size. Ultimately, we obtain translations between neural networks, Boolean networks, the diamond-free fragment of modal substitution calculus and a class of recursive Boolean circuits. Our translations offer a method, for almost any activation function F, of translating any neural network in our setting into an equivalent neural network that uses F at each node. This even includes linear activation functions, which is possible due to using floats rather than actual reals!<\/jats:p>","DOI":"10.1093\/logcom\/exag011","type":"journal-article","created":{"date-parts":[[2026,2,17]],"date-time":"2026-02-17T12:32:53Z","timestamp":1771331573000},"source":"Crossref","is-referenced-by-count":0,"title":["Descriptive complexity for neural networks via Boolean networks"],"prefix":"10.1093","volume":"36","author":[{"given":"Veeti","family":"Ahvonen","sequence":"first","affiliation":[{"name":"Mathematics Research Centre, Tampere University , 33720, Tampere ,","place":["Finland"]}]},{"given":"Damian","family":"Heiman","sequence":"additional","affiliation":[{"name":"Mathematics Research Centre, Tampere University , 33720, Tampere ,","place":["Finland"]}]},{"given":"Antti","family":"Kuusisto","sequence":"additional","affiliation":[{"name":"Mathematics Research Centre, Tampere University , 33720, Tampere ,","place":["Finland"]}]}],"member":"286","published-online":{"date-parts":[[2026,3,11]]},"reference":[{"key":"2026031117155398000_ref1","doi-asserted-by":"publisher","first-page":"9:1","DOI":"10.4230\/LIPICS.MFCS.2023.9","article-title":"Descriptive complexity for distributed computing with circuits","volume-title":"48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, August 28 to September 1, 2023, Bordeaux, France, volume 272 of LIPIcs","author":"Ahvonen","year":"2023"},{"key":"2026031117155398000_ref2","doi-asserted-by":"publisher","first-page":"9:1","DOI":"10.4230\/LIPICS.CSL.2024.9","article-title":"Descriptive complexity for neural networks via boolean networks","volume-title":"32nd EACSL Annual Conference on Computer Science Logic, CSL 2024, February 19-23, 2024, Naples, Italy, volume 288 of LIPIcs","author":"Ahvonen","year":"2024"},{"key":"2026031117155398000_ref3","doi-asserted-by":"crossref","DOI":"10.52202\/079017-3311","article-title":"Logical characterizations of recurrent graph neural networks with reals and floats","volume-title":"The Thirty-eighth Annual Conference on Neural Information Processing Systems","author":"Ahvonen","year":"2024"},{"key":"2026031117155398000_ref4","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exae087","article-title":"Descriptive complexity for distributed computing with circuits","volume":"35","author":"Ahvonen","year":"2025","journal-title":"Journal of Logic and Computation"},{"key":"2026031117155398000_ref5","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2505.07966","author":"Ahvonen","year":"2025","journal-title":"CoRR"},{"key":"2026031117155398000_ref6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/2500000051","article-title":"Introduction to neural network verification","volume":"7","author":"Albarghouthi","year":"2021","journal-title":"Foundations and Trends in Programming Languages"},{"key":"2026031117155398000_ref7","article-title":"The logical expressiveness of graph neural networks","volume-title":"8th International Conference on Learning Representations, ICLR 2020","author":"Barcel\u00f3","year":"2020"},{"key":"2026031117155398000_ref8","doi-asserted-by":"publisher","first-page":"1155","DOI":"10.1016\/0893-6080(96)00130-X","article-title":"On the circuit complexity of sigmoid feedforward neural networks","volume":"9","author":"Beiu","year":"1996","journal-title":"Neural Networks"},{"key":"2026031117155398000_ref9","article-title":"Compiling neural network classifiers into boolean circuits for efficient Shap-score computation","volume-title":"Proceedings of AMW","author":"Bertossi","year":"2023"},{"key":"2026031117155398000_ref10","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781107050884","volume-title":"Modal Logic: Graph. Darst","author":"Blackburn","year":"2001"},{"key":"2026031117155398000_ref11","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/0020-0190(94)90093-0","article-title":"Size-depth tradeoffs for boolean formulae","volume":"49","author":"Bonet","year":"1994","journal-title":"Information Processing Letters"},{"key":"2026031117155398000_ref12","volume-title":"Sequential Logic: Analysis and Synthesis","author":"Cavanagh","year":"2006"},{"key":"2026031117155398000_ref13","volume-title":"Most Permissive Semantics of Boolean Networks","author":"Chatain","year":"2020"},{"key":"2026031117155398000_ref14","doi-asserted-by":"crossref","first-page":"2251","DOI":"10.1109\/TAC.2010.2043294","article-title":"A linear representation of dynamics of boolean networks","volume":"55","author":"Cheng","year":"2010","journal-title":"IEEE Transactions on Automatic Control"},{"key":"2026031117155398000_ref15","volume":"17","author":"Choi","journal-title":"Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning"},{"key":"2026031117155398000_ref16","doi-asserted-by":"crossref","DOI":"10.3233\/FAIA200158","article-title":"On the reasons behind decisions","volume-title":"24th European Conference on Artificial Intelligence, ECAI 2020, vol. 325 of Frontiers in Artificial Intelligence and Applications","author":"Darwiche","year":"2020"},{"key":"2026031117155398000_ref17","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/J.NEUCOM.2022.06.111","article-title":"Activation functions in deep learning: a comprehensive survey and benchmark","volume":"503","author":"Dubey","year":"2022","journal-title":"Neurocomputing"},{"key":"2026031117155398000_ref18","article-title":"PSPACE-completeness of majority automata networks","volume-title":"Theoretical Computer Science","author":"Goles"},{"key":"2026031117155398000_ref19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/LICS52264.2021.9470677","article-title":"The logic of graph neural networks","volume-title":"36th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2021","author":"Grohe","year":"2021"},{"key":"2026031117155398000_ref20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/LICS56636.2023.10175735","article-title":"The descriptive complexity of graph neural networks","volume-title":"38th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2023","author":"Grohe","year":"2023"},{"key":"2026031117155398000_ref21","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1145\/2332432.2332466","article-title":"Weak models of distributed computing, with connections to modal logic","volume-title":"Proceedings of the 2012 ACM Symposium on Principles of distributed computing","author":"Hella","year":"2012"},{"key":"2026031117155398000_ref22","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/s00446-013-0202-3","article-title":"Weak models of distributed computing, with connections to modal logic","volume":"28","author":"Hella","year":"2015","journal-title":"Distributed Computing"},{"key":"2026031117155398000_ref23","first-page":"1511","article-title":"Abduction-based explanations for machine learning models","volume-title":"Proceedings of the AAAI conference on artificial intelligence","author":"Ignatiev","year":"2019"},{"key":"2026031117155398000_ref24","doi-asserted-by":"publisher","DOI":"10.1613\/JAIR.1.17422","article-title":"Explainability via short formulas: the case of propositional logic with implementation","volume":"83","author":"Jaakkola","year":"2025","journal-title":"Journal of Artificial Intelligence Research"},{"key":"2026031117155398000_ref25","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/978-3-319-63387-9_5","article-title":"Reluplex: an efficient SMT solver for verifying deep neural networks","volume-title":"Computer Aided Verification","author":"Katz","year":"2017"},{"key":"2026031117155398000_ref26","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1038\/224177a0","article-title":"Homeostasis and differentiation in random genetic control networks","volume":"224","author":"Kauffman","year":"1969","journal-title":"Nature"},{"key":"2026031117155398000_ref27","volume-title":"The Art of Computer Programming. Volume 2, Seminumerical Algorithms","author":"Knuth","year":"1997"},{"key":"2026031117155398000_ref28","doi-asserted-by":"publisher","first-page":"786","DOI":"10.1109\/TC.1973.5009159","article-title":"A parallel algorithm for the efficient solution of a general class of recurrence equations","volume":"C-22","author":"Kogge","year":"1973","journal-title":"IEEE Transactions on Computers"},{"key":"2026031117155398000_ref29","first-page":"452","article-title":"Modal logic and distributed message passing automata","volume-title":"Computer Science Logic 2013 (CSL 2013), volume 23 of Leibniz International Proceedings in Informatics (LIPIcs)","author":"Kuusisto","year":"2013"},{"key":"2026031117155398000_ref30","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-07003-1","volume-title":"Elements of Finite Model Theory. Texts in Theoretical Computer Science. An EATCS Series","author":"Libkin","year":"2004"},{"key":"2026031117155398000_ref31","article-title":"Algorithms for verifying deep neural networks","volume-title":"Foundations and Trends in Optimization","author":"Liu","year":"2020"},{"key":"2026031117155398000_ref32","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/BF02478259","article-title":"A logical calculus of the ideas immanent in nervous activity","volume":"5","author":"McCulloch","year":"1943","journal-title":"The Bulletin of Mathematical Biophysics"},{"key":"2026031117155398000_ref33","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-76526-6","volume-title":"Handbook of Floating-Point Arithmetic","author":"Muller","year":"2018"},{"key":"2026031117155398000_ref34","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0022-0000(73)80043-1","article-title":"Optimal algorithms for parallel polynomial evaluation","volume":"7","author":"Munro","year":"1973","journal-title":"Journal of Computer and System Sciences"},{"key":"2026031117155398000_ref35","article-title":"An introduction to convolutional neural networks","author":"O\u2019shea","year":"2015"},{"key":"2026031117155398000_ref36","first-page":"5363","article-title":"EvolveGCN: evolving graph convolutional networks for dynamic graphs","volume-title":"Proceedings of the AAAI conference on artificial intelligence","author":"Pareja","year":"2020"},{"key":"2026031117155398000_ref37","article-title":"Complexity of boolean automata networks under block-parallel update modes","volume-title":"3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)","author":"Perrot"},{"key":"2026031117155398000_ref38","first-page":"100:1","article-title":"Asynchronous distributed automata: a characterization of the modal mu-fragment","volume-title":"44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs","author":"Reiter","year":"2017"},{"key":"2026031117155398000_ref39","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1007\/978-3-540-30124-0_29","article-title":"Logical characterizations of PSPACE","volume-title":"Computer Science Logic, 18th International Workshop, CSL 2004, 13th Annual Conference of the EACSL, Karpacz, Poland, September 20-24, 2004, Proceedings, volume 3210 of Lecture Notes in Computer Science","author":"Richerby","year":"2004"},{"key":"2026031117155398000_ref40","article-title":"Logical neural networks","author":"Riegel","year":"2020","journal-title":"CoRR"},{"key":"2026031117155398000_ref41","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1038\/323533a0","article-title":"Learning representations by back-propagating errors","volume":"323","author":"Rumelhart","year":"1986","journal-title":"Nature"},{"key":"2026031117155398000_ref42","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1016\/j.csbj.2020.03.001","article-title":"Concepts in boolean network modeling: what do they all mean?","volume":"18","author":"Schwab","year":"2020","journal-title":"Computational and Structural Biotechnology Journal"},{"key":"2026031117155398000_ref43","article-title":"Logic tensor networks: deep learning and logical reasoning from data and knowledge","volume-title":"Proceedings of the 11th International Workshop on Neural-Symbolic Learning and Reasoning (NeSy\u201916) co-located with the Joint Multi-Conference on Human-Level Artificial Intelligence (HLAI 2016), New York City, NY, USA, July 16-17, 2016, volume 1768 of CEUR Workshop Proceedings","author":"Serafini","year":"2016"},{"key":"2026031117155398000_ref44","doi-asserted-by":"crossref","DOI":"10.33564\/IJEAST.2020.v04i12.054","article-title":"Activation functions in neural networks","volume":"4","author":"Sharma","year":"2020","journal-title":"International Journal of Engineering Applied Sciences and Technology"},{"key":"2026031117155398000_ref45","doi-asserted-by":"crossref","first-page":"971","DOI":"10.1016\/S0893-6080(05)80093-0","article-title":"Classes of feedforward neural networks and their circuit complexity","volume":"5","author":"Shawe-Taylor","year":"1992","journal-title":"Neural Networks"},{"key":"2026031117155398000_ref46","volume-title":"Foundations of Recurrent Neural Networks","author":"Siegelmann","year":"1993"},{"key":"2026031117155398000_ref47","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/3-540-58201-0_55","article-title":"On the computational power of probabilistic and faulty neural networks","volume-title":"International Colloquium on Automata, Languages, and Programming","author":"Siegelmann","year":"1994"},{"key":"2026031117155398000_ref48","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1111\/j.1467-8640.1996.tb00277.x","article-title":"Recurrent neural networks and finite automata","volume":"12","author":"Siegelmann","year":"1996","journal-title":"Computational Intelligence"},{"key":"2026031117155398000_ref49","doi-asserted-by":"crossref","first-page":"2727","DOI":"10.1162\/089976603322518731","article-title":"General-purpose computation with neural networks: a survey of complexity theoretic results","volume":"15","author":"\u0160\u00edma","year":"2003","journal-title":"Neural Computation"},{"key":"2026031117155398000_ref50","doi-asserted-by":"crossref","first-page":"1871","DOI":"10.1162\/neco_a_01522","article-title":"Probing the relationship between latent linear dynamical systems and low-rank recurrent neural network models","volume":"34","author":"Valente","year":"2022","journal-title":"Neural Computation"},{"key":"2026031117155398000_ref51","article-title":"Attention is all you need","volume-title":"Advances in Neural Information Processing Systems","author":"Vaswani","year":"2017"},{"key":"2026031117155398000_ref52","doi-asserted-by":"crossref","first-page":"1268","DOI":"10.1109\/72.641450","article-title":"Recurrent neural nets as dynamical boolean systems with application to associative memory","volume":"8","author":"Watta","year":"1997","journal-title":"IEEE Transactions on Neural Networks"},{"key":"2026031117155398000_ref53","first-page":"12","article-title":"The reduction of a graph to canonical form and the algebra which appears therein","volume":"2","author":"Weisfeiler","year":"1968","journal-title":"Nauchno-Tekhnicheskaya Informatsiya"},{"key":"2026031117155398000_ref54","first-page":"27","article-title":"Boolean networks for cryptography and secure communication","volume":"1","author":"Zanin","year":"2011","journal-title":"Nonlinear Science Letters B: Chaos, Fractal and Synchronization."},{"key":"2026031117155398000_ref55","doi-asserted-by":"crossref","first-page":"16308","DOI":"10.1073\/pnas.0806447105","article-title":"Network model of survival signaling in large granular lymphocyte leukemia","volume":"105","author":"Zhang","year":"2008","journal-title":"Proceedings of the National Academy of Sciences"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/36\/3\/exag011\/67302650\/exag011.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/36\/3\/exag011\/67302650\/exag011.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T21:16:06Z","timestamp":1773263766000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/doi\/10.1093\/logcom\/exag011\/8514506"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,9]]},"references-count":55,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,3,9]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exag011","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"value":"0955-792X","type":"print"},{"value":"1465-363X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2026,4]]},"published":{"date-parts":[[2026,3,9]]},"article-number":"exag011"}}