Languages of Words of Low Automatic Complexity Are Hard to Compute
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909832332705792 |
|---|---|
| author | Chen, Joey Kjos-Hanssen, Bjørn Koswara, Ivan Richter, Linus Stephan, Frank |
| author_facet | Chen, Joey Kjos-Hanssen, Bjørn Koswara, Ivan Richter, Linus Stephan, Frank |
| contents | 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 $Σ$ 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 Σ^*$ 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 Σ^* : 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}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_07696 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Languages of Words of Low Automatic Complexity Are Hard to Compute Chen, Joey Kjos-Hanssen, Bjørn Koswara, Ivan Richter, Linus Stephan, Frank Formal Languages and Automata Theory Logic 68Q45 (Primary) 03D05, 68Q30, 68Q06 (Secondary) F.4.2; F.4.3 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 $Σ$ 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 Σ^*$ 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 Σ^* : 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}$. |
| title | Languages of Words of Low Automatic Complexity Are Hard to Compute |
| topic | Formal Languages and Automata Theory Logic 68Q45 (Primary) 03D05, 68Q30, 68Q06 (Secondary) F.4.2; F.4.3 |
| url | https://arxiv.org/abs/2510.07696 |