Information-theoretic characterizations of recursive infinite strings

Loveland and Meyer have studied necessary and sufficient conditions for an infinite binary string x to be recursive in terms of the program-size complexity relative to n of its n-bit prefixes x_n. Meyer has shown that x is recursive iff ?c, ?n, K(x_n?n) ? c, and Loveland has shown that this is false if one merely stipulates that K(x_n?n) ? c for infinitely many n. We strengthen Meyer's theorem. From the fact that there are few minimal-size programs for calculating n given result, we obtain a necessary and sufficient condition for x to be recursive in terms of the absolute program-size complexity of its prefixes: x is recursive iff ?c, ?n, K(x_n) ? K(n) + c. Again Loveland's method shows that this is no longer a sufficient condition for x to be recursive if one merely stipulates that K(x_n) ? K(n) + c for infinitely many n.     

Polynomial sequences of integral type and recursive matrices

We show how the theory of recursive matrices—bi-infinite matrices in which each row can be recursively computed from the previous one—can be used to formulate a version of the umbral calculus that is also suited for the study of polynomials p(x) taking integer values when the variable x is an integer. In this way, most results of the classical umbral calculus—such as expansion theorems and closed formulas—can be seen as immediate consequences of the two main properties of recursive matrices, namely, the Product Rule and the Double Recursion Theorem.     

Two point hermite approximations for the solution of linear initial value and boundary value problems

Application of an idea originally due to Ch. Hermite allows the derivation of an approximate formula for expressing the integral ∫xixi?1y(x)dx as a linear combination of y(xi?1), y(xi), and their derivatives y(v)(xi?1) up to order v = α and y(v)(xi) up to order v = β. In addition to this integro-differential form a purely differential form of the 2-point Hermite approximation will be derived. Both types will be denoted by Hαβ-approximation. It will be shown that the well-known Obreschkoff-formulas contain no new elements compared to the much older Hαβ-method.The Hαβ-approximation will be applied to the solution of systems of ordinary differential equations of the type y'(x) = M(x)y(x) + q(x), and both initial value and boundary value problems will be treated. Function values at intermediate points x? (xi?1, xi) are obtained by the use of an interpolation formula given in this paper.An advantage of the Hαβ-method is the fact that high orders of approximation (α, β) allow an increase in step size hi. This will be demonstrated by the results of several test calculations.     

Characterization of normal forms possessing inverse in the λ-β-η-calculus

The aim of this paper is to generalize a result given by Curry and Feys, who have shown that the only regular combinators possessing inverse in the λ-β-η-calculus are the permutators, whose definition is p=λzλx₁…λx_n(zx_i1…x_in) for n?0 where i₁,…, i_r is a permutation of 1,…, n. Here we extend this characterization to the set of normal forms, showing that the only normal forms possessing inverse in the λ-βη-calculus are the “hereditarily finite permutators” (h.f.p.), whose recursive definition is: if n?0, P_j (1?j?n) are h.f.p. and i₁,…,i_n is a permutation of 1,…, n, then the normal form of P = λzλx₁…λx_n(z(P₁x_i1))… (P_nin) is an h.f.p.     

Extending separation logic with fixpoints and postponed substitution

We are interested in separation-logic-based static analysis of programs that use shared mutable data structures. In this paper, we introduce backward and forward analysis for a separation logic called BI^μν${\mathit{BI}}^{\mu \nu }$, an extension of separation logic [Ishtiaq and O’Hearn, BI as an assertion language for mutable data structures, in: POPL’01, 2001, pp. 14–26], to which we add fixpoint connectives and postponed substitution. This allows us to express recursive definitions within the logic as well as the axiomatic semantics of while statements.     

Blackwell’s Theorem for T-related fuzzy variables

In this paper, we consider Blackwell’s Theorem in which inter-arrival times are characterized as fuzzy variables under t-norm-based fuzzy operations. We first prove that Blackwell’s Theorem for T-related fuzzy variables with respect to necessity measure holds true where T is an Archimedean t-norm. Subsequently, we provide a counter example under which Blackwell’s Theorem does not hold when T = min. Finally, we evaluate the expected value of fuzzy variable with respect to credibility measure and derive fuzzy Blackwell’s Theorem based on the expected value of fuzzy variables.     

An essay on the linguistic roots of fuzzy sets

