Showing 2025Show all
2 papers · 1 filter
cs.LO2025
The Computational Complexity of Satisfiability in State Space Models
Eric Alsmann, Martin Lange
We analyse the complexity of the satisfiability problem ssmSAT for State Space Models (SSM), which asks whether an input sequence can lead the model to an accepting configuration.…
cs.LG2025
The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logics
Marco Sälzer, Przemysław Andrzej Wałęga, Martin Lange
In recent years, the expressive power of various neural architectures -- including graph neural networks (GNNs), transformers, and recurrent neural networks -- has been characteris…