A las vegas rnc algorithm for maximum matching

Recently two randomized algorithms were discovered that find a maximum matching in an arbitrary graph in polylog time, when run on a parallel random access machine. Both are Monte Carlo algorithms — they have the drawback that with non-zero probability the output is a non-maximum matching. We use the min-max formula for the size of a maximum matching to convert any Monte Carlo maximum matching algorithm into a Las Vegas (error-free) one. The resulting algorithm returns (with high probability) a maximum matching and a certificate proving that the matching is indeed maximum. Research supported by DARPA grant N00039-84-C-0098 and by a US Army Research Office fellowship.     

Fuzzy measures for profit maximization with fuzzy parameters

Profit maximization is an important issue to the firms that pursue the largest economic profit possible. This paper extends the situation from the deterministic to uncertain, where the coefficients are represented by fuzzy numbers. Intuitively, when the problem has fuzzy parameters, the derived profit value should be a fuzzy number as well. The extension principle is utilized to develop a pair of two-level mathematical programs to calculate the upper and lower bounds of the profit value at α-cuts. Following the duality theorem and a variable separation technique, the two-level mathematical programs are transformed into a class of one-level signomial geometric programs to solve. An example is given to illustrate the idea proposed in this paper.     

Families of cuts with the MFMC-property

A family ℱ of cuts of an undirected graphG=(V, E) is known to have the weak MFMC-property if (i) ℱ is the set ofT-cuts for someT⊆V with |T| even, or (ii) ℱ is the set of two-commodity cuts ofG, i.e. cuts separating any two distinguished pairs of vertices ofG, or (iii) ℱ is the set of cuts induced (in a sense) by a ring of subsets of a setT⊆V. In the present work we consider a large class of families of cuts of complete graphs and prove that a family from this class has the MFMC-property if and only if it is one of (i), (ii), (iii).     

The struction of a graph: Application toCN-free graphs

We consider the class of graphs characterized by the forbidden subgraphsC andN:C is the claw (unique graph with degree sequence (3, 1, 1, 1)) andN the net (unique graph with degree sequence (3, 3, 3, 1, 1, 1)). For this class of graphs (calledCN-free) an algorithm is described for determining the stability numberα(G). It is based on a construction associating with anyCN-free graphG anotherCN-free graphG′ such thatα(G′)=α(G)−1. Such a construction reducing the stability number is called a struction. This work was completed while this author was visiting the Dept. of Combinatories and Optimization at the University of Waterloo, Ontario.     

PROPOSITIONAL LOGIC,FRAMES, AND FUZZY ALGEBRA

Abstract

This paper offers a new look at such things as the fuzzy subalgebras and congruences of an algebra, the fuzzy ideals of a ring or a lattice, and similar entities, by exhibiting them as the models, in the chosen frame T of truth values, of naturally corresponding propositional theories. This provides a systematic approach to the study of the partially ordered sets formed by these various entities, and we demonstrate its usefulness by employing it to derive a number of results, some old and some new, concerning these partially ordered sets. In particular, we prove they are complete lattices, algebraic or continuous, depending on whether T is algebraic or continuous, respectively (Proposition 3); they satisfy the same lattice identities for arbitrary T that hold in the case T = 2 (Corollary of Proposition 4); and they are coherent frames for any coherent T whenever this is the case for T = 2 (Proposition 6). In addition we show, generalizing a result by Makamba and Murali [10], that the familiar classical situations where the congruences of an algebra correspond to certain other entities, such as the normal subgroups of a group or the ideals of a ring, extend to the fuzzy case by proving that the corresponding propositional theories are equivalent (Proposition 2). Further, we obtain the result of Gupta and Kantroo [5] that the fuzzy radical ideals of a commutative ring with unit are the meets of fuzzy prime ideals for arbitrary continuous T in place of the unit interval, using basic facts concerning continuous frames (Proposition 7).     

A strongly polynomial minimum cost circulation algorithm

A new algorithm is presented for the minimum cost circulation problem. The algorithm is strongly polynomial, that is, the number of arithmetic operations is polynomial in the number of nodes, and is independent of both costs and capacities.     

Eigenvalues and expanders

