伪BL-代数的犹豫模糊滤子

提出了伪BL-代数的犹豫模糊滤子的概念，给出它的几个等价刻画，并研究了它的一些性质。进一步，引入了伪BL-代数的几种犹豫模糊滤子，如犹豫模糊Boolean滤子、犹豫模糊正规滤子、犹豫模糊超滤子和犹豫模糊固执滤子，讨论了它们的一些刻画，给出了其间的一些关系。通过研究伪BL-代数中犹豫模糊Boolean滤子与犹豫模糊正规滤子的关系，解决了伪BL-代数中是否每个Boolean滤子都是正规滤子这样一个开问题。     

State filters on fuzzy structures with internal states

The aim of this paper is the study of some properties of the state filters of a state pseudo BL-algebra \(\left( A,\sigma \right) \) and also some properties of a state pseudo BL-algebra. By introducing the concepts of simple, semisimple and local state pseudo BL-algebra relative to its state filters set, we present some characterizations of a simple, semisimple and local state pseudo BL-algebras. Also, we adjust a result from universal algebra (Chinese remainder theorem) and, by introducing the concept of a primary state filter on a state BL-algebra, we present a characterization of a local state BL-algebra. We introduce the notion of extended state filter of a state filter associated to a subset of a state pseudo BL-algebra.     

Functions represented by BL-algebra formulas: characterization and approximate representation

The paper is a contribution to the study of functional systems of BL-algebras on [0,1] extended by constants from [0,1] and suprema and infima over (infinite) sets of different instances of the same formula. We prove that the class of functions which are represented by thus specified formulas coincides with the class of extensional functions. Moreover, the class of these functions coincides with the class of Lipschitz continuous functions in the case of BL-algebra whose t-norm has a continuous additive generator. We also consider an approximate representation of functions, represented by BL-formulas with a possibly infinite length, by discrete normal forms and suggest an algorithmic approach to its construction. This paper has been partially supported by grant IAA1187301 of the GA AV ČR.     

State BL-algebras

The concept of a state MV-algebra was firstly introduced by Flaminio and Montagna (An algebraic approach to states on MV-algebras. In: Novák V (ed) Fuzzy logic 2, proceedings of the 5th EUSFLAT conference, September 11–14, Ostrava, vol II, pp 201–206, 2007; Int J Approx Reason 50:138–152, 2009) as an MV-algebra with internal state as a unary operation. Di Nola and Dvurečenskij (Ann Pure Appl Logic 161:161–173, 2009a; Math Slovaca 59:517–534, 2009b) gave a stronger version of a state MV-algebra. In the present paper, we introduce the notion of a state BL-algebra, or more precisely, a BL-algebra with internal state. We present different types of state BL-algebras, like strong state BL-algebras and state-morphism BL-algebras, and we study some classes of state BL-algebras. In addition, we give a sample of important examples of state BL-algebras and present some open problems.     

BL-algebras and effect algebras

Although the notions of a BL-algebra and of an effect algebra arose in rather different contextes, both types of algebras have certain structural properties in common. To clarify their mutual relation, we introduce weak effect algebras, which generalize effect algebras in that the order is no longer necessarily determined by the partial addition. A subclass of the weak effect algebras is shown to be identifiable with the BL-algebras. Moreover, weak D-posets are defined, being based on a partial difference rather than a partial addition. They are equivalent to weak effect algebras. Finally, it is seen to which subclasses of the weak effect algebras certain subclasses of the BL-algebras, namely the MV-, product, and Gödel algebras, correspond.     

Bosbach states on fuzzy structures

Pseudo-BL algebras are non-commutative fuzzy structures which generalize BL-algebras and pseudo-MV algebras. In this paper we study the states on a pseudo-BL algebra. This concept is obtained by using the Bosbach condition for each of the two implications of a pseudo BL-algebra. We also propose a notion of conditional state for BL-algebras.The author would like to thank Laureiu Leutean for his valuable suggestions in obtaining the final version of the paper.     

Basic fuzzy logic and BL-algebras

 The many-valued propositional logic BL (basic fuzzy logic) is investigated. It is known to be complete for tautologies over BL-algebras (particular residuated lattices). Each continuous t-norm on [0,1] determines a BL-algebra; such algebras are called t-algebras. Two additional axioms B1, B2 are found such that BL+(B1,B2) is complete for tautologies over t-algebras. It remains open whether B1, B2 are provable in BL.     

Extremal states on bounded residuated \ell-monoids with general comparability

