On the decomposition of rational functions

Let f:=p/q∈K(x)$f:=p/q\in \mathbb{K}\left(x\right)$ be a rational function in one variable. By Lüroth’s theorem, the collection of intermediate fields K(f)?L?K(x)$\mathbb{K}\left(f\right)?\mathbb{L}?\mathbb{K}\left(x\right)$ is in bijection with inequivalent proper decompositions f=g°h$f=g°h$, with g,h∈K(x)$g,h\in \mathbb{K}\left(x\right)$ of degrees ≥2$\ge 2$. In [Alonso, Cesar, Gutierrez, Jaime, Recio, Tomas, 1995. A rational function decomposition algorithm by near-separated polynomials. J. Symbolic Comput. 19, 527–544] an algorithm is presented to calculate such a function decomposition. In this paper we describe a simplification of this algorithm, avoiding expensive solutions of linear equations. A MAGMA implementation shows the efficiency of our method. We also prove some indecomposability criteria for rational functions, which were motivated by computational experiments.     

On the revision of probabilistic beliefs using uncertain evidence

We revisit the problem of revising probabilistic beliefs using uncertain evidence, and report results on several major issues relating to this problem: how should one specify uncertain evidence? How should one revise a probability distribution? How should one interpret informal evidential statements? Should, and do, iterated belief revisions commute? And what guarantees can be offered on the amount of belief change induced by a particular revision? Our discussion is focused on two main methods for probabilistic revision: Jeffrey's rule of probability kinematics and Pearl's method of virtual evidence, where we analyze and unify these methods from the perspective of the questions posed above.     

On the limits of cache-oblivious rational permutations

Permuting a vector is a fundamental primitive which arises in many applications. In particular, rational permutations, which are defined by permutations of the bits of the binary representations of the vector indices, are widely used. Matrix transposition and bit-reversal are notable examples of rational permutations. In this paper we contribute a number of results regarding the execution of these permutations in cache hierarchies, with particular emphasis on the cache-oblivious setting. We first bound from below the work needed to execute a rational permutation with an optimal cache complexity. Then, we develop a cache-oblivious algorithm to perform any rational permutation, which exhibits optimal work and cache complexities under the tall cache assumption. We finally show that for certain families of rational permutations (including matrix transposition and bit reversal) no cache-oblivious algorithm can exhibit optimal cache complexity for all values of the cache parameters. This latter result specializes the one proved by Brodal and Fagerberg for general permutations to the case of rational permutations, and provides further evidence that the tall cache assumption is often necessary to attain cache optimality in the context of cache-oblivious algorithms.     

The role of trait emotional intelligence in gamers’ preferences for play and frequency of gaming

This paper examines the role of trait emotional intelligence (trait EI) in gamers’ preferences for play and frequency of gaming in a sample of 1051 young adult US/European gamers, who play frequently the online massively multiplayer game, World of Warcraft (WoW). Trait EI was shown to predict social and achievement preferences for play as well as frequency of gaming. In particular, trait EI was positively correlated to a preference for social practices per se and negatively correlated to a preference for achievement-oriented, instrumental practices. These findings advocate that gamers’ preferences for play are in accordance with their emotion-related personality characteristics. Trait EI was also negatively associated with frequency of gaming suggesting that lower scorers on trait EI are more likely associated with more frequent game use.     

Blind digital watermarking of rational Bézier and B-spline curves and surfaces with robustness against affine transformations and Möbius reparameterization

We present a blind watermarking scheme for rational Bézier and B-spline curves and surfaces which is shape-preserving and robust against the affine transformations and Möbius reparameterization that are commonly used in geometric modeling operations in CAD systems. We construct a watermark polynomial with real coefficients of degree four which has the watermark as the cross-ratio of its complex roots. We then multiply the numerator and denominator of the original curve or surface by this polynomial, increasing its degree by four but preserving its shape. Subsequent affine transformations and Möbius reparameterization leave the cross-ratio of these roots unchanged. The watermark can be extracted by finding all the roots of the numerator and denominator of the curve or surface: the cross-ratio of the four common roots will be the watermark. Experimental results confirm both the shape-preserving property and its robustness against attacks by affine transformations and Möbius reparameterization.     

Extension of Brzozowski’s derivation calculus of rational expressions to series over the free partially commutative monoids

