On the approximability relation for semantics of sequential programs (Q2563402)

Denote by \(R= \{ < \sigma, \pi_{1}, \pi_{2} >: \Phi_{\pi_{1}, \sigma} = \Phi_{\pi_{2}, \sigma} \}\) the functional equivalence program relation, where \(\sigma\) is the semantics, \(\pi_{1}, \pi_{2}\) are the program schemes, and \(\Phi_{\pi,\sigma}\) is a function which is computable by the program \(\pi\) in semantics \(\sigma\). Then for the semantics family of sequential programs \(\Omega\) and \(R\) some necessary and sufficient conditions for the \(R\)-approximability of the semantics are proved, and it is shown that the factor set \(\Omega / \approx_{R}\) is a complete lattice, where \(\approx_{R}\) is the equivalence relation of the semantics generated by the quasi-order \(\leq_{R}\).