Linear expanders have numerous applications to theoretical computer science. Here we show that a regular bipartite graph is an expanderif and only if the second largest eigenvalue of its adjacency matrix is well separated from the first. This result, which has an analytic analogue for Riemannian manifolds enables one to generate expanders randomly and check efficiently their expanding properties. It also supplies an efficient algorithm for approximating the expanding properties of a graph. The exact determination of these properties is known to be coNP-complete. The research was supported by the Weizmann Fellowship for Scientific Research and by Air Force Contract OSR 82-0326.     

On the continuity of residuals of triangular norms

In this work a long-standing problem related to the continuity of R-implications, i.e., implications obtained as the residuum of t-norms, has been solved. A complete characterization of the class of continuous R-implications obtained from any arbitrary t-norm is given. In particular, it is shown that an R-implication I_T is continuous if and only if T is a nilpotent t-norm. Using this result, the exact intersection between the continuous subsets of R-implications and (S,N)-implications has been determined, by showing that the only continuous (S,N)-implication that is also an R-implication obtained from any t-norm, not necessarily left-continuous, is the ?ukasiewicz implication up to an isomorphism.     

A random 1-011-011-01algorithm for depth first search

In this paper we present a fast parallel algorithm for constructing a depth first search tree for an undirected graph. The algorithm is anRNC algorithm, meaning that it is a probabilistic algorithm that runs in polylog time using a polynomial number of processors on aP-RAM. The run time of the algorithm isO(T _MM(n) log³ n), and the number of processors used isP _MM (n) whereT _MM(n) andP _MM(n) are the time and number of processors needed to find a minimum weight perfect matching on ann vertex graph with maximum edge weightn.This research was done while the first author was visiting the Mathematical Research Institute in Berkeley. Research supported in part by NSF grant 8120790.Supported by Air Force Grant AFOSR-85-0203A.     

Minimizing setups in ordered sets of fixed width

A simply polynomial time algorithm is given for computing the setup number, or jump number, of an ordered set with fixed width. This arises as an interesting application of a polynomial time algorithm for solving a more general weighted problem in precedence constrained scheduling.     

Six problems of Gian-Carlo Rota in lattice theory and universal algebra

No Abstract. .The algebraic structure sooner or later comes to dominate, whether or not it is recognized when a subject is born. Algebra dictates the analysis. Gian-Carlo Rota [33]     

Observing,reporting, and deciding in networks of sentences

In prior work [7] we considered networks of agents who have knowledge bases in first order logic, and report facts to their neighbors that are in their common languages and are provable from their knowledge bases, in order to help a decider verify a single sentence. In report complete networks, the signatures of the agents and the links between agents are rich enough to verify any decider?s sentence that can be proved from the combined knowledge base. This paper introduces a more general setting where new observations may be added to knowledge bases and the decider must choose a sentence from a set of alternatives. We consider the question of when it is possible to prepare in advance a finite plan to generate reports within the network. We obtain conditions under which such a plan exists and is guaranteed to produce the right choice under any new observations.     

Compact Hausdorff fuzzy topological spaces are topological

Many examples of compact fuzzy topological spaces which are highly non topological are known [5, 6]. Equally many examples of Hausdorff fuzzy topological spaces which are highly non topological can be given. In this paper we show that the two properties - compact and Hausdorff - combined however necessarily imply that the fuzzy topological space is topological. This at once solves some open questions with regard to the compactification of fuzzy topological spaces [8]. It also emphasizes once more the particular role played by compact Hausdorff topological spaces not only in the category of topological spaces but even in the category of fuzzy topological spaces.     

A restricted computation model on Scott domains and its partial primitive recursive functionals

The paper builds on both a simply typed term system and a computation model on Scott domains via so-called parallel typed while programs (PTWP). The former provides a notion of partial primitive recursive functional on Scott domains supporting a suitable concept of parallelism. Computability on Scott domains seems to entail that Kleene's schema of higher type simultaneous course-of-values recursion (scvr) is not reducible to partial primitive recursion. So extensions and PTWP are studied that are closed under scvr. The twist are certain type 1 G?del recursors for simultaneous partial primitive recursion. Formally, denotes a function , however, is modelled such that is finite, or in other words, a partial sequence. As for PTWP, the concept of type writable variables is introduced, providing the possibility of creating and manipulating partial sequences. It is shown that the PTWP-computable functionals coincide with those definable in plus a constant for sequential minimisation. In particular, the functionals definable in denoted can be characterised by a subclass of PTWP-computable functionals denoted . Moreover, hierarchies of strictly increasing classes in the style of Heinermann and complexity classes are introduced such that . These results extend those for and PTWP [Nig94]. Finally, scvr is employed to define for each type the enumeration functional of all finite elements of . Received January 30, 1996     

