Rational bijection of rational sets

Summary In this paper we initiate the study of rational bijections, that is of rational transductions which are bijections of a rational (=regular) set R onto a rational set S. We present a complete and easily decidable characterization of the existence of a rational bijection between two given rational sets.This author acknowledges with pleasure the financial support of the Austrian Federal Ministry of Science and Research which allowed him to spend one week in Graz where this paper was initiated     

Characterizing sets of jobs that admit optimal greedy-like algorithms

The “Priority Algorithm” is a model of computation introduced by Borodin, Nielsen and Rackoff ((Incremental) Priority algorithms, Algorithmica 37(4):295–326, 2003) which formulates a wide class of greedy algorithms. For an arbitrary set \mathbbS\mathbb{S} of jobs, we are interested in whether or not there exists a priority algorithm that gains optimal profit on every subset of \mathbbS\mathbb{S} . In the case where the jobs are all intervals, we characterize such sets \mathbbS\mathbb{S} and give an efficient algorithm (when \mathbbS\mathbb{S} is finite) for determining this. We show that in general, however, the problem is NP-hard.     

An incremental space to visualize dynamic data sets

In Information Visualization, adding and removing data elements can strongly impact the underlying visual space. We have developed an inherently incremental technique (incBoard) that maintains a coherent disposition of elements from a dynamic multidimensional data set on a 2D grid as the set changes. Here, we introduce a novel layout that uses pairwise similarity from grid neighbors, as defined in incBoard, to reposition elements on the visual space, free from constraints imposed by the grid. The board continues to be updated and can be displayed alongside the new space. As similar items are placed together, while dissimilar neighbors are moved apart, it supports users in the identification of clusters and subsets of related elements. Densely populated areas identified in the incSpace can be efficiently explored with the corresponding incBoard visualization, which is not susceptible to occlusion. The solution remains inherently incremental and maintains a coherent disposition of elements, even for fully renewed sets. The algorithm considers relative positions for the initial placement of elements, and raw dissimilarity to fine tune the visualization. It has low computational cost, with complexity depending only on the size of the currently viewed subset, V. Thus, a data set of size N can be sequentially displayed in O(N) time, reaching O(N ²) only if the complete set is simultaneously displayed.     

Arithmetic Meyer sets and finite automata

Non-standard number representation has proved to be useful in the speed-up of some algorithms, and in the modelization of solids called quasicrystals. Using tools from automata theory we study the set of β-integers, that is, the set of real numbers which have a zero fractional part when expanded in a real base β, for a given β > 1. In particular, when β is a Pisot number — like the golden mean —, the set is a Meyer set, which implies that there exists a finite set F (which depends only on β) such that . Such a finite set F, even of minimal size, is not uniquely determined.In this paper we give a method to construct the sets F and an algorithm, whose complexity is exponential in time and space, to minimize their size. We also give a finite transducer that performs the decomposition of the elements of as a sum belonging to .     

On the connection between many-valued contexts and general geometric structures

We study the connection between certain many-valued contexts and general geometric structures. The known one-to-one correspondence between attribute-complete many-valued contexts and complete affine ordered sets is used to extend the investigation to π-lattices, class geometries, and lattices with classification systems. π-lattices are identified as a subclass of complete affine ordered sets, which exhibit an intimate relation to concept lattices closely tied to the corresponding context. Class geometries can be related to complete affine ordered sets using residuated mappings and the notion of a weak parallelism. Lattices with specific sets of classification systems allow for some sort of “reverse conceptual scaling”.     

Least-squares fitting of multiple M-dimensional point sets

Based on the classic absolute orientation technique, a new method for least-squares fitting of multiple point sets in m-dimensional space is proposed, analyzed and extended to a weighted form in this paper. This method generates a fixed point set from k corresponding original m-dimensional point sets and minimizes the mean squared error between the fixed point set and these k point sets under the similarity transformation. Experiments and interesting applications are presented to show its efficiency and accuracy.     

Set constructors,finite sets,and logical semantics

The use of sets in declarative programming has been advocated by several authors in the literature. A representation often chosen for finite sets is that of scons, parallel to the list constructor cons. The logical theory for such constructors is usually tacitly assumed to be some formal system of classical set theory. However, classical set theory is formulated for a general setting, dealing with both finite and infinite sets, and not making any assumptions about particular set constructors. In giving logical-consequence semantics for programs with finite sets, it is important to know exactly what connection exists between sets and set constructors. The main contribution of this paper lies in establishing these connections rigorously. We give a formal system, called SetAx, designed around the scons constructor. We distinguish between two kinds of set constructors, scons(x, y) and dscons(x, y), where both represent {x} ∪ y, but x ϵ y is possible in the former, while x ∉ y holds in the latter. Both constructors find natural uses in specifying sets in logic programs. The design of SetAx is guided by our choice of scons as a primitive symbol of our theory rather than as a defined one, and by the need to deduce non-membership relations between terms, to enable the use of dscons. After giving the axioms SetAx, we justify it as a suitable theory for finite sets in logic programming by (i) showing that the set constructors indeed behave like finite sets; (ii) providing a framework for establishing the correctness of set unification; and (iii) defining a Herbrand structure and providing a basis for discussing logical consequence semantics for logic programs with finite sets. Together, these results provide a rigorous foundation for the set constructors in the context of logical semantics.     

