NP-Partitions over Posets with an Application to Reducing the Set of Solutions of NP Problems

The boolean hierarchy of k-partitions over NP for k 3 was introduced as a generalization of the well-known boolean hierarchy of sets (2-partitions). The classes of this hierarchy are exactly those classes of NP-partitions which are generated by finite labeled lattices. We generalize the boolean hierarchy of NP-partitions by studying partition classes which are defined by finite labeled posets. We give an exhaustive answer to the question of which relativizable inclusions between partition classes can occur depending on the relation between their defining posets. This provides additional evidence for the validity of the Embedding Conjecture for lattices. The study of the generalized boolean hierarchy is closely related to the issue of whether one can reduce the number of solutions of NP problems. For finite cardinality types, assuming the generalized boolean hierarchy of k-partitions over NP is strict, we give a complete characterization when such solution reductions are possible. This resolves in some sense an open question by Hemaspaandra et al.     

Fuzzy relation equations and reduction of fuzzy automata

We show that the state reduction problem for fuzzy automata is related to the problem of finding a solution to a particular system of fuzzy relation equations in the set of all fuzzy equivalences on its set of states. This system may consist of infinitely many equations, and finding its non-trivial solutions may be a very difficult task. For that reason we aim our attention to some instances of this system which consist of finitely many equations and are easier to solve. First, we study right invariant fuzzy equivalences, and their duals, the left invariant ones. We prove that each fuzzy automaton possesses the greatest right (resp. left) invariant fuzzy equivalence, which provides the best reduction by means of fuzzy equivalences of this type, and we give an effective procedure for computing this fuzzy equivalence, which works if the underlying structure of truth values is a locally finite residuated lattice. Moreover, we show that even better reductions can be achieved alternating reductions by means of right and left invariant fuzzy equivalences. We also study strongly right and left invariant fuzzy equivalences, which give worse reductions than right and left invariant ones, but whose computing is much easier. We give an effective procedure for computing the greatest strongly right (resp. left) invariant fuzzy equivalence, which is applicable to fuzzy automata over an arbitrary complete residuated lattice.     

Fuzzy Relation Equations (II): The Branch-point-solutions and the Categorized Minimal Solutions

This paper presents some novel theoretical results as well as practical algorithms and computational procedures on fuzzy relation equations (FRE). These results refine and improve what has already been reported in a significant manner. In the previous paper, the authors have already proved that the problem of solving the system of fuzzy relation equations is an NP-hard problem. Therefore, it is practically impossible to determine all minimal solutions for a large system if P ≠ NP. In this paper, an existence theorem is proven: there exists a special branch-point-solution that is greater than all minimal solutions and less than the maximum solution. Such branch-point-solution can be calculated based on the solution-base-matrix. Furthermore, a procedure for determining all branch-point-solutions is designed. We also provide efficient algorithms which is capable of determining as well as searching for certain types of minimal solutions. We have thus obtained: (1) a fast algorithm to determine whether a solution is a minimal solution, (2) the algorithm to search for the minimal solutions that has at least a minimum value at a component in the solution vector, and (3) the procedure of determining if a system of fuzzy relation equations has the unique minimal solution. Other properties are also investigated.     

An efficient solution procedure for fuzzy relation equations withmax-product composition

We study a system of fuzzy relation equations with max-product composition and present an efficient solution procedure to characterize the whole solution set by finding the maximum solution as well as the complete set of minimal solutions. Instead of solving the problem combinatorially, the procedure identifies the “nonminimal” solutions and eliminates them from the set of minimal solutions     

Distributive mereotopology: extended distributive contact lattices

