Positive Neural Networks in Discrete Time Implement Monotone-Regular Behaviors

We study the expressive power of positive neural networks. The model uses positive connection weights and multiple input neurons. Different behaviors can be expressed by varying the connection weights. We show that in discrete time and in the absence of noise, the class of positive neural networks captures the so-called monotone-regular behaviors, which are based on regular languages. A finer picture emerges if one takes into account the delay by which a monotone-regular behavior is implemented. Each monotone-regular behavior can be implemented by a positive neural network with a delay of one time unit. Some monotone-regular behaviors can be implemented with zero delay. And, interestingly, some simple monotone-regular behaviors cannot be implemented with zero delay.

• Publication year

  2015

• Venue

  Neural Computation

• Publication date

  2015-02-21

• Fields of study

  Mathematics, Computer Science, Medicine

• Identifiers
  DOI 10.1162/NECO_a_00789arXiv 1502.06094PMID 26496040
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• STDP Installs in Winner-Take-All Circuits an Online Approximation to Hidden Markov Model Learning

  2014influential reference
• Noise as a Resource for Computation and Learning in Networks of Spiking Neurons

  2014cited by this paper
• A theoretical basis for efficient computations with noisy spiking neurons

  2014cited by this paper
• Neuronal Dynamics: From Single Neurons To Networks And Models Of Cognition

  2014cited by this paper
• Updating dopamine reward signals

  2013cited by this paper
• Monotone and Partially Monotone Neural Networks

  2010cited by this paper
• State-dependent computations: spatiotemporal processing in cortical networks

  2009cited by this paper
• On the Classification Capability of Sign-Constrained Perceptrons

  2008cited by this paper
• Monotone circuits for monotone weighted threshold functions

  2006cited by this paper
• Links between probabilistic automata and hidden Markov models: probability distributions, learning models and induction algorithms

  2005cited by this paper
• Neuronal circuits of the neocortex.

  2004cited by this paper
• General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results

  2003cited by this paper
• Contrasting neuronal activity in the supplementary and frontal eye fields during temporal organization of multiple saccades.

  2003cited by this paper
• On Monotone Automata and Monotone Languages

  2001cited by this paper
• Stable Encoding of Finite-State Machines in Discrete-Time Recurrent Neural Nets with Sigmoid Units

  2000cited by this paper
• Neuronal activity in the supplementary and presupplementary motor areas for temporal organization of multiple movements.

  2000cited by this paper
• Efficient encoding of finite automata in discrete-time recurrent neural networks

  1999cited by this paper
• Theory of neuromata

  1998cited by this paper
• Constructing deterministic finite-state automata in recurrent neural networks

  1996cited by this paper
• Lower Bounds for the Computational Power of Networks of Spiking Neurons

  1996cited by this paper
• Optimal Simulation of Automata by Neural Nets

  1995cited by this paper
• Circuit complexity and neural networks

  1994cited by this paper
• Bounds on the complexity of recurrent neural network implementations of finite state machines

  1993cited by this paper
• On the computational power of neural nets

  1992cited by this paper
• Efficient simulation of finite automata by neural nets

  1991cited by this paper
• Finding Structure in Time

  1990cited by this paper
• Introduction to the theory of computation

  1989cited by this paper
• The monotone circuit complexity of boolean functions

  1987influential reference
• Introduction to Automata Theory, Languages and Computation

  1979cited by this paper
• Implicit learning of artificial grammars

  1967cited by this paper

• Spatially Adaptable Mechanical Neural Networks with Multi Fully Connected Layers

  2026cites this paper
• GLOBAL DISSIPATIVITY OF POSITIVE NEURAL NETWORKS WITH TIME-VARYING DELAYS

  2025cites this paper
• Finite-time bumpless transfer synchronisation of discrete-time delayed positive neural networks under dual-channel false data inject attacks

  2025cites this paper
• Exponential attractivity of positive inertial neural networks in bidirectional associative memory model with heterogeneous delays

  2024cites this paper
• Positive Solutions and Exponential Stability of Nonlinear Time-Delay Systems in the Model of BAM-Cohen-Grossberg Neural Networks

  2022cites this paper
• State estimation for delayed positive neural networks under false data injection attack

  2021influential citation
• Positivity and Stability of Nonlinear Time-Delay Systems in Neural Networks

  2020cites this paper
• ℓ1-gain Filter Design of Discrete-time Positive Neural Networks with Mixed Delays

  2020cites this paper
• Exponential stability of positive neural networks in bidirectional associative memory model with delays

  2019cites this paper
• Monotone Data Samples Do Not Always Generate Monotone Fuzzy If-Then Rules

  2017cites this paper