Descriptional complexity in encoded Blum static complexity spaces

DOI10.1142/S0129054114400152MaRDI QIDQ5173293zbMATHOpenAlexFDO

Authors C. Câmpeanu

Publication date 9 February 2015

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054114400152

zbMATH Keywords

state complexityBlum static complexity spaceChaitin-Kolmogorov complexitydual complexity measureencoded function space

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Blum Static Complexity and Encoding Spaces
• Invariance and Universality of Complexity
• A note on Blum static complexity measures
• Blum's and Burgin's axioms, complexity, and randomness
• Finite state complexity

Cites work

• A Theory of Program Size Formally Identical to Information Theory
• Algorithmic complexity as a criterion of unsolvability
• Algorithmic complexity of recursive and inductive algorithms
• Invariance and Universality of Complexity
• On the size of machines

Cited in

(2)

• Blum's and Burgin's axioms, complexity, and randomness
• Blum Static Complexity and Encoding Spaces

This page was built for publication: Descriptional complexity in encoded Blum static complexity spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5173293)