We introduce an extension of the derivatives of rational expressions to expressions denoting formal power series over partially commuting variables. The expressions are purely noncommutative, however they denote partially commuting power series. The derivations (which are so-called -derivations) are shown to satisfy the commutation relations.Our main result states that for every so-called rigid rational expression, there exists a stable finitely generated submodule containing it. Moreover, this submodule is generated by what we call Words, that is by products of letters and of pure stars.Consequently this submodule is free and it follows that every rigid rational expression represents a recognizable series in . This generalizes the previously known property where the star was restricted to mono-alphabetic and connected series.     

The μ-basis of a planar rational curve—properties and computation

A moving line L(x,y;t)=0 is a family of lines with one parameter t in a plane. A moving line L(x,y;t)=0 is said to follow a rational curve P(t) if the point P(t₀) is on the line L(x,y;t₀)=0 for any parameter value t₀. A μ-basis of a rational curve P(t) is a pair of lowest degree moving lines that constitute a basis of the module formed by all the moving lines following P(t), which is the syzygy module of P(t). The study of moving lines, especially the μ-basis, has recently led to an efficient method, called the moving line method, for computing the implicit equation of a rational curve [3 and 6]. In this paper, we present properties and equivalent definitions of a μ-basis of a planar rational curve. Several of these properties and definitions are new, and they help to clarify an earlier definition of the μ-basis [3]. Furthermore, based on some of these newly established properties, an efficient algorithm is presented to compute a μ-basis of a planar rational curve. This algorithm applies vector elimination to the moving line module of P(t), and has O(n²) time complexity, where n is the degree of P(t). We show that the new algorithm is more efficient than the fastest previous algorithm [7].     

On the expressiveness of MTL in the pointwise and continuous semantics

We show that the pointwise version of the logic MTL is strictly less expressive than the continuous version, over finitewords. The proof is constructive in that we exhibit a timed language, which is definable in the continuous semantics but is not definable in the pointwise semantics.     

An improvement on the upper bounds of the magnitudes of derivatives of rational triangular Bézier surfaces

New bounds on the magnitudes of the first- and second-order partial derivatives of rational triangular Bézier surfaces are presented. Theoretical analysis shows that the proposed bounds are tighter than the existing ones. The superiority of the proposed new bounds is also illustrated by numerical tests.     

On the relation between the MXL family of algorithms and Gröbner basis algorithms

The computation of Gröbner bases remains one of the most powerful methods for tackling the Polynomial System Solving (PoSSo) problem. The most efficient known algorithms reduce the Gröbner basis computation to Gaussian eliminations on several matrices. However, several degrees of freedom are available to generate these matrices. It is well known that the particular strategies used can drastically affect the efficiency of the computations. In this work, we investigate a recently-proposed strategy, the so-called “Mutant strategy”, on which a new family of algorithms is based (MXL, MXL₂ and MXL₃). By studying and describing the algorithms based on Gröbner basis concepts, we demonstrate that the Mutant strategy can be understood to be equivalent to the classical Normal Selection Strategy currently used in Gröbner basis algorithms. Furthermore, we show that the “partial enlargement” technique can be understood as a strategy for restricting the number of S-polynomials considered in an iteration of the _F4$F_4$ Gröbner basis algorithm, while the new termination criterion used in MXL₃ does not lead to termination at a lower degree than the classical Gebauer–Möller installation of Buchberger’s criteria. We claim that our results map all novel concepts from the MXL family of algorithms to their well-known Gröbner basis equivalents. Using previous results that had shown the relation between the original XL algorithm and _F4$F_4$, we conclude that the MXL family of algorithms can be fundamentally reduced to redundant variants of _F4$F_4$.     

Recall and Reasoning—an information theoretical model of cognitive processes

Cognitive Psychology studies humans’ capabilities to memorize and recall knowledge and images, among others. Connectionistic, propositional and conceptual models are a means to survey these phenomenons. This paper proposes an information theoretical network for simulating stimulus and response in categorical structures. A stimulus triggers an information flow throughout the whole network and generates for all ideas representing vertices an impact in the information theoretical unit [bit], thus measuring the recall intensity and producing a response. The method is shown to yield results of high performance even for complex taxonomies and connectionistic models. Reasoning is the logical counterpart of recall. Once an idea is associated with a stimulus, logical dependencies between both must be established, if required. Information theoretical networks allow to switch between a recall mode and a reasoning mode, also permitting logical reasoning within the same framework. Both capabilities are demonstrated by suitable examples.     

