Nombre moyen de majorants d'une fonction booléenne incomplète Remarques concernant le nombre moyen de monômes premiers

The preliminary computation of the «majorants» enables the determination of the minimal or quasi-minimal disjunctive irredundant forms of an incompletely specified function [3]. In practical cases, the search algorithm for the disjunctive irredundant forms is applicable only if the number of «majorants» is not too large. In this paper formulas are derived to determine the average value of this number. Then the computation of the average number of prime implicants, already given byMileto andPutzolu [4], is rederived in a new form. The result is used to built functions having a great number of prime implicants and yields, for a function ofn variables, a lower bound of the maximal number of prime implicants.     

Simplification of fuzzy switching functions

This paper is concerned with the study of simplification of fuzzy switching functions. A novel algorithm for generating all fuzzy prime implicants is introduced, followed by a new method of simplification of fuzzy switching functions. This algorithm is then reduced to a simple algorithm that produces only those fuzzy prime implicants that are essential. There areonly two other valid techniques for the minimization of fuzzy switching functions in the literature,^(1,2) and those methods are not very suitable for computerized application. Thus, the principal advantages of this technique are the new concept of direct simplification via essential fuzzy prime implicants (without generation of all of the fuzzy prime implicants), and the fact that the algorithm is the first one to be suitable for efficient computer implementation.On leave from the Computer Science Department, New Mexico Institute of Mining and Technology, Socorro, New Mexico.     

Decomposition of graphs and monotone formula size of homogeneous functions

Summary We show that every graph on n nodes can be partitioned by a number of complete bipartite graphs with O(n ²/log n) nodes with no edge belonging to two of them. Since each partition corresponds directly to a monotone formula for the associated quadratic function we obtain an upper bound for the monotone formula size of quadratic functions. Our method extends to uniform hypergraphs with fixed range and thus to homogeneous functions with fixed length of prime implicants. Finally we give an example of a quadratic function where each monotone formula built from arbitrary partitions of the graph (double edges allowed) is not optimal. That means we disprove the single-level-conjecture for formulae.     

Decompositions of four variable Boolean functions

All the decompositions of a Boolean function of four variables can be determined directly from its prime implicants if it is decomposable with one free variable. Decompositions of functions of three variables can be obtained from the column ratio of the variables.     

Karnaugh map analysis and synthesis of threshold functions

A unate function can easily be identified on a Karnaugh map from the well-known property that it consists only of essential prime implicants which intersect at a common implicant. The additional property that the plot of a unate function F(x₁ ?x_n ) on a Karnaugh map should possess in order that F may also be 1-realizable (n≤6) has been found. It has been shown that the 1-realizability of a unate function F corresponds to the ‘ compactness ’ of the plot of F. No resort to the inequalities is made, and no pre-processing such as positivizing and ordering of the given function is required.     

Useless prime implicants of incompletely specified multiple-output switching functions

In the process of finding a minimal sum representation for an incompletely specified multiple-output switching function, there often occur certain types of prime implicants, referred to as useless, which can be discarded because of the presence of the don't-cares. This paper presents a correction to the definition of useless given by Tison and extends the definition to other notations. A procedure for removing useless prime implicants quickly is presented for the case when multiple-output prime implicants are derived from minterms. The deletion of useless prime implicants can, in many cases, speed up any procedure for finding a minimal sum that begins with the multiple-output prime implicants in both hand calculation and in computer implementation.This work was supported in part by the National Science Foundation under Grant No. MCS-77-09744.     

An efficient variable partitioning approach for functional decomposition of circuits

Functional decomposition is a process of splitting a complex circuit into smaller sub-circuits. There exist two major strategies in decomposition, namely, serial and parallel decomposition. In serial decomposition the problem the complex function represented as a truth table with support set variables and partitioned into free and bout set variables. The minterms corresponding to the bound set variables are represented as an equivalent function called the predecessor function. Equivalent minterms of the bound set variables are assigned an output code. The assigned output codes and the free set variable minterms are represented as the successor function. Serial decomposition is further categorized into disjoint and non-disjoint decomposition, when the free and bound set variables are disjoint and non-disjoint respectively. This paper deals with the problem of determining the set of best free and bound variables (variable partitioning problem) for disjoint serial decomposition. Variable partitioning is the first step in decomposition process. An efficient variable partition algorithm is one that determines the set of all free and bound set variables that satisfy the decomposition theorem in minimal time and by exploring the search space effectively. This will allow the decomposition algorithm to determine the best variable partition of a function that results in smaller decomposed functions and with maximum number of do not cares in these functions. Classical approaches to determine the best free and bound set use exhaustive search methods. The time and memory requirements for such approaches are exponential or super exponential.A novel heuristic search approach is proposed to determine the set of good variable partitions in minimal time by minimally exploring the search space. There are two heuristics employed in the proposed search approach, (1) r-admissibility based heuristic or pruned breadth first search (PBFS) approach and (2) Information relation based heuristic or improved pruned breadth first search (IPBFS) approach. The r-admissibility based heuristic is based on r-partition characteristics of the free and bound set variables. The information relation and measure based heuristic is based on information relationship of free and bound set variables that are expressed as r-partition heuristics. The proposed variable partition search approach has been successfully implemented and test with MCNC and Espresso benchmarks and the results indicate that the time complexity is comparable to r-admissible heuristic algorithm and the quality of solution is comparable to exact variable partitioning algorithm. A comparison of PBFS and IPBFS heuristics for certain benchmarks are also discussed in this paper.     

