Existence of solutions for lower semicontinuous quasi-equilibrium problems

In this paper, we deal with the following quasi-equilibrium problem: given a nonempty subset C of a topological vector space X, a nonempty set D, two functions T : C → D, f : X × D → R and a multifunction S : C → 2^X, find such that , and for all . Such a problem, recently introduced in [1], extends and unifies several variational inequality problems, generalized complementarity problems and Nash equilibrium problems. We prove several existence results in which the upper semicontinuity of the multifunction S is not assumed.     

Entropy of multidimensional cellular automata

Since the topological entropy of a vast class of two-dimensional cellular automata (CA) is infinite, of interest is the possibility to renormalize it so that to obtain a positive finite value. We find the asymptotics of the information function of a multidimensional CA and, accordingly, introduce the renormalized topological entropy as a coefficient of this asymptotics. We describe some properties of the introduced quantity, in particular, its positivity for CA of the type of “The Game of Life.” Also, we give an example of an explicit evaluation of this parameter for a particular cellular automaton.     

Analytic-numerical solutions with a priori error bounds for time-dependent mixed partial differential problems

The aim of this paper is double. First, we point out that the hypothesis D(t₁)D(t₂) = D(t₂)D(t₁) imposed in [1] can be removed. Second, a constructive method for obtaining analytic-numerical solutions with a prefixed accuracy in a bounded domain Ω(t₀,t₁) = [0,p] × [t₀,t₁], for mixed problems of the type u_t(x,t) − D(t)u_xx(x,t) = 0, 0 < x < p, t> 0, subject to u(0,t) = u(p,t) = 0 and u(x,0) = F(x) is proposed. Here, u(x,t) and F(x) are r-component vectors, D(t) is a C^{r × r} valued analytic function and there exists a positive number δ such that every eigenvalue z of (1/2) (D(t) + D(t)^H) is bigger than δ. An illustrative example is included.     

Sand automata as cellular automata

In this paper, we exhibit a strong relation between the sand automata configuration space and the cellular automata configuration space. This relation induces a compact topology for sand automata, and a new context in which sand automata are homeomorphic to cellular automata acting on a specific subshift. We show that the existing topological results for sand automata, including the Hedlund-like representation theorem, still hold. In this context, we give a characterization of cellular automata which are sand automata, and study some dynamical behaviors such as equicontinuity. Furthermore, we deal with simple sand automata. We show that the classical definition of nilpotency is not meaningful for sand automata. Then, we introduce the suitable new notion of flattening sand automata. Finally, we prove that this simple dynamical behavior is undecidable.     

On cellular automata over Galois rings

In this paper we study the invertibility of one-dimensional cellular automata, determined by a local rule, acting on the space of all doubly-infinite sequences taking values in a finite Galois ring. We also compute the topological entropy of one-dimensional CA generated by additive local rule over a finite Galois ring. We conclude by showing that the topological entropy of an additive invertible CA over a finite Galois ring is equal to its inverse.     

基于字典学习的非线性降维方法

目前,众多的数据降维（Dimensionality reduction, DR）方法（如经典的PCA（Principle component analysis）, ISOMAP（Isometric mapping））能够使降维后的数据保留原始信号的重要特征,但是从降维后的数据中很好地恢复出原始信号仍旧是一个挑战.近年来,稀疏表示（Sparse representation, SR）在信号重构研究中受到广泛关注,信号可以利用过完备字典中少数原子的线性组合来描述.本文提出一种基于字典学习的非线性降维方法.从高维输入信号到低维特征的降维过程中,期望一些重要的几何特征（内积、距离和夹角）得以保留,同时又能够从低维数据中恢复出原始信号.为达此目的,本文采用CDL（Concentrated dictionary learning）算法训练一个字典对（高维字典D和低维字典P）,使高维原始信号的能量能够聚集于低维子空间中.字典D用来获取稀疏表示系数,字典P是D的直接降维采样,CDL算法能够保证P聚集D中的大部分能量.这样,信号的降维与恢复问题就转变为字典对的训练问题,信号的降维即为从D到P的能量保留过程.实验表明:CDL可在RIP（Restricted isomery property）条件的限制之外具有一定的信号重建能力,能在更低的维度条件下恢复图像,优于传统的压缩感知方法.此外,在噪声较大的情况下,CDL图像压缩效果优于JPEG2000.     

