A characterization theorem for injective model classes axiomatized by general rules

We continue the work in Zhu et al. [Normal conditions for inference relations and injective models, Theoret. Comput. Sci. 309 (2003) 287–311]. A class Ω of strict partial order structures (posets, for short) is said to be axiomatizable if the class of all injective preferential models from Ω may be characterized in terms of general rules. This paper aims to obtain some characteristics of axiomatizable classes. To do this, a monadic second-order frame language is presented. The relationship between ₀-axiomatizability and second-order definability is explored. Then a notion of an admissible set is introduced. Based on this notion, we show that any preferential model, which does not contain any four-node substructure, must be a reduct of some injective model. Furthermore, we furnish a necessary and sufficient condition for the axiomatizability of classes of injective preferential models using general rules. Finally, we show that, in some sense, the class of all posets without any four-node substructure is the largest among axiomatizable classes.     

The characteristic finite volume element method for the nonlinear convection-dominated diffusion problem

In modern numerical simulation of prospecting and exploiting oil–gas resources and environmental science, it is important to consider a numerical method for nonlinear convection-dominated diffusion problems. Based on actual conditions, such as the three-dimensional characteristics of large-scale science-engineering computation, we present a kind of characteristic finite volume element method. Some techniques, such as calculus of variations, commutating operators, the theory of prior estimates and techniques, are adopted. Suboptimal order error estimate in L² norm and optimal order error estimate in H¹ norm are derived to determine the errors for the approximate solution. Numerical results are presented to verify the performance of the scheme.     

A novel lossless data compression scheme based on the error correcting Hamming codes

This paper introduces a novel lossless binary data compression scheme that is based on the error correcting Hamming codes, namely the HCDC scheme. In this scheme, the binary sequence to be compressed is divided into blocks of n bits length. To utilize the Hamming codes, the block is considered as a Hamming codeword that consists of p parity bits and d data bits (n=d+p). Then each block is tested to find if it is a valid or a non-valid Hamming codeword. For a valid block, only the d data bits preceded by 1 are written to the compressed file, while for a non-valid block all n bits preceded by 0 are written to the compressed file. These additional 1 and 0 bits are used to distinguish the valid and the non-valid blocks during the decompression process. An analytical formula is derived for computing the compression ratio as a function of block size, and fraction of valid data blocks in the sequence. The performance of the HCDC scheme is analyzed, and the results obtained are presented in tables and graphs. Finally, conclusions and recommendations for future works are pointed out.     

Bandwidth-sharing networks in overload

Bandwidth-sharing networks as considered by Massoulié and Roberts provide a natural modeling framework for describing the dynamic flow-level interaction among elastic data transfers. Under mild assumptions, it has been established that a wide family of so-called -fair bandwidth-sharing strategies achieve stability in such networks provided that no individual link is overloaded.

In the present paper we focus on -fair bandwidth-sharing networks where the load on one or several of the links exceeds the capacity. Evidently, a well-engineered network should not experience overload, or even approach overload, in normal operating conditions. Yet, even in an adequately provisioned system with a low nominal load, the actual traffic volume may significantly fluctuate over time and exhibit temporary surges. Furthermore, gaining insight into the overload behavior is crucial in analyzing the performance in terms of long delays or low throughputs as caused by large queue build-ups. The way in which such rare events tend to occur, commonly involves a scenario where the system temporarily behaves as if it experiences overload.

In order to characterize the overload behavior, we examine the fluid limit, which emerges from a suitably scaled version of the number of flows of the various classes. The convergence of the scaled number of flows to the fluid limit is empirically validated through simulation experiments. Focusing on linear solutions to the fluid-limit equation, we derive a fixed-point equation for the corresponding asymptotic growth rates. It is proved that a fixed-point solution is also a solution to a related strictly concave optimization problem, and hence exists and is unique. We use the fixed-point equation to investigate the impact of the traffic intensities and the variability of the flow sizes on the asymptotic growth rates. The results are illustrated for linear topologies and star networks as two important special cases. Finally, we briefly discuss extensions to models with user impatience.     

Fast algorithms for finding disjoint subsequences with extremal densities

We derive fast algorithms for the following problem: given a set of n points on the real line and two parameters s and p, find s disjoint intervals of maximum total length that contain at most p of the given points. Our main contribution consists of algorithms whose time bounds improve upon a straightforward dynamic programming algorithm, in the relevant case that input size n is much bigger than parameters s and p. These results are achieved by selecting a few candidate intervals that are provably sufficient for building an optimal solution via dynamic programming. As a byproduct of this idea we improve an algorithm for a similar subsequence problem of Chen et al. [Disjoint segments with maximum density, in: International Workshop on Bioinformatics Research and Applications IWBRA 2005, (within ICCS 2005), Lecture Notes in Computer Science, vol. 3515, Springer, Berlin, pp. 845–850]. The problems are motivated by the search for significant patterns in biological data. Finally, we propose several heuristics that further reduce the time complexity in typical instances. One of them leads to an apparently open subsequence sum problem of independent interest.     

Robust information filter for decentralized estimation