Two-Level Multiple-Output Logic Minimization Using A Single Function

A new method for obtaining a two-level collective minimal cover for a set of incompletely-specified switching functions $S=\{f_1,f_2,\ldots,f_n\}$ is presented. The method relies on the introduction of a single auxiliary function F whose subfunctions (restrictions) with respect to some additional auxiliary variables $y_1,y_2,\ldots,y_{n-1}$ are certain members of S . The complete sum of F has full information on the multiple-output prime implicants (MOPIs) of the set of functions S . A particularly constrained minimal cover for F contains only labeled versions of some paramount prime implicants (PPIs) of S and can be used to construct a multiple-output minimal cover for S . The present method can proceed by map, algebraic or tabular techniques, though only the map version is presented herein. This version employs a single map whose construction avoids the ANDing operations needed in the classical method, and whose size is almost one half the total size of the maps used by the classical method, and whose entries can be variable as well as constant. The minimization process is a direct two-step technique that avoids constructing the set of all PPIs as it produces only these PPIs needed in the minimal cover. Details of the method are carefully explained and illustrated via a typical example.     

A note on the simplification of fuzzy switching functions

This note is concerned with the modification of the definition of fuzzy consensus. The modified version is used to find the set of all fuzzy prime implicants of a fuzzy switching function as defined previously. The fuzzy algebra used to derive these functions satisfies the set of axioms of a distributive lattice with unique identities under the operators of maximum and minimum as described earlier.     

Bases for closed sets of implicants and implicates in temporal logic

Prime implicates and implicants are used in several areas of Artificial Intelligence. However, their calculation is not always an easy task. Nevertheless, it is important to remark the distinction between (i) computing the prime implicates and implicants and (ii) using the information they contain. In this paper, we present a way in which (ii) can be done without actually doing (i) by limiting prime implicants and implicates management to unitary implicants and implicates. Besides, we outline how the use of this technique is particularly relevant in the field of automated deduction in temporal logics. The information contained in temporal implicates and implicants can be used to design transformations of temporal formulae able to increase the power of automated deduction techniques for temporal logics. Particularly, we have developed a theory for unitary temporal implicates and implicants that can be more efficiently computed than prime implicants, while still providing the information needed to design this kind of transformations. The theory we have developed in this paper is easily extensible to cover different types of temporal logics, and is integrable in different automated deduction methods for these temporal logics. Received: 14 May 1999 / 22 March 2002     

AnO(n 2) incremental algorithm for modular decomposition of graphs and 2-structures

This paper gives anO(n ²) incremental algorithm for computing the modular decomposition of 2-structures [1], [2]. A 2-structure is a type of edge-colored graph, and its modular decomposition is also known as the prime tree family. Modular decomposition of 2-structures arises in the study of relational systems. The modular decomposition of undirected graphs and digraphs is a special case, and has applications in a number of combinatorial optimization problems. This algorithm generalizes elements of a previousO(n ²) algorithm of Muller and Spinrad [3] for the decomposition of undirected graphs. However, Muller and Spinrad's algorithm employs a sophisticated data structure that impedes its generalization to digraphs and 2-structures, and limits its practical use. We replace this data structure with a scheme that labels each edge with at most one node, thereby obtaining an algorithm that is both practical and general to 2-structures.     

Analysis of a simple factorization algorithm

The probability that the k^th largest prime factor of a number n is at most n^x is shown to approach a limit F_k(x) as n → ∞. Several interesting properties of F_k(x) are explored, and numerical tables are given. These results are applied to the analysis of an algorithm commonly used to find all prime factors of a given number. The average number of digits in the k^th largest prime factor of a random m-digit number is shown to be asymptotically equivalent to the average length of the k^th longest cycle in a permutation on m objects.     

Rules to find the partition of<Emphasis Type="Italic">n</Emphasis> with maximum l. c. m.