The notion of contact algebra is one of the main tools in the region based theory of space. It is an extension of Boolean algebra with an additional relation C called contact. The elements of the Boolean algebra are considered as formal representations of spatial regions as analogues of physical bodies and Boolean operations are considered as operations for constructing new regions from given ones and also to define some mereological relations between regions as part-of, overlap and underlap. The contact relation is one of the basic mereotopological relations between regions expressing some topological nature. It is used also to define some other important mereotopological relations like non-tangential inclusion, dual contact, external contact and others. Most of these definitions are given by means of the operation of Boolean complementation. There are, however, some problems related to the motivation of the operation of Boolean complementation. In order to avoid these problems we propose a generalization of the notion of contact algebra by dropping the operation of complement and replacing the Boolean part of the definition by that of a distributive lattice. First steps in this direction were made in (Düntsch et al. Lect. Notes Comput. Sci. 4136, 135–147, 2006, Düntsch et al. J. Log. Algebraic Program. 76, 18–34, 2008) presenting the notion of distributive contact lattice based on the contact relation as the only mereotopological relation. In this paper we consider as non-definable primitives the relations of contact, nontangential inclusion and dual contact, extending considerably the language of distributive contact lattices. Part I of the paper is devoted to a suitable axiomatization of the new language called extended distributive contact lattice (EDC-lattice) by means of universal first-order axioms true in all contact algebras. EDC-lattices may be considered also as an algebraic tool for a certain subarea of mereotopology, called in this paper distributive mereotopology. The main result of Part I of the paper is a representation theorem, stating that each EDC-lattice can be isomorphically embedded into a contact algebra, showing in this way that the presented axiomatization preserves the meaning of mereotopological relations without considering Boolean complementation. Part II of the paper is devoted to topological representation theory of EDC-lattices, transferring into the distributive case important results from the topological representation theory of contact algebras. It is shown that under minor additional assumptions on distributive lattices as extensionality of the definable relations of overlap or underlap one can preserve the good topological interpretations of regions as regular closed or regular open sets in topological space.     

Solution of Fuzzy Equations with Max-Product Composition in Inverse Control and Decision Making Problems

A system of max-product type of equations, to which many inverse problems of fuzzy sets and relations, is solved. The minimal solution of this type of equations is determined from the solution of covering problems, which are NP-complete problems. A compatibility criterion for a system and redundancy criteria for equations and variables are formulated in terms of coverings. Possibilities for the reduction of the dimension of a covering problem and its solution methods are examined.     

Some results of fuzzy BCK-filters

Let X be a bounded BCK-algebra and f a fuzzy set in X. If a fuzzy BCK-filter μ in X satisfies that (i) fμ, (ii) for any fuzzy BCK-filter ν in X, fν implies μν, then μ is said to be generated by f and denote μ by [f) for short. In the present paper, we give a procedure to construct the [f) by f. As applications of this result we prove that the set of all fuzzy BCK-filters in a bounded BCK-algebra forms a complete and infinitely distributive lattice.     

Fuzzy relation equations (I): the general and specialized solving algorithms

 In this article, we develop a new method and an algorithm to solve a system of fuzzy relation equations. We first introduce a solution-base-matrix and then give a tractable mathematical logic representation of all minimal solutions. Next, we design a new universal algorithm to get them. Two simplification rules are found to simplify the solution-base-matrix. We show that a polynomial time algorithm to find all minimal solutions for a general system of fuzzy relation equations simply does not exist with expectation of P=N P. Hence, the problem of solving fuzzy relation equations is an N P-hard problem in terms of computational complexity. Our universal algorithm is still useful when one does not solve a large number of equations. In many real applications the problem of solving fuzzy relation equations can be simplified in polynomial time problems. In this article, we will discuss several cases of practical applications which have such polynomial algorithms.     

A characterisation of meet and join respecting pre-orders and congruences on finite lattices

A connection between pre-orders that respect the operations of the lattice and sets of join-irreducibles closed under a relation between joinirreducibles is demonstrated. It is shown that any lattice pre-order determines two sets of join-irreducibles closed under the relation and that elements of the lattice are related by the pre-order if and only if the subsets of joinirreducibles which they are greater than are comparable. The above connection is extended to congruences and the set of join-irreducibles that determine congruences that produce distributive quotient lattices are characterised. Finally it is shown that the quotient lattice of an arbitrary congruence is isomorphic to the lattice of decreasing subsets of join-irreducibles that determine the congruence.     

Uniqueness of Normal Proofs in Implicational Intuitionistic Logic

A minimal theorem in a logic L is an L-theorem which is not a non-trivial substitution instance of another L-theorem. Komori (1987) raised the question whether every minimal implicational theorem in intuitionistic logic has a unique normal proof in the natural deduction system NJ. The answer has been known to be partially positive and generally negative. It is shown here that a minimal implicational theorem A in intuitionistic logic has a unique -normal proof in NJ whenever A is provable without non-prime contraction. The non-prime contraction rule in NJ is the implication introduction rule whose cancelled assumption differs from a propositional variable and appears more than once in the proof. Our result improves the known partial positive solutions to Komori's problem. Also, we present another simple example of a minimal implicational theorem in intuitionistic logic which does not have a unique -normal proof in NJ.     

