Subsumptive general solutions and parametric general solutions of Post equations (Q454896)

The solution of a Boolean equation by a system of recurrent inequalities has been well known for a long time. An axiomatization of this method was introduced and studied by \textit{R. Melter} and the reviewer [Colloq. Math. Soc. Janos Bolyai 33, 637--650 (1983; Zbl 0523.94028)] under the name of subsumptive general solution; it applies verbatim to Post equations as follows. Let \( f: P^n\to P \) be a Post function such that the equation \( f(x_1,\dots,x_n)=0 \) is consistent, and let \( u_k,v_k:P^{n-k}\to P\), \(k=1,\dots,n-1\), \(u_n,v_n\in P \) be Post functions. The system of inequalities \[ u_j(x_{j+1},\dots,x_n)\leq x_j\leq v_j(x_{j+1},\dots,x_n), \quad j=1,\dots,n-1, \] \[ u_n\leq x_n \leq v_n, \] is said to determine a subsumptive general solution of the equation \( f(x_1,\dots,x_n)=0 \) iff the above inequalities are equivalent to the property that for every \( k\in\{1,\dots,n\} \) and every \( (x_k,\dots,x_n)\in P^{n-k+1}\) there exists \( (x_1,\dots,x_{k-1})\in P^{k-1} \) such that \( f(x_1,\dots,x_n)=0 \). The authors provide a necessary and sufficient condition for a system of Post functions \( u_k,v_k \) to be a subsumptive general solution of a Post equation \( f = 0\). They also prove that any Post transformation \( X = \Phi(T) \) is a parametric general solution of a certain Post equation. These theorems generalize results obtained by the reviewer [Inf. Sci. 180, No. 12, 2440--2447 (2010; Zbl 1209.06006)] for Boolean equations.