标题： 低自动复杂度词语的语言很难计算 显示英文标题

标题： Languages of Words of Low Automatic Complexity Are Hard to Compute

摘要： The automatic complexity of a finite word (string) is an analogue for finite automata of Sipser's distinguishing complexity (1983) and was introduced by Shallit and Wang (2001). For a finite alphabet $\Sigma$ of at least two elements, we consider the non-deterministic automatic complexity given by exactly - yet not necessarily uniquely - accepting automata: a word $x \in \Sigma^*$ has exact non-deterministic automatic complexity $k \in \mathbb{N}$ if there exists a non-deterministic automaton of $k$ states which accepts $x$ while rejecting every other word of the same length as $x$, and no automaton of fewer states has this property. Importantly, and in contrast to the classical notion, the witnessing automaton may have multiple paths of computation accepting $x$. 我们用$A_{Ne}$表示这个复杂度度量，并研究了一类低$A_{Ne}$复杂度的语言，定义为$L_q = \{ \, x \in \Sigma^* : A_{Ne}(x) < q|x| \, \}$，该类由有理数$q \in (0,1/2)$参数化（推广了 Kjos-Hanssen 首先研究的一类集合）。 我们证明对于每个$q \in (0,1/2)$，该类既不是上下文无关的，也不能被某些布尔电路识别。 在此过程中，我们回答了 Kjos-Hanssen 提出的一个开放性问题，该问题量化了$L_{1/3}$在布尔电路中的复杂度，还证明了$A_{Ne}$的香农效应。 显示英文摘要

摘要： The automatic complexity of a finite word (string) is an analogue for finite automata of Sipser's distinguishing complexity (1983) and was introduced by Shallit and Wang (2001). For a finite alphabet $\Sigma$ of at least two elements, we consider the non-deterministic automatic complexity given by exactly - yet not necessarily uniquely - accepting automata: a word $x \in \Sigma^*$ has exact non-deterministic automatic complexity $k \in \mathbb{N}$ if there exists a non-deterministic automaton of $k$ states which accepts $x$ while rejecting every other word of the same length as $x$, and no automaton of fewer states has this property. Importantly, and in contrast to the classical notion, the witnessing automaton may have multiple paths of computation accepting $x$. We denote this measure of complexity by $A_{Ne}$, and study a class of languages of low $A_{Ne}$-complexity defined as $L_q = \{ \, x \in \Sigma^* : A_{Ne}(x) < q|x| \, \}$, which is parameterised by rationals $q \in (0,1/2)$ (generalising a class of sets first studied by Kjos-Hanssen). We show that for every $q \in (0,1/2)$, this class is neither context-free nor recognisable by certain Boolean circuits. In the process, we answer an open question of Kjos-Hanssen quantifying the complexity of $L_{1/3}$ in terms of Boolean circuits, and also prove the Shannon effect for $A_{Ne}$.