Languages of words of low automatic complexity are hard to compute

DOI10.4230/LIPICS.FSTTCS.2025.24MaRDI QIDQ7391896zbMATH OpenFDO

Authors Joey Chen, Bjørn Kjos-Hanssen, Ivan Koswara, Linus Richter, Frank Stephan

Publication date 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.FSTTCS.2025.24

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Cites work

• A formal theory of inductive inference. Part I
• A formal theory of inductive inference. Part II
• A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
• A Second Course in Formal Languages and Automata Theory
• Algorithmic randomness and complexity.
• An incompressibility theorem for automatic complexity
• Asymptotical behaviour of some non-uniform measures
• Automata theory and its applications
• Automatic complexity of Fibonacci and tribonacci words
• Automatic complexity of shift register sequences
• Automatic complexity. A computable measure of irregularity
• Automaticity. I: Properties of a measure of descriptional complexity
• Boolean complexity classes vs. their arithmetic analogs
• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 3133387 (Why is no real title available?)
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 1970438 (Why is no real title available?)
• scientific article; zbMATH DE number 1747450 (Why is no real title available?)
• scientific article; zbMATH DE number 3293666 (Why is no real title available?)
• scientific article; zbMATH DE number 3422274 (Why is no real title available?)
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Maximal automatic complexity and context-free languages
• Nondeterministic automatic complexity of overlap-free and almost square-free words
• On the complexity of automatic complexity
• On the Tape Complexity of Deterministic Context-Free Languages
• Planar digraphs for automatic complexity
• Properties that characterize LOGCFL
• Ramanujan's proof of Bertrand's postulate
• Some theorems on the algorithmic approach to probability theory and information theory (1971 dissertation directed by A. N. Kolmogorov)
• The definition of random sequences
• The equation \(a_ M=b^ Nc^ P\) in a free group
• Two Applications of Inductive Counting for Complementation Problems

This page was built for publication: Languages of words of low automatic complexity are hard to compute

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