From Formal Language Theory to Statistical Learning: Finite Observability of Subregular Languages
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910051191488512 |
|---|---|
| author | Hayashi, Katsuhiko Kamigaito, Hidetaka |
| author_facet | Hayashi, Katsuhiko Kamigaito, Hidetaka |
| contents | We prove that all standard subregular language classes are linearly separable when represented by their deciding predicates. This establishes finite observability and guarantees learnability with simple linear models. Synthetic experiments confirm perfect separability under noise-free conditions, while real-data experiments on English morphology show that learned features align with well-known linguistic constraints. These results demonstrate that the subregular hierarchy provides a rigorous and interpretable foundation for modeling natural language structure. Our code used in real-data experiments is available at https://github.com/UTokyo-HayashiLab/subregular. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_22598 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | From Formal Language Theory to Statistical Learning: Finite Observability of Subregular Languages Hayashi, Katsuhiko Kamigaito, Hidetaka Computation and Language Formal Languages and Automata Theory Machine Learning We prove that all standard subregular language classes are linearly separable when represented by their deciding predicates. This establishes finite observability and guarantees learnability with simple linear models. Synthetic experiments confirm perfect separability under noise-free conditions, while real-data experiments on English morphology show that learned features align with well-known linguistic constraints. These results demonstrate that the subregular hierarchy provides a rigorous and interpretable foundation for modeling natural language structure. Our code used in real-data experiments is available at https://github.com/UTokyo-HayashiLab/subregular. |
| title | From Formal Language Theory to Statistical Learning: Finite Observability of Subregular Languages |
| topic | Computation and Language Formal Languages and Automata Theory Machine Learning |
| url | https://arxiv.org/abs/2509.22598 |