The asymptotic size of finite irreducible semigroups of rational matrices
In this paper we investigate the maximum size of finite semigroups of rational $n \times n$ matrices, with the goal of shedding more light on their structure. Such semigroups provide a rich generalisation of transition monoids of unambiguous (and, in particular, deterministic) finite automata. While in general such semigroups can be arbitrarily large in terms of $n$, a classical result of Schützenberger from 1962 implies an upper bound of $2^{O(n^2 \log n)}$ for irreducible semigroups. A semigroup of rational matrices is called irreducible if the only subspaces of $\mathbb{Q}^n$ that are…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2601.01236
curl -X POST /api/v1/records/arxiv/2601.01236/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.01236/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'