{"id":"arxiv/2601.01236","url":"https://arxiv.org/abs/2601.01236","tags":["cs.FL","math.GR","math.RA"],"score":0,"title":"The asymptotic size of finite irreducible semigroups of rational matrices","domain":"cs.FL","source":"arxiv","authors":["Stefan Kiefer","Andrew Ryzhikov"],"reviews":0,"subject":"cs.FL","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-01-03","reactions":{}}