Extended Games–Chan algorithm for the 2-adic complexity of FCSR-sequences

Binary sequences generated by feedback shift registers with carry operation (FCSR) share many of the important properties enjoyed by sequences generated by linear feedback shift registers. We present an FCSR analog of the (extended) Games–Chan algorithm, which efficiently determines the linear complexity of a periodic binary sequence with period length T = 2ⁿ or pⁿ, where p is an odd prime and 2 is a primitive element modulo p². The algorithm to be presented yields an upper bound for the 2-adic complexity, an FCSR analog of the linear complexity, of a pⁿ-periodic binary sequence.     

On some dynamical subsets of the rauzy fractal

Let ( ,(+1)_n) be the adic system associated to the substitution: 1 → 12,…,(n − 1) → 1n, n → 1. In Sirvent (1996) it was shown that there exist a subset Cⁿ of and a map h_n: C → Cⁿ such that the dynamical system (C, h_n) is semiconjugate to ( ). In this paper we compute the Hausdorff and Billingsley dimensions of the geometrical realizations of the set Cⁿ on the (n− l)-dimensional torus. We also show that the dynamical system (Cⁿ,h_n) cannot be realized on the (n − 1)-torus.     

Confluent general-factorial difference and derivative operators and polynomial-exponential interpolation

A previous application of the Newton divided difference series of the displacement function E^z = (1 + Δ)^z = e ^Dz, where the operators Δ and D are the variables, to purely exponential interpolation employing general-factorial differences and derivatives, {Pi;^m_i=0 (Δ - S_i)}f(0) and {Pi;^m_i=0 (D - t_i)}f(0), in which the s_i's and t_i's are distinct[1], is here extended to mixed polynomial-exponential interpolation where the s_i's and t_i's are no longer distinct.     

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.     

Constructing space-filling curves of compact connected manifolds

Let M be a compact connected (topological) manifold of finite- or infinite-dimension n. Let 0 r 1 be arbitrary but fixed. We construct in this paper a space-filling curve f from [0,1] onto M, under which M is the image of a compact set A of Hausdorff dimension r. Moreover, the restriction of f to A is one-to-one over the image of a dense subset provided that 0 r log|2ⁿ/log(2ⁿ + 2). The proof is based on the special case where M is the Hilbert cube [0,1]^ω.     

Uniqueness theorems on meromorphic functions sharing one value

In this paper, we study with a weighted sharing method the uniqueness problem of [fⁿ(z)]^(k) and [gⁿ(z)]^(k) sharing one value and obtain some results which extend the theorems given by M. Fang, S. Bhoosnurmath and S. Dyavanal et al.     

Repetitiveness of languages generated by morphisms

We study the repetition of subwords in languages generated by morphisms. Fundamental to our approach is the notion of quasi-repetitive elements. Using these elements we present a new characterization for repetitive morphisms, from which we derive a simple proof for the fact that a D0L-language is repetitive if and only if it is strongly repetitive (Ehrenfeucht and Rozenberg, Inform. and Control 59 (1983) 13–35). From this proof we obtain a structurally simple polynomial-time algorithm for deciding whether such a language is repetitive. From further results on quasi-repetitive elements we obtain as a consequence a complete characterization for all those morphisms on a two-letter alphabet that are repetitive, a result which is closely related to a result of Séébold (Bull. EATCS 36 (1988) 137–151) on the D0L periodicity problem. Finally, we characterize those morphisms f on a two-letter alphabet, for which the language L(f) generated by f or the language SL(f) of subwords of L(f) are context-free or even regular.     

A note on discrete-time positive realizations

A discrete-time positive linear system has the property that any nonnegative initial state and any nonnegative input produces a nonnegative trajectory in the state space and output for all time. Such systems are Rⁿ⁺-reachable if every state of the nonnegative orthant Rⁿ⁺ is reachable from origin with a nonnegative input function, in a finite-time interval. A simple necessary and sufficient condition for Rⁿ⁺-realizability, i.e. for the existence of a nonnegative realization that is also Rⁿ⁺-reachable, is stated. The realization procedure is straightforward.     

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.     