Invariant control sets on flag manifolds

LetG be a semisimple Lie group and letS G be a subsemigroup with nonempty interior. In this paper we study invariant control sets for the action ofS on homogeneous spaces ofG. These sets on the boundary manifolds of the group are characterized in terms of the semisimple elements contained in intS. From this characterization a result on controllability of control systems on semisimple Lie groups is derived. Invariant control sets for the action of S on the boundaries of larger groups¯G withG ¯G are also studied. This latter case includes the action ofS on the projective space and on the flag manifolds.This research was partially supported by CAPES, Grant No. 3578/82-4.     

Exploiting randomness on continuous sets

In this paper, we introduce a new type of field—continuous sets, where we can exploit randomness in the non-repeating decimal expansions of irrationals for cryptographical purposes, and present two specific sets, a real interval [0, 1) and a functional space F_[0, 1). On [0, 1), we propose ideal irrational random number generator (IIRNG) which generates non-repeating random number sequence as a truly RNG by computing the decimal expansion of an randomly chosen irrational. On F_[0, 1), we propose integral encryption scheme (IES) with which we can encrypt an infinite message and obtain perfect security in one-time encryption by computing the integration of the message on a randomly chosen function. Either the seeds of IIRNG or the keys of IES are sufficiently safe and immune to exhaustive key search. Both IIRNG and IES require the assumption that an element of [0, 1) or F_[0, 1) can be uniformly randomly chosen. Though the assumption cannot be achieved in classical finite machine, we present the discretization of the assumption, i.e., randomly choosing an element of U or V (the set of all possible methods of generating irrationals or functions). The immunity of seeds or keys to exhaustive key search still exists, since any finite search for a random element of U or V is inefficient. This is the basic idea of implementing IIRNG and IES in finite machine. Two corresponding examples IRNG and IBC are also presented, whose securities are guaranteed by the randomly chosen elements of U or V.     

Computing transparently: the independent sets in a graph

A procedure is given for finding the independent sets in an undirected graph by xeroxing onto transparent plastic sheets. Let an undirected graph having n vertices and m edges be given. A list of all the independent subsets of the set of vertices of the graph is constructed by using a xerox machine in a manner that requires the formation of only n + m + 1 successive transparencies. An accompanying list of the counts of the elements in each independent set is then constructed using only O(n ²) additional transparencies. The list with counts provides a list of all maximum independent sets. This gives an O(n ²) step solution for the classical problem of finding the cardinality of a maximal independent set in a graph. The applicability of these procedures is limited, of course, by the increase in the information density on the transparencies when n is large. Our ultimate purpose here is to give hand tested ‘ultra parallel’ algorithmic procedures that may prove suitable for realization using future optical technologies.     

Algorithms for testing that sets of DNA words concatenate without secondary structure

We present an efficient algorithm for determining whether all moleculesin a combinatorial set of DNA or RNA strandsare structure free, and thus availablefor bonding to their Watson-Crick complements.This work is motivated by the goalof testing whether strands used in DNAcomputations or as molecular bar-codesare structure free, where the strands areconcatenations of short words. We alsopresent an algorithm for determining whetherall words in S*, for some finite setS of equi-length words, are structure free. This revised version was published online in June 2006 with corrections to the Cover Date.     

Translation sets of permutations: Enumeration of selfcomplementary step-cycles

For given integern>2, there corresponds to each step-cycle a set of permutations, called a translation set. All the translation sets of permutations on the setS={1, 2, ...,n?1} form a set of equivalence classes on the set of all permutations onS. The selfcomplementary step-cycles are described and enumerated. A more general introduction to translation sets may be found in [4] and [3].     

A REVIEW OF TREE CONVEX SETS TEST

A collection of sets may have some interesting properties which help identify efficient algorithms for constraint satisfaction problems and combinatorial auction problems. One of the properties is tree convexity. A collection S of sets is tree convex if we can find a tree T whose nodes are the union of the sets of S and each set of S is the nodes of a subtree of T . This concept extends that of row convex sets each of which is an interval over a total ordering of the elements of the union of these sets. An interesting problem is to find efficient algorithms to test whether a collection of sets is tree convex. It is not known before if there exists a linear time algorithm for this test. In this paper, we review the materials that are the key to a linear algorithm: hypergraphs, a characterization of tree convex sets and the acyclic hypergraph test algorithm. Some typos in the original paper of the acyclicity test are corrected here. Some experiments show that the linear algorithm is significantly faster than a well‐known existing algorithm.     

Robust invariant sets for constrained storage systems

