Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.21226 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908677029494784 |
|---|---|
| author | Hoyrup, Mathieu |
| author_facet | Hoyrup, Mathieu |
| contents | Given a language, which in this article is a set of strings of some fixed length, we study the problem of producing its elements by a procedure in which each position has its own local rule. We introduce a way of measuring how much communication is needed between positions. The communication structure is captured by a simplicial complex whose vertices are the positions and the simplices are the communication channels between positions. The main problem is then to identify the simplicial complexes that can be used to generate a given language. We develop the theory and apply it to a number of languages. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_21226 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Local generation of languages Hoyrup, Mathieu Discrete Mathematics Combinatorics G.2.0 Given a language, which in this article is a set of strings of some fixed length, we study the problem of producing its elements by a procedure in which each position has its own local rule. We introduce a way of measuring how much communication is needed between positions. The communication structure is captured by a simplicial complex whose vertices are the positions and the simplices are the communication channels between positions. The main problem is then to identify the simplicial complexes that can be used to generate a given language. We develop the theory and apply it to a number of languages. |
| title | Local generation of languages |
| topic | Discrete Mathematics Combinatorics G.2.0 |
| url | https://arxiv.org/abs/2511.21226 |