A criterion for the decidability of the \(A\)-completeness problem for definite automata (Q656372)

A function \(T: (E_{2}^{n})^{\infty}\to E_{2}^{\infty}\) with an input sequence \((\mathbf{x}(1),\mathbf{x}(2),\dots) \in (E_{2}^{n})^{\infty}\) and an output sequence \((y(1),y(2),\dots)\in E_{2}^{\infty}\) is called a definite automaton with \(n\) inputs of height \(h\) if there are functions \(f_{j}: (E_{2}^{n})^j \to E_{2}\), \(j=1,2,\dots ,h\), such that \(y(i) = f_{i}(\mathbf{x}(1), \mathbf{x}(2),\dots, \mathbf{x}(i))\) if \(i\leq h\), and \(y(i) = f_{h}(\mathbf{x}(i-h+1),\mathbf{x}(i-h+2),\dots,\mathbf{x}(i))\) if \(i>h\). Let \(\mathcal{P}_{a}\) be the set of all definite automata. Any definite automaton can be obtained by superposition operations from Boolean functions and delays. Each Boolean function is associated with a definite automaton of height 1. Let \(t\in\mathbb{N}=\{1,2,3,\dots\}\). Two automata \(T_{1}\) and \(T_{2}\) with \(n\) inputs are \(t\)-equal if they coincide for words of length \(t\). Let \([M]_{t}\) be the set of all definite automata that are \(t\)-equal to those obtained from \(M\) by superposition operations. A set \(M\) is \(A\)-complete if \([M]_{t}=\mathcal{P}_{a}\) for any \(t\). Let \(F\) be a clone of Boolean functions. The \(A\)-completeness(\(F\)) problem is as follows: given a finite system \(V\) of definite automata, determine whether or not the system \(F\bigcup V\) is \(A\)-complete. For \(m\geq 2\), let \(f_{m}(x_{1},x_{2},\dots, x_{m+1}) = \bigvee_{i=1}^{m+1}x_{1}\dots x_{i-1}x_{i+1}\dots x_{m+1}\) and \((h_{m})^{*}\) be the dual of the function \(h\). Theorem. The \(A\)-completeness(\(F\)) problem is algorithmically decidable if and only if, for a certain \(f\in\{h_{2}, x+y+z, h_{3}, (h_{3})^{*}\}\), it is true that \(f\in F\).