Several items are produced and stored into n buffers in order to supply an external demand without interruptions. We consider the classical problem of determining control laws and smallest buffer levels guaranteeing that an unknown bounded demand is always satisfied. A simple model with n decoupled integrators and n additive bounded disturbances is employed. The coupling arises from bounds on the total production capacity and on the total demand. Invariant set theory for linear and switched linear systems is exploited to compute robust positive invariant sets and controlled robust invariant sets for two commonly adopted scheduling policies. This paper provides the explicit expression of the invariant sets for any arbitrary n.     

On minimal elements of upward-closed sets

Upward-closed sets of integer vectors enjoy the merit of having a finite number of minimal elements, which is behind the decidability of a number of Petri net related problems. In general, however, such a finite set of minimal elements may not be effectively computable. In this paper, we develop a unified strategy for computing the sizes of the minimal elements of certain upward-closed sets associated with Petri nets. Our approach can be regarded as a refinement of a previous work by Valk and Jantzen (in which a necessary and sufficient condition for effective computability of the set was given), in the sense that complexity bounds now become available provided that a bound can be placed on the size of a witness for a key query. The sizes of several upward-closed sets that arise in the theory of Petri nets as well as in backward-reachability analysis in automated verification are derived in this paper, improving upon previous decidability results shown in the literature.     

The geometry of basis sets for morphologic closing

P. Maragos (1989) provided a framework for the decomposition of many morphologic operations into orthogonal components or basis sets. Using this framework, a method to find the minimal basis set for the important operation of closing in two dimensions is described. The closing basis sets are special because their elements are members of an ordered, global set of closing shapes or primitives. The selection or design of appropriate individual or multiple structuring elements for image filtering can be better understood, and sometimes implemented more easily, through consideration of the orthogonal closing decomposition. Partial closing of images using ordered fractions of a closing basis set may give a finer texture or roughness measure than that obtained from the conventional use of scaled sets of shapes such as the disc. The connection between elements of the basis set for closing and the complete, minimal representation of arbitrary logic functions is analyzed from a geometric viewpoint     

Two simply connected sets that have the same area are IP-equivalent

A pair of neighboring, opposite-valued pixels in a two-valued digital image is called interchangeable if reversing their values preserves the topology of the image. It was conjectured in Rosenfeld, Saha, Nakamula, Pattern Recognition 34 (2001) 1853-1865 that if two digital images have the same number of 1's, and their sets of 1's S,T are simply connected, then S can be transformed into T by a sequence of interchanges. In that paper this conjecture was proved only for certain special cases—for example, if S and T are arcs. This paper proves the conjecture for arbitrary simply connected sets.     

Dominating,weakly stable,and uncovered sets: Properties and generalizations

We consider the problem of collective choice in a tournament, i.e., when the majority relation, which plays the role of the collective preference system on this set of alternatives, can be represented by a complete asymmetric oriented graph. We compare three solutions of the collective choice problem: minimal dominating, uncovered, and minimal weakly stable sets. We construct generalizations of the minimal dominating set and find out, with their help, how the system of dominating sets looks like in the general case. We formulate a criterion that determines whether an alternative belongs to a minimal weakly stable set. We find out how minimal weakly stable sets relate to uncovered sets. Based on the notion of stability of an alternative and the set of alternatives we construct generalizations for the notions of uncovered and weakly stable sets—the classes of k-stable alternatives and k-stable sets. We prove inclusion relations between these classes.     

Optimal conclusive sets for comparator networks

A set of input vectors S$S$ is conclusive for a certain functionality if, for every comparator network, correct functionality for all input vectors is implied by correct functionality for all vectors in S$S$. We consider four functionalities of comparator networks: sorting, merging, sorting of bitonic vectors, and halving. For each of these functionalities, we present two conclusive sets of minimal cardinality. The members of the first set are restricted to be binary, while the members of the second set are unrestricted. For all the above functionalities, except halving, the unrestricted conclusive set is much smaller than the binary one.     

Fuzzy sets and cut systems in a category of sets with similarity relations

Let \Upomega\Upomega be a complete residuated lattice. Let SetR(\Upomega){\mathbf{SetR}}(\Upomega) be the category of sets with similarity relations with values in \Upomega\Upomega (called \Upomega\Upomega-sets), which is an analogy of the category of classical sets with relations as morphisms. A fuzzy set in an \Upomega\Upomega-set in the category SetR(\Upomega){\mathbf{SetR}}(\Upomega) is a morphism from \Upomega\Upomega-set to a special \Upomega\Upomega-set (\Upomega,?),(\Upomega,\leftrightarrow), where ?\leftrightarrow is the biresiduation operation in \Upomega.\Upomega. In the paper, we prove that fuzzy sets in \Upomega\Upomega-sets in the category SetR(\Upomega){\mathbf{SetR}}(\Upomega) can be expressed equivalently as special cut systems (C_a)_{a ? \Upomega}.(C_{\alpha})_{\alpha\in\Upomega}.