Research map / Learning theory and algorithms / Sample complexity
Automata Cascades: Expressivity and Sample Complexity
Alessandro Ronca, Nadezda Alexandrovna Knorozova, Giuseppe De Giacomo
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a simple cascade of prime automata | Automata · Regular languages | expressivity | Improved |
| Restrict cascade components to flip-flops | Group-free automata · Star-free regular languages | expressivity | Improved |
Closest papers by meaning
- First-Order Automata (AAAI 2025 · similarity 0.84)
- On the Expressiveness and Length Generalization of Selective State Space Models on Regular Languages (AAAI 2025 · similarity 0.83)
- Non-Asymptotic Length Generalization (ICML 2025 · similarity 0.83)
- CAX: Cellular Automata Accelerated in JAX (ICLR 2025 · similarity 0.82)
- Discovering modular solutions that generalize compositionally (ICLR 2024 · similarity 0.82)
- (How) Do Language Models Track State? (ICML 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
