On the complexity of automatic complexity

DOI10.1007/s00224-017-9795-4zbMath1387.68158arXiv1607.06106OpenAlexW2963062403MaRDI QIDQ1694011

Bjørn Kjos-Hanssen

Publication date: 1 February 2018

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1607.06106

zbMATH Keywords

computational complexityNP-completenesscontext-free languagesautomatic complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Automatic complexity of Fibonacci and tribonacci words ⋮ An incompressibility theorem for automatic complexity ⋮ The number of languages with maximum state complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Nondeterministic automatic complexity of overlap-free and almost square-free words
• Every iterated morphism yields a co-CFL
• A multi-parameter analysis of hard problems on deterministic finite automata
• The Complexity of Complexity
• Algorithmic Randomness and Complexity
• The Boolean Hierarchy I: Structural Properties
• Complexity of automaton identification from given data
• On the complexity of minimum inference of regular sets

This page was built for publication: On the complexity of automatic complexity