On semidefinite linear complementarity problems

Given a linear transformation L:? ⁿ →? ⁿ and a matrix Q∈? ⁿ , where ? ⁿ is the space of all symmetric real n×n matrices, we consider the semidefinite linear complementarity problem SDLCP(L,? ⁿ ₊,Q) over the cone ? ⁿ ₊ of symmetric n×n positive semidefinite matrices. For such problems, we introduce the P-property and its variants, Q- and GUS-properties. For a matrix A∈R ^n×n , we consider the linear transformation L _A :? ⁿ →? ⁿ defined by L _A (X):=AX+XA ^T and show that the P- and Q-properties for L _A are equivalent to A being positive stable, i.e., real parts of eigenvalues of A are positive. As a special case of this equivalence, we deduce a theorem of Lyapunov. Received: March 1999 / Accepted: November 1999?Published online April 20, 2000     

bi-strong Smarandache BL-algebras

In this paper, we introduce the notion of bi-Smarandache BL-algebra, bi-weak Smarandache BL-algebra, bi-Q-Smarandache ideal and bi-Q-Smarandache implicative filter, we obtain some related results and construct quotient of bi-Smarandache BL-algebras via MV-algebras (or briefly bi-Smarandache quotient BL-algebra) and prove some theorems. Finally, the notion of bi-strong Smarandache BL-algebra is presented and relationship between bi-strong Smarandache BL-algebra and bi-Smarandache BL-algebra are studied.     

Green functions and eigenfunction expansions for the square of the Laplace–Beltrami operator on plane domains

For a certain class of domains Ω⊂ℂ with smooth boundary and Δtilde;_Ω=w ²Δ the Laplace–Beltrami operator with respect to the Poincaré metric ds ²=w(z)^-2 dz dz on Ω, we (1) show that the Green function for the biharmonic operator Δtilde;_Ω ², with Dirichlet boundary data, is positive on Ω×Ω; and (2) obtain an eigenfunction expansion for the operator Δtilde;_Ω, which reduces to the ordinary non-Euclidean Fourier transform of Helgason for Ω=𝔻 (the unit disc). In both cases the proofs go via uniformization, and in (1) we obtain a Myrberg-like formula for the corresponding Green function. Finally, the latter formula as well as the eigenfunction expansion are worked out more explicitly in the simplest case of Ω an annulus, and a result is established concerning the convergence of the series ∑ _ω∈G (1-|ω0|²) ^s for G the covering group of the uniformization map of Ω and 0<s<1. Received: August 21, 2000?Published online: October 30, 2002 RID="*" ID="*"The first author was supported by GA AV CR grants no. A1019701 and A1019005.     

Implicative hyper <Emphasis Type="Italic">K</Emphasis>-algebras

In this note we first define the notions of (weak, strong) implicative hyper K-algebras. Then we show by examples that these notions are different. After that we state and prove some theorems which determine the relationship between these notions and (weak) hyper K-ideals. Also we obtain some relations between these notions and (weak) implicative hyper K-ideals. Finally, we study the implicative hyper K-algebras of order 3, in particular we obtain a relationship between the positive implicative hyper K-algebras and (weak, strong) implicative hyper K-algebras under a simple condition.     

Hyper‐Archimedean BL‐algebras are MV‐algebras

Generalizations of Boolean elements of a BL‐algebra L are studied. By utilizing the MV‐center MV(L) of L, it is reproved that an element x ∈ L is Boolean iff x ∨ x * = 1 . L is called semi‐Boolean if for all x ∈ L, x * is Boolean. An MV‐algebra L is semi‐Boolean iff L is a Boolean algebra. A BL‐algebra L is semi‐Boolean iff L is an SBL‐algebra. A BL‐algebra L is called hyper‐Archimedean if for all x ∈ L, xⁿ is Boolean for some finite n ≥ 1. It is proved that hyper‐Archimedean BL‐algebras are MV‐algebras. The study has application in mathematical fuzzy logics whose Lindenbaum algebras are MV‐algebras or BL‐algebras. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Local bounded commutative residuated ℓ-monoids

