Logical semirings and their usage for construction of quick algorithms (Q1280316)

The author introduces the following definition. A semiring \(A\) is called a logical semiring, if the set of its elements can be split into two nonintersecting subsets \(A_0\) and \(A_1\) so that the mapping \(\varphi\: A\to S_2\), such that \(\varphi(a) = 0\) if \(a\in A_0\) and \(\varphi(a)=1\) if \(a\in A_1\), is a homomorphism of the semiring \(A\) on the semiring \(S_2\). The construction of quick algorithms for the determination of properties of a discrete function is described.