Discontinuous quasivariational-like inequalities

In this note, we deal with the following problem: given X Rⁿ, a multification gG : X → 2^X, two (single-valued) maps f : X → Rⁿ, η : X × X → Rⁿ, find a point x* X such that x* Γ (x*) and f(x*), η(x,x*) ≥ 0 for all x Γ(x*). We prove an existence theorem in which, in particular, the function f is not supposed to be continuous.     

Constrained string editing

Let X and Y be any two strings of finite length. We consider the problem of transforming X to Y using the edit operations of deletion, insertion, and substitution. The optimal transformation is the one which has the minimum edit distance associated with it. The problem of computing this distance and the optimal transformation using no edit constraints has been studied in the literature. In this paper we consider the problem of transforming X to Y using any arbitrary edit constraint involving the number and type of edit operations to be performed. An algorithm is presented to compute the minimum distance associated with editing X to Y subject to the specified constraint. The algorithm requires O(¦X¦ ¦ Y¦min(¦ X¦,¦ Y¦)) time and space. The technique to compute the optimal transformation is also presented.     

Criterion of Infinite Topological Entropy for Multidimensional Cellular Automata

The paper proves the infinity of the topological entropy for a wide class of multi-dimensional cellular automata, namely, automata with spaceships.     

Computing planar swept polygons under translation

A translational sweep is the translating of a polygon, called the generatrix G, around another polygon, called the directrix D, under two conditions: (1) G is always in contact with D; and (2) the interiors of G and D do not intersect. Three classes of translational sweep are studied, including the case in which both G and D are convex; the case in which G is convex, D monotone; and the case in which both are monotone. Efficient algorithms for computing the trajectory and the swept area as well as geometric and computational properties are presented for each class. A notion called the inverse generatrix, which reveals a duality between the trajectory and the swept polygon, is introduced to reduce complexity.     

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.     

Transformations of the one-dimensional cellular automata rule space

We introduce the notion of double permutation in order to study particular classes of transformations of the one-dimensional cellular automata rule space. These classes of transformations are characterized according to different sets of metrical, language theoretic, and dynamical properties they preserve. Each set of transformations we propose induces an equivalence relation over the cellular automata rule space. We give exact results on the cardinality of the quotient sets generated by these equivalence relations. Finally, we discuss some interesting open problems.     

Theory of granular lattices and its applications

Based on the concept of components of elements of a complete lattice this paper proposed the theory of granular lattices and proved that a topological space X is locally connected if and only if the lattice Ω(X) of its topology is a granular lattice. Moreover, this paper discussed compactness of abstract semantics on certain granular lattices and proved that the semantics is compact if it is continuous in a natural sense, and as a corollary, the compactness of Lukasiewicz's semantics was clarified.     

Controllable fair queuing for meeting performance goals

Computing and storage utilities must control resource usage to meet contractual performance targets for hosted customers under dynamic conditions, including flash crowds and unexpected resource failures. This paper explores properties of proportional share resource schedulers that are necessary for stability and responsiveness under feedback control. It shows that the fairness properties commonly defined for proportional share schedulers using Weighted Fair Queuing (WFQ) are not preserved across changes to the relative weights of competing request flows. As a result, conventional WFQ schedulers are not controllable by a resource controller that adapts by adjusting the weights. The paper defines controllable fairness properties, presents an algorithm to adjust any WFQ scheduler when the weights change, and proves that the algorithm results in controllable-fair schedulers.