One look for the optimal decomposition of the positive integern such that the l. c. m. of its members is a maximum. It is showed that a good lower bound for such function ofn is\(\mathop \prod \limits_r^k P_r \) whereP _r is ther-th prime number, and\(\mathop \sum \limits_r^k P_r \leqslant n\). Rules are given to improve the lower bound until to the exact valnes for anyn≤200 and for many other greater valnes ofn. Asymptotic bounds are finally established. The results allow us to find the maximum reverberation length, realizable by an autonomous circeuit whose boolean functions depend on only one variable.     

Finding bipartite subgraphs efficiently

Polynomial algorithms are given for the following two problems:

•

given a graph with n vertices and m edges, find a complete balanced bipartite subgraph Kq,q with ,

•

given a graph with n vertices, find a decomposition of its edges into complete balanced bipartite graphs having altogether O(n²/lnn) vertices.

The first algorithm can be modified to have running time linear in m and find a Kq^′,q^′ with q^′=⌊q/5⌋. Previous proofs of the existence of such objects, due to K?vári, Sós and Turán (1954) [10], Chung, Erd?s and Spencer (1983) [5], Bublitz (1986) [4] and Tuza (1984) [13] were non-constructive.     

Analysis and design of associative memories based on recurrent neural network with discontinuous activation functions

This paper considers a recurrent neural network (RNN) with a special class of discontinuous activation function which is piecewise constants in the state space. One sufficient condition is established to ensure that the novel recurrent neural networks can have (4k−1)ⁿ locally exponential stable equilibrium points. Such RNN is suitable for synthesizing high-capacity associative memories. The design procedure is presented with the method of singular value decomposition. Finally, the validity and performance of the results are illustrated by use of two numerical examples.     

Hashing via finite field

In order to produce full length probe sequences, the table size m for many existing open addressing hash functions, for example, the widely used double hashing, must be prime, i.e., m = p where p is prime. In this paper, we propose a new and efficient open addressing technique, called hashing via finite field, to construct a new class of hash functions with table size m = pⁿ, where p is prime and n ? 1. It is clear that it includes prime m as a special case when n = 1. We show that the new class of hash functions constructed via finite field produces full length probe sequences on all table elements. Also, some theoretic analysis is provided along with concrete examples.     

Direct and indirect algorithms for on-line learning of disjunctions

It is easy to design on-line learning algorithms for learning k out of n variable monotone disjunctions by simply keeping one weight per disjunction. Such algorithms use roughly O(n^k) weights which can be prohibitively expensive. Surprisingly, algorithms like Winnow require only n weights (one per variable or attribute) and the mistake bound of these algorithms is not too much worse than the mistake bound of the more costly algorithms. The purpose of this paper is to investigate how exponentially many weights can be collapsed into only O(n) weights. In particular, we consider probabilistic assumptions that enable the Bayes optimal algorithm's posterior over the disjunctions to be encoded with only O(n) weights. This results in a new O(n) algorithm for learning disjunctions which is related to the Bylander's BEG algorithm originally introduced for linear regression. Besides providing a Bayesian interpretation for this new algorithm, we are also able to obtain mistake bounds for the noise free case resembling those that have been derived for the Winnow algorithm. The same techniques used to derive this new algorithm also provide a Bayesian interpretation for a normalized version of Winnow.     

Simplification of Switching Functions Involving a very Large Number of ‘Don't Care’ States†

A method of simplification of switching functions involving a very large number of ‘ don't care’ states is suggested in the present paper. First a tabular technique is suggested which generates all the prime implicants starting from the maxterm type expressions of switching functions, avoiding generation of the prime implicants formed of ‘don't care’ states only. The technique presented is simple and iterative. Next it is suggested how the knowledge of the sets of prime implicants thus obtained can be utilized for finding minimal or other irredundant sums of switching functions.     

Time-slot assignment for TDMA-systems

In satellite communication as in other technical systems using the TDMA-technique (time division multiple access) the problem arises to decompose a given (n×n)-matrix in a weighted sum of permutation matrices such that the sum of the weights becomes minimal. We show at first that an optimal solution of this problem can be obtained inO(n ⁴)-time using at mostO(n ²) different permutation matrices. Thereafter we discuss shortly the decomposition inO(n) different matrices which turns out to be NP-hard. Moreover it is shown that an optimal decomposition using a class of 2n permutation matrices which are fixed in advance can be obtained by solving a classical assignment problem. This latter problem can be generalized by taking arbitrary Boolean matrices. The corresponding decomposition problem can be transformed to a special max flow min cost network flow problem, and is thus soluble by a genuinely polynomial algorithm.