μ-Bases and singularities of rational planar curves

We provide a technique to detect the singularities of rational planar curves and to compute the correct order of each singularity including the infinitely near singularities without resorting to blow ups. Our approach employs the given parametrization of the curve and uses a μ-basis for the parametrization to construct two planar algebraic curves whose intersection points correspond to the parameters of the singularities including infinitely near singularities with proper multiplicity. This approach extends Abhyankar's method of t-resultants from planar polynomial curves to rational planar curves. We also derive the classical result that for a rational planar curve of degree n the sum of all the singularities with proper multiplicity is (n−1)(n−2)/2. Examples are provided to flesh out our results.     

On conditional diagnosability and reliability of the BC networks

An n-dimensional bijective connection network (in brief, BC network), denoted by X _n , is an n-regular graph with 2 ⁿ nodes and n2 ^n?1 edges. Hypercubes, crossed cubes, twisted cubes, and Möbius cubes all belong to the class of BC networks (Fan and He in Chin. J. Comput. 26(1):84–90, [2003]). We prove that the super connectivity of X _n is 2n?2 for n≥3 and the conditional diagnosability of X _n is 4n?7 for n≥5. As a corollary of this result, we obtain the super connectivity and conditional diagnosability of the hypercubes, twisted cubes, crossed cubes, and Möbius cubes.     

The future refereeing process in Cyberspace of the Data & Knowledge Engineering Journal: an attempt in guaranteeing security and privacy on three levels

The refereeing process for the Data & Knowledge Engineering Journal as it is and will be executed in Cyberspace is the subject of this paper, in particular security and privacy aspects. This process can be defined and implemented in the Mokum system; we will show that it complies to the security and privacy rules on three levels:

1. Highest: at the conceptual level.

2. Middle: at the implementational level.

3. Lowest: at the communicational level.

     

On the declarative and procedural semantics of deductive object-oriented systems

We present declarative and procedural semantics for a deductive object-oriented language, Gulog. The declarative semantics is based on preferred minimal models. We describe both bottom-up and top-down query evaluation procedures and show that they are sound with respect to the declarative semantics. The results contribute to our understanding of the interaction of inheritance, overriding and deduction in the presence of both functional and set-valued methods, and multiple inheritance.     

On the analysis of cooperation and antagonism in networks of communicating processes

We propose a new method for the analysis of cooperative and antagonistic properties of communicating finite state processes (FSPs). This algebraic technique is based on a composition operator and on the notion of possibility equivalence among FSPs. We demonstrate its utility by showing that potential blocking, termination, and lockout can be decided in polynomial time for loosely connected networks of tree FSPs. Potential blocking and termination are examples of cooperative properties, while lockout is an antagonistic one. For loosely connected networks of (the more general) acyclic FSPs, the cooperative properties become NP-complete and the antagonistic ones PSPACE-complete. For tightly coupled networks of tree FSPs, we also have NP-completeness for the cooperative properties. For the harder case of FSPs with cycles, we provide a natural extension of the method.A preliminary version of this paper appeared as an extended abstract in theProceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing, August, 1985, pp. 23–38. P. C. Kanellakis was supported by ONR-DARPA Grant N00014-83-K-0146, NSF Grant DCR-8302391, and by the Office of Army Research under contract DAAG29-84-K-0058. S. A. Smolka was supported by National Science Foundation Grant DCR-8505873.     

Optimized implementations of rational approximations—a case study on the Voigt and complex error function

Rational functions are frequently used as efficient yet accurate numerical approximations for real and complex valued special functions. For the complex error function w(x+iy), whose real part is the Voigt function K(x,y), the rational approximation developed by Hui, Armstrong, and Wray [Rapid computation of the Voigt and complex error functions, J. Quant. Spectrosc. Radiat. Transfer 19 (1978) 509-516] is investigated. Various optimizations for the algorithm are discussed. In many applications, where these functions have to be calculated for a large x grid with constant y, an implementation using real arithmetic and factorization of invariant terms is especially efficient.