This paper presents a robust information filter which inherits the structural simplicity of the information filter and the robustness property of the H_∞ filter with respect to noise statistics. In this filter, an assurance level γ on the noise bound is reflected in the newly defined covariance matrix. It provides robustness against uncertainty in the noise model by sacrificing performance in the minimum variance sense. All these are achieved while retaining the simple structure of the standard information filter. Thus, it is able to realize robust decentralized estimation with less communication and computational load while without the need to model the system noise accurately.     

Fuzzy rough set theory for the interval-valued fuzzy information systems

The concept of the rough set was originally proposed by Pawlak as a formal tool for modelling and processing incomplete information in information systems, then in 1990, Dubois and Prade first introduced the rough fuzzy sets and fuzzy rough sets as a fuzzy extension of the rough sets. The aim of this paper is to present a new extension of the rough set theory by means of integrating the classical Pawlak rough set theory with the interval-valued fuzzy set theory, i.e., the interval-valued fuzzy rough set model is presented based on the interval-valued fuzzy information systems which is defined in this paper by a binary interval-valued fuzzy relations RF⁽ⁱ⁾(U×U) on the universe U. Several properties of the rough set model are given, and the relationships of this model and the others rough set models are also examined. Furthermore, we also discuss the knowledge reduction of the classical Pawlak information systems and the interval-valued fuzzy information systems respectively. Finally, the knowledge reduction theorems of the interval-valued fuzzy information systems are built.     

Incremental margin algorithm for large margin classifiers

In this contribution, we introduce a new on-line approximate maximal margin learning algorithm based on an extension of the perceptron algorithm. This extension, which we call fixed margin perceptron (FMP), finds the solution of a linearly separable learning problem given a fixed margin. It is shown that this algorithm converges in updates, where γ_f<γ^* is the fixed margin, γ^* is the optimum margin and R is the radius of the ball that circumscribes the data. The incremental margin algorithm (IMA) approximates the large margin solution by successively using FMP with increasing margin values. This incremental approach always guarantees a good solution at hands. Also, it is easy to implement and avoids quadratic programming methods. IMA was tested using several different data sets and it yields results similar to those found by an SVM.     

Multimodal logic programming

We give a framework for developing the least model semantics, fixpoint semantics, and SLD-resolution calculi for logic programs in multimodal logics whose frame restrictions consist of the conditions of seriality (i.e. ) and some classical first-order Horn clauses. Our approach is direct and no special restriction on occurrences of □_i and _i is required. We apply our framework for a large class of basic serial multimodal logics, which are parameterized by an arbitrary combination of generalized versions of axioms T, B, 4, 5 (in the form, e.g. 4:□_i→□_j□_k) and I:□_i→□_j. Another part of the work is devoted to programming in multimodal logics intended for reasoning about multidegree belief, for use in distributed systems of belief, or for reasoning about epistemic states of agents in multiagent systems. For that we also use the framework, and although these latter logics belong to the mentioned class of basic serial multimodal logics, the special SLD-resolution calculi proposed for them are more efficient.     

Improved construction for universality of determinant and permanent

