Theoretical Advances and Computational Limits in Automata and Neural Networks

The recent developments in the research area have primarily focused on advancing theoretical understanding and computational capabilities of various models, particularly in the context of automata theory and deep learning architectures. A significant trend is the exploration of the computational limits and expressiveness of modern neural network models, such as Hopfield networks and state-space models, through the lens of circuit complexity theory. These studies have provided rigorous bounds on the computational capabilities of these models, revealing their theoretical limitations and guiding the development of new architectures. Additionally, there has been notable progress in automata theory, with research on the undecidability of probabilistic finite automaton emptiness problems and lower bounds on state complexity for transforming two-way nondeterministic finite automata to unambiguous finite automata. These findings contribute to a deeper understanding of the fundamental properties and limitations of these models. Furthermore, novel approaches in combinatorial optimization, such as non-binary dynamical Ising machines, have demonstrated the potential for scalable electronic accelerators by bridging the gap between continuous dynamical systems and discrete optimization problems. Overall, the field is moving towards a more nuanced understanding of computational models, with a focus on both theoretical rigor and practical implications for scalable and efficient solutions.

Sources

Probabilistic Finite Automaton Emptiness is Undecidable for a Fixed Automaton

On the Expressive Power of Modern Hopfield Networks

The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity

A lower bound on the state complexity of transforming two-way nondeterministic finite automata to unambiguous finite automata

Probability and Angelic Nondeterminism with Multiset Semantics

Non-binary dynamical Ising machines for combinatorial optimization

Nondeterministic Auxiliary Depth-Bounded Storage Automata and Semi-Unbounded Fan-in Cascading Circuits

Built with on top of