The analytic results are confirmed by experimental evaluation using a three-tier Web service and a prototype controllable-fair scheduler called C-SFQ(D). C-SFQ(D) extends concurrency-controlled Start-time Fair Queuing (SFQ(D), which supports proportional sharing in multi-tasking computing resources. The prototype includes an adaptive control system that adjusts the flow weights in C-SFQ(D) to meet latency and throughput targets under a variety of conditions. The experimental results demonstrate the importance of controllable-fair scheduling for feedback control of computing utilities.     

Enabling structural summaries for efficient update and workload adaptation

To facilitate queries over semi-structured data, various structural summaries have been proposed. Structural summaries are derived directly from data and serve as the indexes for evaluating path expressions. We introduce D(k)-index, an adaptive structural summary, for general graph-structured data. Building on previous 1-index and A(k)-index, D(k)-index is also based on the concept of bisimilarity. However, as a generalization of 1-index and A(k)-index, D(k)-index possesses the adaptive ability to adjust its structure to changes in query load. It also enables efficient update algorithms, which are crucial to real applications but have not been adequately addressed in previous literatures. Our experiments show that D(k)-index is a more effective structural summary than previous static ones as a result of its query load sensitivity. In addition, the update operations on it can be performed more efficient than on its predecessors.     

Emergence and control of macro-spatial structures in perturbed cellular automata, and implications for pervasive computing systems

Predicting the behavior of complex decentralized pervasive computing systems before their deployment in a dynamic environment, as well as being able to influence and control their behavior in a decentralized way, will be of fundamental importance in the near future. In this context, this paper describes the general behavior observed in a large set of asynchronous cellular automata when external perturbations influence the internal activities of cellular automata cells. In particular, we observed that stable macrolevel spatial structures emerge from local interactions among cells, a behavior that does not emerge when cellular automata are not perturbed. Similar sorts of macrolevel behaviors are likely to emerge in the context of pervasive computing systems and need to be studied, controlled, and possibly fruitfully exploited. On this basis, the paper also reports the results of a set of experiments, showing how it is possible to control, in a decentralized way, the behavior of perturbed cellular automata, to make any desired patterns emerge.     

Chaos Theory in Operations Research

The purpose of this paper is to illustrate the potential importance of non-linear dynamical systems theory in OR. After a brief introduction into some basic concepts. We study an advertising diffusion model to exemplify the composition of chaos and optimalily in dynamic programming. It turns out that economies of scale may imply period three cycle and consequently topological chaos. Furthermore, we present an outlook to further potential applications of non-linear dynamical systems in OR/MS queing systems are briefly discussed whose random coding fluctuations are endogenously generated in a pure deterministic framework. Among the various paradigms favouring complex behaviour are dynamic strategic interactions, slow-fast systems, and cellular automata.     

Power and size of extended Watson–Crick L systems

A Watson–Crick D0L system is a language-theoretic model which is based on a D0L system and a letter-to-letter morphism, representing the Watson–Crick complementarity phenomenon of DNA. The two components are connected by a triggering mechanism. The computational capacity of these constructs is of particular interest. In this paper we prove that if the underlying systems are EDT0L systems or E0L systems, then these constructs are able to generate any recursively enumerable language. Moreover, to reach this power, Watson–Crick EDT0L systems with either two tables or a bounded number of non-terminals suffice.     

McClellan transformation and the construction of biorthogonal wavelet bases of LR

Bidimensional wavelet bases are constructed by means of McClellan's transformation applied to a pair of one-dimensional biorthogonal wavelet filters. It is shown that under some conditions on the transfer function F(ω₁,ω₂) associated to the McClellan transformation and on the dilation matrix D, it is possible to construct symmetric compactly supported biorthogonal wavelet bases of L²(R²). Finally, the construction method is illustrated by means of numerical examples.     

On interpreting and inferring propositional formulas of data dependencies in a relational database

This paper concerns generally the satisfaction and the inference problem involving functional and/or multivalued dependencies in a relational database. In particular, two independent aids in solving an inference problem, concerning the logical counterparts of functional as well as multivalued dependencies, are introduced. The first aid is provided by establishing a pair of complementary inequivalence and equivalence theorems between the propositional formula corresponding to the difference, U-X, in set theory and the propositional formula not(X) where U is a relation scheme and X is a subset of U. By applying these theorems, correctness of solving an inference problem is assured. The second aid is the application of a Venn diagram for simplifying a propositional formula involving conjunctions, differences, etc., for solving an inference problem. A guideline for constructing simplified Venn diagrams is also given and discussed.