Bounded residuated lattice ordered monoids (RlR\ell-monoids) are a common generalization of pseudo-BLBL-algebras and Heyting algebras, i.e. algebras of the non-commutative basic fuzzy logic (and consequently of the basic fuzzy logic, the Łukasiewicz logic and the non-commutative Łukasiewicz logic) and the intuitionistic logic, respectively. We investigate bounded RlR\ell-monoids satisfying the general comparability condition in connection with their states (analogues of probability measures). It is shown that if an extremal state on Boolean elements fulfils a simple condition, then it can be uniquely extended to an extremal state on the RlR\ell-monoid, and that if every extremal state satisfies this condition, then the RlR\ell-monoid is a pseudo-BLBL-algebra.     

On very true operators on pocrims

Hájek introduced the logic enriching the logic BL by a unary connective vt which is a formalization of Zadeh’s fuzzy truth value “very true”. algebras, i.e., BL-algebras with unary operations, called vt-operators, which are among others subdiagonal, are an algebraic counterpart of Partially ordered commutative integral residuated monoids (pocrims) are common generalizations of both BL-algebras and Heyting algebras. The aim of our paper is to introduce and study algebraic properties of pocrims endowed by “very-true” and “very-false”-like operators. Research is supported by the Research and Development Council of Czech Government via project MSN 6198959214.     

Bounded commutative residuated ℓ-monoids with general comparability and states

Bounded commutative Rℓ-monoids are a generalization of MV-algebras as well as of BL-algebras. For such monoids the authors in [DvRa] introduced states, analogues of probability measures. We study Boolean elements and introduce the general comparability property. It entails that the monoids with the property are BL-algebras, and extremal states on Boolean elements can be uniquely extended to extremal states on the monoids. Moreover, the hull-kernel topology of maximal filters is totally disconnected.     

On two versions of the Loomis–Sikorski Theorem for algebraic structures

We present two versions of the Loomis–Sikorski Theorem, one for monotone σ-complete generalized pseudo effect algebras with strong unit satisfying a kind of the Riesz decomposition property. The second one is for Dedekind σ-complete positive pseudo Vitali spaces with strong unit. For any case we can find an appropriate system of nonnegative bounded functions forming an algebra of the given type with the operations defined by points that maps epimorphically onto the algebra. The paper has been supported by the Center of Excellence SAS—Physics of Information—I/2/2005, the grant VEGA No. 2/6088/26 SAV, the Slovak Research and Development Agency under the contract No. APVV-0071-06, Slovak-Italian Project No. 15:“Algebraic and logical systems of soft computing”, and MURST, project “Analisi Reale”.     

On pseudo BL-algebras with internal state

The scope of this paper is to put in evidence some characteristics and properties of the operations with state filters of a pseudo BL-algebra with internal state. I define the concepts of maximal and prime state filter of a state pseudo BL-algebra, I characterize a maximal state filter and I prove a Prime state filter theorem. Also, I characterize the state-filters algebra of a state pseudo BL-algebra.     

The Bit Complexity of Distributed Sorting

We study the bit complexity of the sorting problem for asynchronous distributed systems. We show that for every network with a tree topology T, every sorting algorithm must send at least bits in the worst case, where is the set of possible initial values, and Δ _T is the sum of distances from all the vertices to a median of the tree. In addition, we present an algorithm that sends at most bits for such trees. These bounds are tight if either L=Ω(N ^1+ε ) or Δ _T =Ω(N ² ). We also present results regarding average distributions. These results suggest that sorting is an inherently nondistributive problem, since it requires an amount of information transfer that is equal to the concentration of all the data in a single processor, which then distributes the final results to the whole network. The importance of bit complexity—as opposed to message complexity—stems also from the fact that, in the lower bound discussion, no assumptions are made as to the nature of the algorithm. Received May 2, 1994; revised December 22, 1995.     

A new problem for rule following

Wittgenstein saw a problem with the idea that ‘rule following’ is a transparent process. Here I present an additional problem, based on recent ideas about non-Turing computing. I show that even the simplest algorithm—Frege’s successor function, i.e. counting—cannot by itself determine the ‘output’. Specification of a computing machine is also required.     

Optimization Algorithms on Subspaces: Revisiting Missing Data Problem in Low-Rank Matrix

