Languages of Words of Low Automatic Complexity Are Hard to Compute

MaRDI QIDQ7197445arXivFDO

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

Publication date 2025

Published in arXiv

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Networks and circuits as models of computation; circuit complexity (68Q06) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Formal languages and automata (68Q45)

arXiv classification

cs.FL

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 Q7197445)