Linear stationary control systems over the Boolean semiring and their graphs of modules

We consider linear stationary dynamical systems over the Boolean semiring. We analyze the properties of complete observability, identifiability, attainability, and controllability of a system. We define the notion of the “graph of modules” of totally controllable totally attainable Boolean linear stationary systems by analogy with spaces of modules in the case of systems over fields. The above-mentioned graph is described in the simplest case of one-dimensional inputs and outputs. We prove the weak connectedness of this oriented graph.     

On the shape of solution sets of systems of (functional) equations

Solution sets of systems of linear equations over fields are characterized as being affine subspaces. But what can we say about the “shape” of the set of all solutions of other systems of equations? We study solution sets over arbitrary algebraic structures, and we give a necessary condition for a set of n-tuples to be the set of solutions of a system of equations in n unknowns over a given algebra. In the case of Boolean equations we obtain a complete characterization, and we also characterize solution sets of systems of Boolean functional equations.     

Some remarks on Boolean control systems: Controllability domains and realization theory

We construct a theory of realizations and controllability domains for linear stationary systems in the category of finitely generated free semimodules over a Boolean semiring. We show that the classical realization theorems cannot be generalized to this case, and we prove some incomplete analogs of these theorems. We analyze the structure of controllability domains and the reachability and observability characteristics. In particular, we define a geometric object representing the reachability properties of a system, namely, the generalized reachability topology on the state space.     

Boolean autoencoders and hypercube clustering complexity

We introduce and study the properties of Boolean autoencoder circuits. In particular, we show that the Boolean autoencoder circuit problem is equivalent to a clustering problem on the hypercube. We show that clustering m binary vectors on the n-dimensional hypercube into k clusters is NP-hard, as soon as the number of clusters scales like ${m^\epsilon (\epsilon >0 )}$ , and thus the general Boolean autoencoder problem is also NP-hard. We prove that the linear Boolean autoencoder circuit problem is also NP-hard, and so are several related problems such as: subspace identification over finite fields, linear regression over finite fields, even/odd set intersections, and parity circuits. The emerging picture is that autoencoder optimization is NP-hard in the general case, with a few notable exceptions including the linear cases over infinite fields or the Boolean case with fixed size hidden layer. However learning can be tackled by approximate algorithms, including alternate optimization, suggesting a new class of learning algorithms for deep networks, including deep networks of threshold gates or artificial neurons.     

Lower estimates of circuit complexity in the basis of antichain functions

The antichain function is a characteristic function of an antichain in the Boolean cube. The set of antichain functions is an infinite complete basis. We study the computational complexity of Boolean functions over an antichain functional basis. In this paper we prove an asymptotic lower bound of order $\sqrt n $ for the computational complexity of a linear function, a majority function, and almost all Boolean functions of n variables.     

Linear codes from vectorial Boolean power functions

In this paper, three classes of binary linear codes with few weights are proposed from vectorial Boolean power functions, and their weight distributions are completely determined by solving certain equations over finite fields. In particular, a class of simplex codes and a class of first-order Reed-Muller codes can be obtained from our construction by taking the identity map, whose dual codes are Hamming codes and extended Hamming codes, respectively.     

On the generalized indices of boolean matrices

We characterize completely those Boolean matrices with the largest generalized indices in the class of Boolean matrices and in the class of reducible Boolean matrices and derive a new upper bound for the generalized index in terms of period. We also generalize the upper and lower multiexponents of primitive Boolean matrices to general Boolean matrices.     

On the generalized indices of boolean matrices

We characterize completely those Boolean matrices with the largest generalized indices in the class of Boolean matrices and in the class of reducible Boolean matrices and derive a new upper bound for the generalized index in terms of period. We also generalize the upper and lower multiexponents of primitive Boolean matrices to general Boolean matrices.     

Basic Theory in Construction of Boolean Functions with Maximum Possible Annihilator Immunity

So far there is no systematic attempt to construct Boolean functions with maximum annihilator immunity. In this paper we present a construction keeping in mind the basic theory of annihilator immunity. This construction provides functions with the maximum possible annihilator immunity and the weight, nonlinearity and algebraic degree of the functions can be properly calculated under certain cases. The basic construction is that of symmetric Boolean functions and applying linear transformation on the input variables of these functions, one can get a large class of non-symmetric functions too. Moreover, we also study several other modifications on the basic symmetric functions to identify interesting non-symmetric functions with maximum annihilator immunity. In the process we also present an algorithm to compute the Walsh spectra of a symmetric Boolean function with O(n²) time and O(n) space complexity. We use the term “Annihilator Immunity” instead of “Algebraic Immunity” referred in the recent papers [3–5, 9, 18, 19]. Please see Remark 1 for the details of this notational change     

