Recognizing Decomposition of a Partial Boolean Function

A hard combinatorial problem is investigated which has useful application in design of discrete devices: the two-block decomposition of a partial Boolean function. The key task is regarded: finding such a weak partition on the set of arguments, at which the considered function can be decomposed. Solving that task is essentially speeded up by the way of preliminary discovering traces of the sought-for partition. Efficient combinatorial operations are used by that, based on parallel execution of operations above adjacent units in the Boolean space.

Essential Arity Gap of Boolean Functions

In this paper we investigate the Boolean functions with maximum essential arity gap. Additionally we propose a simpler proof of an important theorem proved by M. Couceiro and E. Lehtonen in [3]. They use Zhegalkin’s polynomials as normal forms for Boolean functions and describe the functions with essential arity gap equals 2. We use to instead Full Conjunctive Normal Forms of these polynomials which allows us to simplify the proofs and to obtain several combinatorial results concerning the Boolean functions with a given arity gap. The Full Conjunctive Normal Forms are also sum of conjunctions, in which all variables occur.

On the Hyperbolicity Domain of the Polynomial x^n + a1x^(n-1) + 1/4+ an

∗ Partially supported by INTAS grant 97-1644

Boolean Rings that are Baire Spaces

∗ The present article was originally submitted for the second volume of Murcia Seminar on Functional Analysis (1989). Unfortunately it has been not possible to continue with Murcia Seminar publication anymore. For historical reasons the present vesion correspond with the original one.

Weak Polynomial Identities for M1,1(E)

* Partially supported by Universita` di Bari: progetto “Strutture algebriche, geometriche e descrizione degli invarianti ad esse associate”.

Polynomial Automorphisms Over Finite Fields

It is shown that the invertible polynomial maps over a finite field Fq , if looked at as bijections Fn,q −→ Fn,q , give all possible bijections in the case q = 2, or q = p^r where p > 2. In the case q = 2^r where r > 1 it is shown that the tame subgroup of the invertible polynomial maps gives only the even bijections, i.e. only half the bijections. As a consequence it is shown that a set S ⊂ Fn,q can be a zero set of a coordinate if and only if #S = q^(n−1).

Dubrovin Type Equations for Completely Integrable Systems Associated with a Polynomial Pencil

Dubrovin type equations for the N -gap solution of a completely integrable system associated with a polynomial pencil is constructed and then integrated to a system of functional equations. The approach used to derive those results is a generalization of the familiar process of finding the 1-soliton (1-gap) solution by integrating the ODE obtained from the soliton equation via the substitution u = u(x + λt).

Quadratic Mean Radius of a Polynomial in C(Z)

* Dedicated to the memory of Prof. N. Obreshkoff

Decomposition of Boolean Functions – Recognizing a Good Solution by Traces

The problem of sequent two-block decomposition of a Boolean function is regarded in case when a good solution does exist. The problem consists mainly in finding an appropriate weak partition on the set of arguments of the considered Boolean function, which should be decomposable at that partition. A new fast heuristic combinatorial algorithm is offered for solving this task. At first the randomized search for traces of such a partition is fulfilled. The recognized traces are represented by some "triads" - the simplest weak partitions corresponding to non-trivial decompositions. After that the whole sought-for partition is restored from the discovered trace by building a track initialized by the trace and leading to the solution. The results of computer experiments testify the high practical efficiency of the algorithm.

Implementation of a Heuristic Method of Decomposition of Partial Boolean Functions

An original heuristic algorithm of sequential two-block decomposition of partial Boolean functions is researched. The key combinatorial task is considered: finding of suitable partition on the set of arguments, i. e. such one, on which the function is separable. The search for suitable partition is essentially accelerated by preliminary detection of its traces. Within the framework of the experimental system the efficiency of the algorithm is evaluated, the boundaries of its practical application are determined.

Polynomial Expansions for Solutions of Higher-Order Bessel Heat Equation in Quantum Calculus

Mathematics Subject Class.: 33C10,33D60,26D15,33D05,33D15,33D90

The Eccentric Connectivity Polynomial of some Graph Operations

The eccentric connectivity index of a graph G, ξ^C, was proposed by Sharma, Goswami and Madan. It is defined as ξ^C(G) = ∑ u ∈ V(G) degG(u)εG(u), where degG(u) denotes the degree of the vertex x in G and εG(u) = Max{d(u, x) | x ∈ V (G)}. The eccentric connectivity polynomial is a polynomial version of this topological index. In this paper, exact formulas for the eccentric connectivity polynomial of Cartesian product, symmetric difference, disjunction and join of graphs are presented.

On Arrangements of Real Roots of a Real Polynomial and Its Derivatives

2000 Mathematics Subject Classification: 12D10.

Z2-Graded Polynomial Identities for Superalgebras of Block-Triangular Matrices

000 Mathematics Subject Classification: Primary 16R50, Secondary 16W55.

On the Factorization of the Poincaré Polynomial: A Survey

2000 Mathematics Subject Classification: 13P05, 14M15, 14M17, 14L30.