























We show that the digraph of a nondeterministic finite automaton witnessing the automatic complexity of a word can always be taken to be planar. In the case of total transition functions studied by Shallit and Wang, planarity can fail. Let $s_q(n)$ be the number of binary words $x$ of length $n$ having nondeterministic automatic complexity $A_N(x)=q$. We show that $s_q$ is eventually constant for each $q$ and that the eventual constant value of $s_q$ is computable.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。