On the error in Padé approximations for functions defined by Stieltjes integrals

Consdier I(z) = ∫^b_a w(t)f(t, z) dt, f(t, z) = (1 + t/z)⁻¹. It is known that generalized Gaussian quadrature of I(z) leads to approximations which occupy the (n, n + r − 1) positions of the Padé matrix table for I(z). Here r is a positive integer or zero. In a previous paper the author developed a series representation for the error in Gaussian quadrature. This approach is now used to study the error in the Padé approximations noted. Three important examples are treated. Two of the examples are generalized to the case where f(t, z) = (1 + t/z)^−v.     

Computation of eigenpairs of Ax = γBx for vibrations of spinning deformable bodies

It is shown that, when linear theory is used, the general eigenvalue problem related with the free vibrations of spinning deformable bodies is of the type Ax = γBx, where A is Hermitian, and B is real positive definite. Since the order n of the matrices may be large, and A and B are banded or block banded, due to the economics of the numerical solution, one is interested in obtaining only those eigenvalues which fall within the frequency band of interest of the problem. The paper extends the well known method of bisections and iteration of Rⁿ to n dimensional complex spaces, i.e. to Cⁿ, so that it can be applied to the present problem.     

C interpolation on smooth manifolds with one-parameter transformations

This paper presents a method for Cⁿ interpolation on smooth manifolds by performing one-parameter transformations on them. Continuity of interpolating curves is achieved by smooth transitions between the transformations. Interpolating curves have local control. Constructing of curves on quadrics, SO(3, R) and GL(3, R) is considered.     

On factorization forests of finite height

Simon (Theoret. Comput. Sci. 72 (1990) 65–94) has proved that every morphism from a free semigroup to a finite semigroup S admits a Ramseyan factorization forest of height at most 9|S|. In this paper, we prove the same result of Simon with an improved bound of 7|S|. We provide a simple algorithm for constructing a factorization forest. In addition, we show that the algorithm cannot be improved significantly. We give examples of semigroup morphism such that any Ramseyan factorization forest for the morphism would require a height not less than |S|.     

Polyhedral perturbations that preserve topological form

The idea, that we are willing to accept variation in an object but that we insist it should retain its original topological form, has powerful intuitive appeal, and the concept appears in many applied fields. Some of the most important of these are tolerancing and metrology, solid modeling, engineering design, finite element analysis, surface reconstruction, computer graphics, path planning in robotics, fairing procedures, image analysis, and medical imaging. In this paper we focus on the field of tolerancing and metrology. The requirement that two objects or sets should have the same topological form requires a precise definition. We specify “same topological form” to mean that there exists a “space homeomorphism” from R³ onto R³ that carries a nominal object S onto another design object. In general, establishing the existence of such space homeomorphisms can be considerably more difficult than demonstrating classical topological equivalence by a homeomorphism. In the special case when the boundary of S is a polyhedral two-sphere in R³, one of the authors has previously given a simple sufficient condition for the existence of a space homeomorphism mapping S onto another design object. This paper presents an analogous sufficient condition for the case when S is a finite polyhedron in R³. The result relies upon a triangulation of the boundary and upon a dependent parameter that specifies the maximum size of permissible perturbations of the vertices of the polyhedron.     

Combinatorial lower bounds for secret sharing schemes

In a perfect secret sharing scheme, it holds that , where S denotes the secret and denotes the set of the share of user i. On the other hand, it is well known that if S is not uniformly distributed, where denotes the set of secrets. In this case, . Then, which is bigger, or We first prove that for any distribution on S by using a combinatorial argument. This is a more sharp lower bound on for not uniformly distributed S. Our proof makes it intuitively clear why must be so large. Next, we extend our technique to show that max_i for some access structure.     

Nonnegative solutions of singular boundary value problems with sign changing nonlinearities