This paper mainly tries to show that the membership function of a fuzzy set labeled P does show some intrinsic property related with how P is actually managed in the universe of discourse. Its final goal is to analyze an answer to the question, which intrinsic but simple property allows a function to represent a fuzzy set labeled P? The presented property exhibits that the membership function just ‘measures’ in some scale the extent up to which x is P in language, for all x in the universe of discourse.Such study is done in a form allowing to consider how to represent the ‘collective’ originated by a predicate reflecting a collective noun. As particular cases of what is presented, and when the degrees can be some kinds of numerical subsets, the Zadeh’s fuzzy sets, the interval-valued, the intuitionistic, and the type-2 fuzzy sets, appear as particular cases and to some extent are discussed. A ‘unification’ of all different kinds of fuzzy sets based on a linguistic origin is achieved.     

On selecting thek largest with median tests

LetW _itk(n) be the minimax complexity of selecting thek largest elements ofn numbersx ₁,x ₂,...,x _n by pairwise comparisonsx _i :x _j . It is well known thatW ₂(n) =n?2+ [lgn], andW _k (n) = n + (k?1)lg n +O(1) for all fixed k ≥ 3. In this paper we studyW′ _k (n), the minimax complexity of selecting thek largest, when tests of the form “Isx _i the median of {x _i ,x _j ,x _t }?” are also allowed. It is proved thatW′₂(n) =n?2+ [lgn], andW′ _k (n) =n + (k?1)lg₂ n +O(1) for all fixedk≥3.     

Embedding hamiltonian paths in hypercubes with a required vertex in a fixed position

Assume that n is a positive integer with n?2. It is proved that between any two different vertices x and y of Qn there exists a path Pl(x,y) of length l for any l with h(x,y)?l?n²−1 and 2|(l−h(x,y)). We expect such path Pl(x,y) can be further extended by including the vertices not in Pl(x,y) into a hamiltonian path from x to a fixed vertex z or a hamiltonian cycle. In this paper, we prove that for any two vertices x and z from different partite set of n-dimensional hypercube Qn, for any vertex y∈V(Qn)−{x,z}, and for any integer l with h(x,y)?l?n²−1−h(y,z) and 2|(l−h(x,y)), there exists a hamiltonian path R(x,y,z;l) from x to z such that dR(x,y,z;l)(x,y)=l. Moreover, for any two distinct vertices x and y of Qn and for any integer l with h(x,y)?l?²n−1 and 2|(l−h(x,y)), there exists a hamiltonian cycle S(x,y;l) such that dS(x,y;l)(x,y)=l.     

Channel assignment via fast zeta transform

We show an O^?(n(?+1))-time algorithm for the channel assignment problem, where ? is the maximum edge weight. This improves on the previous O^?(n(?+2))-time algorithm by Král (2005) [1], as well as algorithms for important special cases, like L(2,1)-labeling. For the latter problem, our algorithm works in O^?(n³) time. The progress is achieved by applying the fast zeta transform in combination with the inclusion-exclusion principle.     

Eine stets quadratisch konvergente Modifikation des Steffensen-Verfahrens

It is shown that the following modification of the Steffensen procedurex _n+1=x _n ?k _s (x _n )f(x _n ) (f[x _n ,x _n ?f(x _n )])^?1 (n=0,1,...) withk _s (x)=(1?z _s (x))^?1,z _s (x)=f(x) 2f[x?f(x),x,x+f(x)]×(f[x,x?f(x)])^?2 is quadratically convergent to the root of the equation \(f(x) = (x - \bar x)^p g(x) = 0(p > 0,g(\bar x) \ne 0)\) . Furthermore \(\mathop {\lim }\limits_{n \to \infty } k_s (x_n ) = p\) holds.     

The panpositionable panconnectedness of augmented cubes

A graph G is panconnected if, for any two distinct vertices x and y of G, it contains an [x, y]-path of length l for each integer l satisfying d_G(x, y) ? l ? ∣V(G)∣ − 1, where d_G(x, y) denotes the distance between vertices x and y in G, and V(G) denotes the vertex set of G. For insight into the concept of panconnectedness, we propose a more refined property, namely panpositionable panconnectedness. Let x, y, and z be any three distinct vertices in a graph G. Then G is said to be panpositionably panconnected if for any d_G(x, z) ? l₁ ? ∣V(G)∣ − d_G(y, z) − 1, it contains a path P such that x is the beginning vertex of P, z is the (l₁ + 1)th vertex of P, and y is the (l₁ + l₂ + 1)th vertex of P for any integer l₂ satisfying d_G(y, z) ? l₂ ? ∣V(G)∣ − l₁ − 1. The augmented cube, proposed by Choudum and Sunitha [6] to be an enhancement of the n-cube Q_n, not only retains some attractive characteristics of Q_n but also possesses many distinguishing properties of which Q_n lacks. In this paper, we investigate the panpositionable panconnectedness with respect to the class of augmented cubes. As a consequence, many topological properties related to cycle and path embedding in augmented cubes, such as pancyclicity, panconnectedness, and panpositionable Hamiltonicity, can be drawn from our results.     