Low-rank matrix approximation has applications in many fields, such as 3D reconstruction from an image sequence and 2D filter design. In this paper, one issue with low-rank matrix approximation is re-investigated: the missing data problem. Much effort was devoted to this problem, and the Wiberg algorithm or the damped Newton algorithm were recommended in previous studies. However, the Wiberg or damped Newton algorithms do not suit for large (especially “long”) matrices, because one needs to solve a large linear system in every iteration. In this paper, we revitalize the usage of the Levenberg-Marquardt algorithm for solving the missing data problem, by utilizing the property that low-rank approximation is a minimization problem on subspaces. In two proposed implementations of the Levenberg-Marquardt algorithm, one only needs to solve a much smaller linear system in every iteration, especially for “long” matrices. Simulations and experiments on real data show the superiority of the proposed algorithms. Though the proposed algorithms achieve a high success rate in estimating the optimal solution by random initialization, as illustrated by real examples; it still remains an open issue how to properly do the initialization in a severe situation (that is, a large amount of data is missing and with high-level noise).     

Optimization Problems Related to Zigzag Pocket Machining

A fundamental problem of manufacturing is to produce mechanical parts from billets by clearing areas within specified boundaries from the material. Based on a graph-theoretical formulation, the algorithmic handling of one particular machining problem—``zigzag pocket machining'—is investigated. We present a linear-time algorithm that ensures that every region of the pocket is machined exactly once, while attempting to minimize the number of tool retractions required. This problem is shown to be -hard for pockets with holes. Our algorithm is provably good in the sense that the machining path generated for a pocket with h holes requires at most 5 . . . OPT + 6 . . . h retractions, where OPT is the (unknown) minimum number of retractions required by any algorithm. The algorithm has been implemented, and practical tests for pockets without holes suggest that one can expect an approximation factor of about 1.5 for practical examples, rather than the factor 5 as proved by our analysis. Received July 3, 1997; revised September 7, 1997.     

An Efficient Algorithm for Solving Pseudo Clique Enumeration Problem

The problem of finding dense structures in a given graph is quite basic in informatics including data mining and data engineering. Clique is a popular model to represent dense structures, and widely used because of its simplicity and ease in handling. Pseudo cliques are natural extension of cliques which are subgraphs obtained by removing small number of edges from cliques. We here define a pseudo clique by a subgraph such that the ratio of the number of its edges compared to that of the clique with the same number of vertices is no less than a given threshold value. In this paper, we address the problem of enumerating all pseudo cliques for a given graph and a threshold value. We first show that it seems to be difficult to obtain polynomial time algorithms using straightforward divide and conquer approaches. Then, we propose a polynomial time, polynomial delay in precise, algorithm based on reverse search. The time complexity for each pseudo clique is O(Δlog |V|+min {Δ ²,|V|+|E|}). Computational experiments show the efficiency of our algorithm for both randomly generated graphs and practical graphs.     

New quadratic models for the maximum weighted cut problem

New quadratic models are proposed to improve the upper-bound estimates in the maximum weighted cut problem. They are found by two original methods for deriving redundant quadratic constraints. A well-known linear model is shown to follow from the models proposed. Recommendations on how to develop its strengthened analogs are given. This study is partially sponsored from the grant UM2-2574-KV-03 (CRDF Cooperative Grants Program). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 63—75, January–February 2006.     

Process industry scheduling optimization using genetic algorithm and mathematical programming

This article addresses the problem of scheduling in oil refineries. The problem consists of a multi-product plant scheduling, with two serial machine stages—a mixer and a set of tanks—which have resource constraints and operate on a continuous flow basis. Two models were developed: the first using mixed-integer linear programming (MILP) and the second using genetic algorithms (GA). Their main objective was to meet the whole forecast demand, observing the operating constraints of the refinery and minimizing the number of operational changes. A real-life data-set related to the production of fuel oil and asphalt in a large refinery was used. The MILP and GA models proved to be good solutions for both primary objectives, but the GA model resulted in a smaller number of operational changes. The reason for this is that GA incorporates a multi-criteria approach, which is capable of adaptively updating the weights of the objective throughout the evolutionary process.     

A linear algorithm for the pos/neg-weighted 1-median problem on a cactus

The 1-median problem on a network asks for a vertex minimizing the sum of the weighted shortest path distances from itself to all other vertices, each associated with a certain positive weight. We allow fornegative weights as well and devise an exact algorithm for the resulting ‘pos/neg-weighted’ problem defined on a cactus. The algorithm visits every vertex just once and runs thus in linear time. This research has been supported by the Spezialforschungsbereich F 003 ‘Optimierung und Kontrolle’, Projektbereich Diskrete Optimierung.