On the Expressiveness of State Space Models via Temporal Logics
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911402476699648 |
|---|---|
| author | Alsmann, Eric Noori, Lowejatan Lange, Martin |
| author_facet | Alsmann, Eric Noori, Lowejatan Lange, Martin |
| contents | We investigate the expressive power of state space models (SSM), which have recently emerged as a potential alternative to transformer architectures in large language models. Building on recent work, we analyse SSM expressiveness through fragments and extensions of linear temporal logic over finite traces. Our results show that the expressive capabilities of SSM vary substantially depending on the underlying gating mechanism. We further distinguish between SSM operating over fixed-width arithmetic (quantised models), whose expressive power remains within regular languages, and SSM with unbounded precision, which can capture counting properties and non-regular languages. In addition, we provide a systematic comparison between these different SSM variants and known results on transformers, thereby clarifying how the two architectures relate in terms of expressive power. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_19467 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the Expressiveness of State Space Models via Temporal Logics Alsmann, Eric Noori, Lowejatan Lange, Martin Logic in Computer Science Formal Languages and Automata Theory Machine Learning We investigate the expressive power of state space models (SSM), which have recently emerged as a potential alternative to transformer architectures in large language models. Building on recent work, we analyse SSM expressiveness through fragments and extensions of linear temporal logic over finite traces. Our results show that the expressive capabilities of SSM vary substantially depending on the underlying gating mechanism. We further distinguish between SSM operating over fixed-width arithmetic (quantised models), whose expressive power remains within regular languages, and SSM with unbounded precision, which can capture counting properties and non-regular languages. In addition, we provide a systematic comparison between these different SSM variants and known results on transformers, thereby clarifying how the two architectures relate in terms of expressive power. |
| title | On the Expressiveness of State Space Models via Temporal Logics |
| topic | Logic in Computer Science Formal Languages and Automata Theory Machine Learning |
| url | https://arxiv.org/abs/2601.19467 |