The notion of descriptional complexity or algorithmic information, also known as Chaitin-Kolmogorov complexity, was defined in the '60s in terms of minimal description length [14, 17]. This concept was extended in 2012 in two papers, each using a different approach. One of the papers studies properties of the complexity function, and uses the notion of encoded function space; the other one extends Blum axioms for static complexity, and defines Blum static complexity spaces. In formal language theory we also use the concept of descriptional complexity for the number of states, or the number of transitions in a minimal finite automaton accepting a regular language, and apparently, this number has no connection to Chaitin-Kolmogorov complexity. In this paper we establish such a connection by extending the notions of Blum static complexity and of encoded function space.
展开▼