Valiant [L. Valiant, Completeness classes in algebra, in: Proc. 11th Annual ACM Symposium on the Theory of Computing, Atlanta, GA, 1979, pp. 249–261] proved that every polynomial of formula size e is a projection of the (e+2)×(e+2) determinant polynomial. We improve “e+2” to “e+1”, also for a definition of formula size that does not count multiplications by constants as gates. Our proof imitates the “2e+2” proof of von zur Gathen [J. von zur Gathen, Feasible arithmetic computations: Valiant's hypothesis, Journal of Symbolic Computation 4 (1987) 137–172], but uses different invariants and a tighter set of base cases.     

On absolute summability factors of infinite series

In this paper a general theorem on |A,δ|_k-summability methods has been proved. This theorem includes, as a special case, a known result in [E. Savas, Factors for |A|_k Summability of infinite series, Comput. Math. Appl. 53 (2007) 1045–1049].     

Compensation of the thermal influence on a high accuracy optical fibre displacement sensor

Thermal drifts are the main sources of error on measurements made with a high accuracy extrinsic optical fibre displacement sensor. We propose a theoretical model which can be used to calculate the influence of temperature permitting hence to correct the measurement. Our model is based on the analysis of the effect of the temperature on electronic and optoelectronic components of the sensor. The model has been experimentally validated at a mesoscopic range of accuracy (1σ300 nm) using a custom-made optical fibre sensor.     

Adaptive sampled-data tracking for input-constrained exothermic chemical reaction models

We consider digital input-constrained adaptive and non-adaptive output feedback control for a class of nonlinear systems which arise as models for controlled exothermic chemical reactors. Our objective is set-point control of the temperature of the reaction, with pre-specified asymptotic tracking accuracy set by the designer. Our approach is based on λ-tracking controllers, but in a context of piecewise constant sampled-data output feedbacks and possibly adapted sampling periods. The approach does not require any knowledge of the systems parameters, does not invoke an internal model, is simple in its design, copes with noise corrupted output measurements, and requires only a feasibility assumption in terms of the reference temperature and the input constraints.     

Vector extrapolation methods with applications to solution of large systems of equations and to PageRank computations

An important problem that arises in different areas of science and engineering is that of computing the limits of sequences of vectors {x_n}, where with N very large. Such sequences arise, for example, in the solution of systems of linear or nonlinear equations by fixed-point iterative methods, and lim_n→∞x_n are simply the required solutions. In most cases of interest, however, these sequences converge to their limits extremely slowly. One practical way to make the sequences {x_n} converge more quickly is to apply to them vector extrapolation methods. In this work, we review two polynomial-type vector extrapolation methods that have proved to be very efficient convergence accelerators; namely, the minimal polynomial extrapolation (MPE) and the reduced rank extrapolation (RRE). We discuss the derivation of these methods, describe the most accurate and stable algorithms for their implementation along with the effective modes of usage in solving systems of equations, nonlinear as well as linear, and present their convergence and stability theory. We also discuss their close connection with the method of Arnoldi and with GMRES, two well-known Krylov subspace methods for linear systems. We show that they can be used very effectively to obtain the dominant eigenvectors of large sparse matrices when the corresponding eigenvalues are known, and provide the relevant theory as well. One such problem is that of computing the PageRank of the Google matrix, which we discuss in detail. In addition, we show that a recent extrapolation method of Kamvar et al. that was proposed for computing the PageRank is very closely related to MPE. We present a generalization of the method of Kamvar et al. along with a very economical algorithm for this generalization. We also provide the missing convergence theory for it.     

Games with winning conditions of high Borel complexity

We first consider infinite two-player games on pushdown graphs. In previous work, Cachat et al. [Solving pushdown games with a Σ₃-winning condition, in: Proc. 11th Annu. Conf. of the European Association for Computer Science Logic, CSL 2002, Lecture Notes in Computer Science, Vol. 2471, Springer, Berlin, 2002, pp. 322–336] have presented a winning decidable condition that is Σ₃-complete in the Borel hierarchy. This was the first example of a decidable winning condition of such Borel complexity. We extend this result by giving a family of decidable winning conditions of arbitrary finite Borel complexity. From this family, we deduce a family of decidable winning conditions of arbitrary finite Borel complexity for games played on finite graphs. The problem of deciding the winner for these conditions is shown to be non-elementary.     

Transition between concentric or tangent circles with a single segment of PH quintic curve

The paper describes a method to join two circles with a C-shaped and an S-shaped transition curve, composed of a Pythagorean hodograph quintic segment, preserving G² continuity. It is considered desirable to have such a curve in satellite path planning, highway or railway route designing, or non-holonomic robot path planning. As an extension of our previous work, we show that a single quintic curve can be used for blending or for a transition curve between two circles, including the previously unsolved cases of concentric and tangential circles.     

A calculus of coroutines

We describe a simple but expressive calculus of sequential processes, represented as coroutines. We show that this calculus can be used to express a variety of programming language features including procedure calls, labelled jumps, integer references and stacks. We describe the operational properties of the calculus using reduction rules and equational axioms.

We describe a notion of categorical model for our calculus, and give a simple example of such a model based on a category of games and strategies. We prove full abstraction results showing that equivalence in the categorical model corresponds to observational equivalence in the calculus, and also to equivalence of evaluation trees, which are infinitary normal forms for the calculus.

We show that our categorical model can be used to interpret the untyped λ-calculus and use this fact to extract a sound translation of the latter into our calculus of coroutines.     

Third-order Idealized Algol with iteration is decidable

The problems of contextual equivalence and approximation are studied for the third-order fragment of Idealized Algol with iteration (). They are approached via a combination of game semantics and language theory. It is shown that for each -term one can construct a pushdown automaton recognizing a representation of the strategy induced by the term. The automata have some additional properties ensuring that the associated equivalence and inclusion problems are solvable in Ptime. This gives an Exptime decision procedure for the problems of contextual equivalence and approximation for β-normal terms. Exptime-hardness of the problems, even for terms without iteration, is also shown.     

Stability for first order delay dynamic equations on time scales

In this paper, we establish some sufficient conditions for the uniform stability and the uniformly asymptotical stability of the first order delay dynamic equation

where is a time scale, p(.) is rd-continuous and positive, the delay function . Our results unify the corresponding ones for differential and difference equations. To the best of our knowledge, this is the first time to discuss the asymptotical behavior of delay dynamic equations on time scales.     

Controlling the delay trade-off between packet flows using multiple reserved places

We analyse a discrete-time queueing model with packet arrivals that are either delay-sensitive (type 1) or delay-tolerant (type 2). The prominent feature of this model is its reservation-based queueing discipline, which reduces the queueing delay perceived by the 1-packets at the cost of allowing higher delays for the 2-packets. A total of N reserved places are introduced in the queue. Whenever a 1-packet enters the queue, it takes the position of the most advanced reservation and creates a new one at the end of the queue. The amount of delay differentiation between 1- and 2-packets can thus be controlled smoothly by the parameter N. We obtain the probability-generating function, the mean value and the tail distribution of the delay experienced by 1- and 2-packets.