Linear complete differential resultants and the implicitization of linear DPPEs

The linear complete differential resultant of a finite set of linear ordinary differential polynomials is defined. We study the computation by linear complete differential resultants of the implicit equation of a system of n$n$ linear differential polynomial parametric equations in n−1$n-1$ differential parameters. We give necessary conditions to ensure properness of the system of differential polynomial parametric equations.     

Rough approximations via ideal on a complete completely distributive lattice

The rough approximations on a complete completely distributive lattice L based on binary relation were introduced by Zhou and Hu (Inf Sci 269:378–387, 2014), where the binary relation was defined on the set of non-zero join-irreducible elements. This paper extends Zhou and Hu’s rough set model by defining new approximation operators via ideal. When I is the least ideal of L and R is a reflexive binary relation, these two approximations coincide. We present the essential properties of new approximations and also discuss how the new one relates to the old one. Finally, the topological and lattice structures of the approximations are given.     

Solving interval-valued fuzzy relation equations

Solving systems of fuzzy relation equations is an important topic in fuzzy set theory. This paper studies the composite interval-valued fuzzy relation equations. After analyzing the properties of its solution set, we convert the fuzzy relation equations into a fuzzy relation inequality system and propose an efficient computational procedure to generate the whole solution set. Examples are included to illustrate the idea and algorithm     

Some classes of automata as partially ordered sets

A class of automata is considered as a partially ordered set by homomorphism relation. We show first that some classes of automata. e.g., quasiperfect automata, perfect automata and strongly cofinal automata, are lattices, and other classes, e.g., strongly connected automata, cyclic automata and cofinal automata, are not lattices. At the same time, we give algorithms for computing the least upper bound and the greatest lower bound of given two elements in each class which forms a lattice.     

Properties of \text{max-}* fuzzy relation equations

We extend the result of Zhang et al. (J Fuzzy Math 14:53, 2006), who discussed the finite fuzzy relation equations with max–min and max–prod composition. In this article, the $\text{max-}*$ composition is used for wide family of operations $*$ . In particular, families of solutions of two relation equations are compared.     

Continuous time-varying linear systems

We discuss implicit systems of ordinary linear differential equations with (time-) variable coefficients, their solutions in the signal space of hyperfunctions according to Sato and their solution spaces, called time-varying linear systems or behaviours, from the system theoretic point of view. The basic result, inspired by an analogous one for multidimensional constant linear systems, is a duality theorem which establishes a categorical one–one correspondence between time-varying linear systems or behaviours and finitely generated modules over a suitable skew-polynomial ring of differential operators. This theorem is false for the signal spaces of infinitely often differentiable functions or of meromorphic (hyper-)functions or of distributions on . It is used to obtain various results on key notions of linear system theory. Several new algorithms for modules over rings of differential operators and, in particular, new Gröbner basis algorithms due to Insa and Pauer make the system theoretic results effective.     

Enumeration and generation with a string automata representation

The representation of combinatorial objects is decisive for the feasibility of several enumerative tasks. In this work, we present a unique string representation for complete initially-connected deterministic automata (ICDFAs) with n$n$ states over an alphabet of k$k$ symbols. For these strings we give a regular expression and show how they are adequate for exact and random generation, allow an alternative way for enumeration and lead to an upper bound for the number of ICDFAs. The exact generation algorithm can be used to partition the set of ICDFAs in order to parallelize the counting of minimal automata, and thus of regular languages. A uniform random generator for ICDFAs is presented that uses a table of pre-calculated values. Based on the same table, an optimal coding for ICDFAs is obtained.     

On the role of complementation in implicit language equations and relations

We solve systems of boolean implicit equations and relations with union and complementation. If the languages are regular, we determine whether a system of implicit boolean equations or relations has solutions. If there is a solution, we provide an effective construction of a (regular) solution. We give representations for maximal and minimal solutions. Moreover, we also solve the problem of uniqueness of solutions as well as whether infinitely many solutions exist.