Reducing belief simpliciter to degrees of belief

Is it possible to give an explicit definition of belief (simpliciter) in terms of subjective probability, such that believed propositions are guaranteed to have a sufficiently high probability, and yet it is neither the case that belief is stripped of any of its usual logical properties, nor is it the case that believed propositions are bound to have probability 1? We prove the answer is ‘yes’, and that given some plausible logical postulates on belief that involve a contextual “cautiousness” threshold, there is but one way of determining the extension of the concept of belief that does the job. The qualitative concept of belief is not to be eliminated from scientific or philosophical discourse, rather, by reducing qualitative belief to assignments of resiliently high degrees of belief and a “cautiousness” threshold, qualitative and quantitative belief turn out to be governed by one unified theory that offers the prospects of a huge range of applications. Within that theory, logic and probability theory are not opposed to each other but go hand in hand.     

An Ω(n 5/4) lower bound on the randomized complexity of graph properties

A decision tree algorithm determines whether an input graph withn nodes has a property by examining the entries of the graph's adjacency matrix and branching according to the information already gained. All graph properties which are monotone (not destroyed by the addition of edges) and nontrivial (holds for somes but not all graphs) have been shown to require (n ²) queries in the worst case.In this paper, we investigate the power of randomness in recognizing these properties by considering randomized decision tree algorithms in which coins may be flipped to determine the next entry to be examined. The complexity of a randomized algorithm is the expected number of entries that are examined in the worst case. The randomized complexity of a property is the minimum complexity of any randomized decision tree algorithm which computes the property. We improve Yao's lower bound on the randomized complexity of any nontrivial monotone graph property from (n log^1/12 n) to (n ^5/4).     

The monotone circuit complexity of boolean functions

Recently, Razborov obtained superpolynomial lower bounds for monotone circuits that cliques in graphs. In particular, Razborov showed that detecting cliques of sizes in a graphm vertices requires monotone circuits of size Ω(m ^s /(logm)^2s ) for fixeds, and sizem ^Ω(logm) form/4]. In this paper we modify the arguments of Razborov to obtain exponential lower bounds for circuits. In particular, detecting cliques of size (1/4) (m/logm)^2/3 requires monotone circuits exp (Ω((m/logm)^1/3)). For fixeds, any monotone circuit that detects cliques of sizes requiresm) ^s ) AND gates. We show that even a very rough approximation of the maximum clique of a graph requires superpolynomial size monotone circuits, and give lower bounds for some Boolean functions. Our best lower bound for an NP function ofn variables is exp (Ω(n ^1/4 · (logn)^1/2)), improving a recent result of exp (Ω(n ^1/8-ε)) due to Andreev. First author supported in part by Allon Fellowship, by Bat Sheva de-Rotschild Foundation by the Fund for basic research administered by the Israel Academy of Sciences. Second author supported in part by a National Science Foundation Graduate Fellowship.     

How to draw a planar graph on a grid

Answering a question of Rosenstiehl and Tarjan, we show that every plane graph withn vertices has a Fáry embedding (i.e., straight-line embedding) on the 2n–4 byn–2 grid and provide anO(n) space,O(n logn) time algorithm to effect this embedding. The grid size is asymptotically optimal and it had been previously unknown whether one can always find a polynomial sized grid to support such an embedding. On the other hand we show that any setF, which can support a Fáry embedding of every planar graph of sizen, has cardinality at leastn+(1–o(1))n which settles a problem of Mohar.Supported in part by P. R. C. Mathematiques et Informatique.Supported in part by HSF grant 1814.Part of the work on this paper was done while this author was on sabbatical leave at école Normal Supérieure and école des Hautes études en Sciences Sociales; supported in part by NSF grant DMS-850 1947.     

Hidden Markov Models Training by a Particle Swarm Optimization Algorithm

In this work we consider the problem of Hidden Markov Models (HMM) training. This problem can be considered as a global optimization problem and we focus our study on the Particle Swarm Optimization (PSO) algorithm. To take advantage of the search strategy adopted by PSO, we need to modify the HMM's search space. Moreover, we introduce a local search technique from the field of HMMs and that is known as the Baum–Welch algorithm. A parameter study is then presented to evaluate the importance of several parameters of PSO on artificial data and natural data extracted from images.