Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Blum Static Complexity and Encoding Spaces
verfasst von : Cezar Câmpeanu
Erschienen in: Descriptional Complexity of Formal Systems
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.