View in EDS

Descriptive complexity for neural networks via Boolean networks.

Saved in:
Bibliographic Details
Title: Descriptive complexity for neural networks via Boolean networks.
Authors: Ahvonen, Veeti1 (AUTHOR), Heiman, Damian1 (AUTHOR), Kuusisto, Antti1 (AUTHOR)
Source: Journal of Logic & Computation. Apr2026, Vol. 36 Issue 3, p1-56. 56p.
Subjects: Boolean networks, Feedforward neural networks, Floating-point arithmetic, Logic design, Artificial neural networks, Computational complexity
Abstract: 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! [ABSTRACT FROM AUTHOR]
Copyright of Journal of Logic & Computation is the property of Oxford University Press / USA and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 193363971
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Descriptive complexity for neural networks via Boolean networks.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Ahvonen%2C+Veeti%22">Ahvonen, Veeti</searchLink><relatesTo>1</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Heiman%2C+Damian%22">Heiman, Damian</searchLink><relatesTo>1</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Kuusisto%2C+Antti%22">Kuusisto, Antti</searchLink><relatesTo>1</relatesTo> (AUTHOR)
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Journal+of+Logic+%26+Computation%22">Journal of Logic & Computation</searchLink>. Apr2026, Vol. 36 Issue 3, p1-56. 56p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Boolean+networks%22">Boolean networks</searchLink><br /><searchLink fieldCode="DE" term="%22Feedforward+neural+networks%22">Feedforward neural networks</searchLink><br /><searchLink fieldCode="DE" term="%22Floating-point+arithmetic%22">Floating-point arithmetic</searchLink><br /><searchLink fieldCode="DE" term="%22Logic+design%22">Logic design</searchLink><br /><searchLink fieldCode="DE" term="%22Artificial+neural+networks%22">Artificial neural networks</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+complexity%22">Computational complexity</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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! [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Journal of Logic & Computation is the property of Oxford University Press / USA and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=193363971
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1093/logcom/exag011
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 56
        StartPage: 1
    Subjects:
      – SubjectFull: Boolean networks
        Type: general
      – SubjectFull: Feedforward neural networks
        Type: general
      – SubjectFull: Floating-point arithmetic
        Type: general
      – SubjectFull: Logic design
        Type: general
      – SubjectFull: Artificial neural networks
        Type: general
      – SubjectFull: Computational complexity
        Type: general
    Titles:
      – TitleFull: Descriptive complexity for neural networks via Boolean networks.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Ahvonen, Veeti
      – PersonEntity:
          Name:
            NameFull: Heiman, Damian
      – PersonEntity:
          Name:
            NameFull: Kuusisto, Antti
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 04
              Text: Apr2026
              Type: published
              Y: 2026
          Identifiers:
            – Type: issn-print
              Value: 0955792X
          Numbering:
            – Type: volume
              Value: 36
            – Type: issue
              Value: 3
          Titles:
            – TitleFull: Journal of Logic & Computation
              Type: main
ResultId 1