The paper presents sufficient conditions for the existence of positive solutions of the equation x″(t) + q(t)f(t,x(t),x′(t)) = 0 with the Dirichlet conditions x(0) = 0, x(1) = 0 and of the equation (p(t)x′(t))′ + p(t)q(t)f(t,x(t),p(t)x′(t)) = 0 with the boundary conditions lim_t→o⁺ p(t)x′(t) = 0, x(1) = 0. Our nonlinearity f is allowed to change sign and f may be singular at x = 0. The proofs are based on a combination of the regularity and sequential techniques and the method of lower and upper functions.     

A novel solution for maze traversal problems using artificial neural networks

In this paper we have addressed the problem of finding a path through a maze of a given size. The traditional ways of finding a path through a maze employ recursive algorithms in which unwanted or non-paths are eliminated in a recursive manner. Neural networks with their parallel and distributed nature of processing seem to provide a natural solution to this problem. We present a biologically inspired solution using a two level hierarchical neural network for the mapping of the maze as also the generation of the path if it exists. For a maze of size S the amount of time it takes would be a function of S (O(S)) and a shortest path (if more than one path exists) could be found in around S cycles where each cycle involves all the neurons doing their processing in a parallel manner. The solution presented in this paper finds all valid paths and a simple technique for finding the shortest path amongst them is also given. The results are very encouraging and more applications of the network setup used in this report are currently being investigated. These include synthetic modeling of biological neural mechanisms, traversal of decision trees, modeling of associative neural networks (as in relating visual and auditory stimuli of a given phenomenon) and surgical micro-robot trajectory planning and execution.     

Theories of contact specified by connection matrices

We begin by characterizing notions of geometric continuity represented by connection matrices. Next we present a set of geometric properties that must be satisfied by all reasonable notions of geometric continuity. These geometric requirements are then reinterpreted as an equivalent collection of algebraic constraints on corresponding sets of connection matrices. We provide a general technique for constructing sets of connection matrices satisfying these criteria and apply this technique to generate many examples of novel notions of geometric continuity. Using these constraints and construction techniques, we show that there is no notion of geometric continuity between reparametrization continuity of order 3, (G³), and Frenet frame continuity of order 3, (F³); that there are several notions of geometric continuity between G⁴ and F⁴; and that the number of different notions of geometric continuity between Gⁿ and Fⁿ grows at least exponentially with n.     

Heaps and heapsort on secondary storage

A heap structure designed for secondary storage is suggested that tries to make the best use of the available buffer space in primary memory. The heap is a complete multi-way tree, with multi-page blocks of records as nodes, satisfying a generalized heap property. A special feature of the tree is that the nodes may be partially filled, as in B-trees. The structure is complemented with priority-queue operations insert and delete-max. When handling a sequence of S operations, the number of page transfers performed is shown to be O(∑_{i = 1}^S(1/P) log_(M/P)(N_i/P)), where P denotes the number of records fitting into a page, M the capacity of the buffer space in records, and N_i, the number of records in the heap prior to the ith operation (assuming P 1 and S> M c · P, where c is a small positive constant). The number of comparisons required when handling the sequence is O(∑_{i = 1}^S log₂ N_i). Using the suggested data structure we obtain an optimal external heapsort that performs O((N/P) log_(M/P)(N/P)) page transfers and O(N log₂ N) comparisons in the worst case when sorting N records.     

On the sensitivity of camera calibration

The orientation position errors of an object's coordinate frame are determined when the offset of image centre and lens distortion are not included in the calibration process. The orientation and position errors are [(u₀)² + (v₀)²]^0.5/f and [(u²₀+v²₀)T²_z + (u²₀T²_z + v²₀T_y²)]^0.5/f, respectively, where f is the focal length, (u₀, v₀) is the offset of image centre and (T_x T_y T_z) is the position of an object. We also obtain the following conclusions: (a) The offset of image centre has little effect on the determinations of the position and orientation of a coordinate frame; (b) the lens distortion will not dramatically change the position and orientation of a coordinate frame; (c) the scale factor has a great effect on the position of a coordinate frame, and on the accuracy of measurement; (d) the offset of image centre is more sensitive than the lens distortion on the determinations of the position and orientation of a coordinate frame. Finally, some experimental results are given to demonstrate the theoretical analysis given in this paper.