An upper bound on the mean-square error in the sampling expansion for non-band-limited processes

An upper bound is obtained on the mean-square error involved when a real-valued non-band-limited nonstationary random process x(t) is approximated by the sampling expansion

$\text{∑}\text{n=?∞}\text{∞}\text{x(nT)}\text{sin}\text{π(t?nT)/T}\text{π(t?nT)/T}$

for some T > 0. When the process x(t) is band-limited over [$\text{?}\text{1}\text{2T}\text{,}\text{1}\text{2T}$], this error bound reduces to zero.     

Undecidability of the first-order arithmetic A[P(x), 2x, x + 1]

It is shown that the first-order arithmetic A[P(x), 2x, x + 1] with two functions 2x, x + 1 and a monadic predicate symbol P(x) is undecidable, by using a kind of two-dimensional finite automata, called finite causal ω²-systems. From this immediately follows R.M. Robinson's result, which says that the monadic second-order theory with two functions 2x, x + 1 is undecidable. This is also considered as an improvement on H. Putnam's result about the undecidability of the first-order arithmetic with addition and a monadic predicate symbol.     

A recursive and a grammatical characterization of the exponential-time languages

We characterize the class of all languages which are acceptable in exponential time by means of recursive and grammatical methods. (i) The class of all languages which are acceptable in exponential time is uniquely characterized by the class of all (0-1)-functions which can be generated, starting with the initial functions of the Grzegorczyk-class $\text{E}$², by means of subtitution and limited recursion of the form f(x, y + 1) = h(x, y), f(x, y), f(x, l(x, y))), l(x, y) ? y. (ii) The class of all languages which are acceptable in exponential time is equal to the class of all languages generated by context-sensitive grammars with context-free control sets.     

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].     

Robust algorithms that locate local extrema of a function of one variable from interval measurement results: A remark

The problem of locating local maxima and minima of a function from approximate measurement results is vital for many physical applications: inspectral analysis, chemical species are identified by locating local maxima of the spectra; inradioastronomy, sources of celestial radio emission, and their subcomponents, are identified by locating local maxima of the measured brightness of the radio sky;elementary particles are identified by locating local maxima of the experimental curves. Since measurements are never absolutely precise, as a result of the measurements, we have aclass of possible functions. If we measuref(x _i ) with interval uncertainty, this class consists of all functionsf for whichf(x _i ) ε [y _i ??, y _i +?], wherey _i are the results of measuringf(x _i ), andε is the measurement accuracy. For this class, in [2], a linear-time algorithm was described. In real life, a measuring instrument can sometimes malfunction, leading to the so-calledoutliers, i.e., measurementsy _i that can be way offf(x _i ) (and thus do not restrict the actual valuesf(x _i ) at all). In this paper, we describerobust algorithms, i.e., algorithms that find the number of local extrema in the presence of possible outliers. These algorithms solve an important practical problem, but they are not based on any new mathematical results: they simply use algorithms from [2] and [3].     

Linear Differential Operators for Polynomial Equations

Given a squarefree polynomial P ∈ k₀[ x,y ], k₀a number field, we construct a linear differential operator that allows one to calculate the genus of the complex curve defined by P =  0 (when P is absolutely irreducible), the absolute factorization of P over the algebraic closure of k₀, and calculate information concerning the Galois group of P over ___ k₀(x) as well as overk₀ (x).     

Comments on “Modified criterion for global asymptotic stability of fixed-point state-space digital filters using two’s complement arithmetic” [Automatica 46 (2010) 475-478]

A recently reported criterion [Singh V. (2010). Modified criterion for global asymptotic stability of fixed-point state-space digital filters using two’s complement arithmetic. Automatica, 46, 475-478], which is a modified version of an earlier criterion due to Mills-Mullis-Roberts, for the global asymptotic stability of fixed-point state-space digital filters with two’s complement arithmetic is reviewed. Pertaining to second-order digital filters, it is shown that Singh’s approach will never lead to a larger overflow stability region in the parameter space as compared to that obtainable via Mills-Mullis-Roberts criterion.