Bounded commutative residuated lattice ordered monoids (Rℓ-monoids) are a common generalization of, e.g., BL-algebras and Heyting algebras. In the paper, the properties of local and perfect bounded commutative Rℓ-monoids are investigated.     

On (∈, ∈ ∨ q)‐fuzzy filters of R0‐algebras

In this paper, we introduce the notions of (∈, ∈ ∨ q)‐fuzzy filters and (∈, ∈ ∨ q)‐fuzzy Boolean (implicative) filters in R₀‐algebras and investigate some of their related properties. Some characterization theorems of these generalized fuzzy filters are derived. In particular, we prove that a fuzzy set in R₀‐algebras is an (∈, ∈ ∨ q)‐fuzzy Boolean filter if and only if it is an (∈, ∈ ∨ q)‐fuzzy implicative filter. Finally, we consider the concepts of implication‐based fuzzy Boolean (implicative) filters of R₀‐algebras (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Modal operators on bounded commutative residuated <Emphasis Type="Italic">ℓ</Emphasis>-monoids

Bounded commutative residuated lattice ordered monoids (Rℓ-monoids) are a common generalization of, e.g., Heyting algebras and BL-algebras, i.e., algebras of intuitionistic logic and basic fuzzy logic, respectively. Modal operators (special cases of closure operators) on Heyting algebras were studied in [MacNAB, D. S.: Modal operators on Heyting algebras, Algebra Universalis 12 (1981), 5–29] and on MV-algebras in [HARLENDEROVá,M.—RACHŮNEK, J.: Modal operators on MV-algebras, Math. Bohem. 131 (2006), 39–48]. In the paper we generalize the notion of a modal operator for general bounded commutative Rℓ-monoids and investigate their properties also for certain derived algebras. The first author was supported by the Council of Czech Government, MSM 6198959214.     

Fuzzy prime Boolean filters and their operations in IMT L-algebras

Some characterizations of fuzzy prime Boolean filters of IMT L-algebras are given. The lattice operations and the order-reversing involution on the set PB(M) of all fuzzy prime Boolean filters of IMT L-algebras are defined. It is showed that the set PB(M) endowed with these operations is a complete quasi-Boolean algebra (a distributive complete lattice with an order-reversing involution). It is derived that the algebra M=F, which is the set of all cosets of F, is isomorphic to the Boolean algebra {0; 1} if F is a fuzzy prime Boolean filter. By introducing an adjoint pair on PB(M), it is proved that the set PB(M) is also a residuated lattice.     

The Frattini Subalgebra of Restricted Lie Superalgebras

In the present paper, we study the Frattini subalgebra of a restricted Lie superalgebra （L, [p]）. We show first that if L = A1 ＋ A2 ＋… ＋An, then Фp（L） = Фp（A1） ＋Фp（A2） ＋…＋Фp（An）, where each Ai is a p-ideal of L. We then obtain two results： F（L） = Ф（L） = J（L） = L if and only if L is nilpotent; Fp（L） and F（L） are nilpotent ideals of L if L is solvable. In addition, necessary and sufficient conditions are found for Фp-free restricted Lie superalgebras. Finally, we discuss the relationships of E-p-restricted Lie superalgebras and E-restricted Lie superalgebras.     

The spectrum of partitions of a Boolean algebra

The main notion dealt with in this article is

On the rank of mixed 0,1 polyhedra

For a polytope in the [0,1] ⁿ cube, Eisenbrand and Schulz showed recently that the maximum Chvátal rank is bounded above by O(n ²logn) and bounded below by (1+ε)n for some ε>0. Chvátal cuts are equivalent to Gomory fractional cuts, which are themselves dominated by Gomory mixed integer cuts. What do these upper and lower bounds become when the rank is defined relative to Gomory mixed integer cuts? An upper bound of n follows from existing results in the literature. In this note, we show that the lower bound is also equal to n. This result still holds for mixed 0,1 polyhedra with n binary variables. Received: March 15, 2001 / Accepted: July 18, 2001?Published online September 17, 2001     

Monadic Bounded Commutative Residuated ℓ-monoids

Bounded commutative residuated ℓ-monoids are a generalization of algebras of propositional logics such as BL-algebras, i.e. algebraic counterparts of the basic fuzzy logic (and hence consequently MV-algebras, i.e. algebras of the Łukasiewicz infinite valued logic) and Heyting algebras, i.e. algebras of the intuitionistic logic. Monadic MV-algebras are an algebraic model of the predicate calculus of the Łukasiewicz infinite valued logic in which only a single individual variable occurs. We introduce and study monadic residuated ℓ-monoids as a generalization of monadic MV-algebras. Jiří Rachůnek was supported by the Council of Czech Goverment MSM 6198959214.     

A fast algorithm for computing minimum 3-way and 4-way cuts

For an edge-weighted graph G with n vertices and m edges, we present a new deterministic algorithm for computing a minimum k-way cut for k=3,4. The algorithm runs in O(n ^k-1 F(n,m))=O(mn ^k log(n ² /m)) time and O(n ²) space for k=3,4, where F(n,m) denotes the time bound required to solve the maximum flow problem in G. The bound for k=3 matches the current best deterministic bound ?(mn ³) for weighted graphs, but improves the bound ?(mn ³) to O(n ² F(n,m))=O(min{mn ^8/3,m ^3/2 n ²}) for unweighted graphs. The bound ?(mn ⁴) for k=4 improves the previous best randomized bound ?(n ⁶) (for m=o(n ²)). The algorithm is then generalized to the problem of finding a minimum 3-way cut in a symmetric submodular system. Received: April 1999 / Accepted: February 2000?Published online August 18, 2000     

Perfect residuated lattice ordered monoids

Bounded Rℓ-monoids form a large subclass of the class of residuated lattices which contains certain of algebras of fuzzy and intuitionistic logics, such as GMV-algebras (= pseudo-MV-algebras), pseudo-BL-algebras and Heyting algebras. Moreover, GMV-algebras and pseudo-BL-algebras can be recognized as special kinds of pseudo-MV-effect algebras and pseudo-weak MV-effect algebras, i.e., as algebras of some quantum logics. In the paper, bipartite, local and perfect Rℓ-monoids are investigated and it is shown that every good perfect Rℓ-monoid has a state (= an analogue of probability measure).     

Prime spectra of non-commutative generalizations of MV-algebras

Non-commutative generalizations of MV-algebras were introduced by G. Georgescu and A. Iorgulesco as well as by the author; the generalizations are equivalent and are called GMV-algebras. We show that GMV-algebras can be considered as special cases of Grishin algebras. As MV-algebras are algebraic models of the Łukasiewicz logic and Grishin algebras have the analogous role for the classical bilinear logic, GMV-algebras correspond to a non-commutative logic between the above logics. Further, by A. Dvurečenskij, any GMV-algebra is isomorphic to an interval of an l-group, which in general is not commutative. This generalizes D. Mundici's representation of MV-algebras by means of intervals of abelian l-groups. In the paper (using this representation) we describe the properties of prime ideal spectra of GMV-algebras and of their factor algebras and ideals and prove that the spectrum of closed ideals of any GMV-algebra is homeomorphic to that of a completely distributive GMV-algebra. Received January 4, 2001; accepted in final form May 2, 2002.     

Global convergence of a class of non-interior point algorithms using Chen-Harker-Kanzow-Smale functions for nonlinear complementarity problems

We propose a class of non-interior point algorithms for solving the complementarity problems(CP): Find a nonnegative pair (x,y)∈ℝ ²ⁿ satisfying y=f(x) and x _i y _i =0 for every i∈{1,2,...,n}, where f is a continuous mapping from ℝ ⁿ to ℝ ⁿ . The algorithms are based on the Chen-Harker-Kanzow-Smale smoothing functions for the CP, and have the following features; (a) it traces a trajectory in ℝ ³ⁿ which consists of solutions of a family of systems of equations with a parameter, (b) it can be started from an arbitrary (not necessarily positive) point in ℝ ²ⁿ in contrast to most of interior-point methods, and (c) its global convergence is ensured for a class of problems including (not strongly) monotone complementarity problems having a feasible interior point. To construct the algorithms, we give a homotopy and show the existence of a trajectory leading to a solution under a relatively mild condition, and propose a class of algorithms involving suitable neighborhoods of the trajectory. We also give a sufficient condition on the neighborhoods for global convergence and two examples satisfying it. Received April 9, 1997 / Revised version received September 2, 1998? Published online May 28, 1999     

On voronoi diagrams in theL p-metric in ℝD

We prove upper bounds on the number ofL _p-spheres passing throughD+1 points in general position in ℝ”, and on the sum of the Betti numbers of the intersection of bisectors in theL _p-metric, wherep is an even positive integer. The bounds found do not depend onp. Our result implies that the complexity of Voronoi diagrams (for point sites in general position) in theL _p-metric is bounded for increasingp. The proof for this upper bound involves the techniques of Milnor [12] and Thom [16] for finding a bound on the sum of the Betti numbers of algebraic varieties, but instead of the usual degree of polynomials we use their additive complexity, and apply results of Benedetti and Risler [2], [13]. Furthermore, we prove that inD dimensions and for evenp the number ofL _p-spheres passing throughD+1 points in general position is odd. In particular, combined with results of [8], [9], our results clarify the structure of Voronoi diagrams based on theL _p-metric (with evenp) in three dimensions. For the proof we use the theory of degree of continuous mappings in ℝ^D, which is a tool widely applied in nonlinear analysis [14]. This work was partially supported by Deutsche Forschungsgemeinschaft, Grant K1 655/2-1. A preliminary version of this paper was presented at the 11th Annual Symposium on Theoretical Aspects of Computer Science, France, 1994.     

On the stability of solutions to quadratic programming problems

We consider the parametric programming problem (Q _p ) of minimizing the quadratic function f(x,p):=x ^T Ax+b ^T x subject to the constraint Cx≤d, where x∈ℝ ⁿ , A∈ℝ ^n×n , b∈ℝ ⁿ , C∈ℝ ^m×n , d∈ℝ ^m , and p:=(A,b,C,d) is the parameter. Here, the matrix A is not assumed to be positive semidefinite. The set of the global minimizers and the set of the local minimizers to (Q _p ) are denoted by M(p) and M ^loc (p), respectively. It is proved that if the point-to-set mapping M ^loc (·) is lower semicontinuous at p then M ^loc (p) is a nonempty set which consists of at most ? _m,n points, where ? _m,n = is the maximal cardinality of the antichains of distinct subsets of {1,2,...,m} which have at most n elements. It is proved also that the lower semicontinuity of M(·) at p implies that M(p) is a singleton. Under some regularity assumption, these necessary conditions become the sufficient ones. Received: November 5, 1997 / Accepted: September 12, 2000?Published online November 17, 2000     

Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems

This note studies _A , a condition number used in the linear programming algorithm of Vavasis and Ye [14] whose running time depends only on the constraint matrix A∈ℝ ^m×n , and (A), a variant of another condition number due to Ye [17] that also arises in complexity analyses of linear programming problems. We provide a new characterization of _A and relate _A and (A). Furthermore, we show that if A is a standard Gaussian matrix, then E(ln _A )=O(min{mlnn,n}). Thus, the expected running time of the Vavasis-Ye algorithm for linear programming problems is bounded by a polynomial in m and n for any right-hand side and objective coefficient vectors when A is randomly generated in this way. As a corollary of the close relation between _A and (A), we show that the same bound holds for E(ln(A)). Received: September 1998 / Accepted: September 2000?Published online January 17, 2001