Complete observability of differential-algebraic systems with delays

We study the statement and solvability of complete observability problems for linear stationary differential-algebraic dynamical systems with delays (DAD systems. Since in the general case, the state space of such systems is infinite-dimensional and is not necessarily “minimal,” we consider various statements of problems depending on what states are observed. Our attention is focused on the simplest DAD system in symmetric form. We obtain efficient parametric criteria and analyze relationships between various notions of complete observability for DAD systems. In the case of DAD systems with scalar coefficients, we obtain a complete classification of notions of complete observability in the class of continuous initial functions with the continuous matching condition. We analyze the problem of computing the minimum number of outputs of a spectrally observable DAD system.     

Special elements of the lattice of epigroup varieties

We describe right-hand skew Boolean algebras in terms of a class of presheaves of sets over Boolean algebras called Boolean sets, and prove a duality theorem between Boolean sets and étalé spaces over Boolean spaces.     

The spherical constraint in Boolean quadratic programs

We propose a new approach to bound Boolean quadratic optimization problems. The idea is to re-express the Boolean constraints as one “spherical” constraint, whose dualization amounts to semidefinite least-squares problems. Studying this dualization provides an alternative interpretation of the sdp relaxation. It also reveals a new class of non-convex problems with no duality gap.     

Boolean-rank-preserving operators and Boolean-rank-1 spaces

We study the extent to which certain theorems on linear operators on field-valued matrices carry over to linear operators on Boolean matrices. We obtain analogues and near analogues of several such theorems. One of these leads us to consider linear spaces of m × n Boolean matrices whose nonzero members all have Boolean rank 1. We obtain a structure theorem for such spaces that enables us to determine the maximum Boolean dimension of such spaces and their maximum cardinality.     

Complexity of the Realization of a Linear Boolean Function in the Class of <Emphasis Type="Italic">π</Emphasis>-Schemes

Using Khrapchenko’s method, we obtain the exact lower bound of 40 for the complexity in the class of π-schemes of a linear Boolean function depending substantially on 6 variables. We give a simplified proof of several lower bounds for the complexity of linear Boolean functions which are previously obtained on the basis of the same method.     

Standard completions for quasiordered sets

A standard completion for a quasiordered set Q is a closure system whose point closures are the principal ideals of Q. We characterize the following types of standard completions by means of their closure operators:

1. V-distributive completions,
2. Completely distributive completions,
3. A-completions (i.e. standard completions which are completely distributive algebraic lattices),
4. Boolean completions.

Moreover, completely distributive completions are described by certain idempotent relations, and the A-completions are shown to be in one-to-one correspondence with the join-dense subsets of Q. If a pseudocomplemented meet-semilattice Q has a Boolean completion ?, then Q must be a Boolean lattice and ? its MacNeille completion.     

Elementary Equivalence of Linear Groups Over Rings with a Finite Number of Central Idempotents and Over Boolean Rings

In the present paper, we start with a criterion of elementary equivalence of linear groups over rings with just a finite number of central idempotents. Then we study elementary equivalence of linear groups over Boolean algebras. We prove that two linear groups over Boolean algebras are elementarily equivalent if and only if their dimensions coincide and these Boolean algebras are elementarily equivalent.     

Complexity of Boolean algebras and their Scott rank

We deal with problems associated with Scott ranks of Boolean algebras. The Scott rank can be treated as some measure of complexity of an algebraic system. Our aim is to propound and justify the procedure which, given any countable Boolean algebra, will allow us to construct a Boolean algebra of a small Scott rank that has the same natural algebraic complexity as has the initial algebra. In particular, we show that the Scott rank does not always serve as a good measure of complexity for the class of Boolean algebras. We also study into the question as to whether or not a Boolean algebra of a big Scott rank can be decomposed into direct summands with intermediate ranks. Examples are furnished in which Boolean algebras have an arbitrarily big Scott rank such that direct summands in them either have a same rank or a fixed small one, and summands of intermediate ranks are altogether missing. This series of examples indicates, in particular, that there may be no nontrivial mutual evaluations for the Scott and Frechet ranks on a class of countable Boolean algebras. Supported by RFFR grant No. 99-01-00485, by a grant for Young Scientists from SO RAN, 1997, and by the Federal Research Program (FRP) “Integration”. Translated fromAlgebra i Logika, Vol. 38, No. 6, pp. 643–666, November–December, 1999.