05998433

j

05998433 Zhuk, D.N. A criterion for the decidability of the $A$-completeness problem for definite automata. Dokl. Math. 84, No. 1, 447-449 (2011); translation from Dokl. Akad. Nauk 439, No. 1, 18-20 (2011). 2011 Maik Nauka/Interperiodica, Moscow; Pleiades Publishing, New York; Springer, Secaucus, NJ EN definite automata algorithmic decidability A-completeness Boolean functions automatic structures monadic second-order logic push-down machines

doi:10.1134/S1064562411040065

A function $T: (E_{2}^{n})^{\infty}\to E_{2}^{\infty}$ with an input sequence $(\bold{x}(1),\bold{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}(\bold{x}(1), \bold{x}(2),\dots, \bold{x}(i))$ if $i\leq h$, and $y(i) = f_{h}(\bold{x}(i-h+1),\bold{x}(i-h+2),\dots,\bold{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$. Alex Nabebin (Moskva)