Comparison between the complexity of a function and the complexity of its graph

DOI10.1016/S0304-3975(01)00029-9zbMath0982.68073OpenAlexW1968180501MaRDI QIDQ5958280

Bruno Durand, Sylvain Porrot

Publication date: 3 March 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(01)00029-9

zbMATH Keywords

Kolmogorov complexitydata flow complexityrecursive functionrecursive infinite sequences

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items (1)

Descriptive complexity of computable sequences

Cites Work

• Relations between varieties of kolmogorov complexities
• A variant of the Kolmogorov concept of complexity
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• Descriptive complexity of computable sequences
• Unnamed Item
• Unnamed Item

This page was built for publication: Comparison between the complexity of a function and the complexity of its graph