Combinatorics on words in symbolic dynamics: The quadratic map

This paper is contributed to the combinatorial properties of the MSS sequences, which are the periodic kneading words of quadratic maps defined on a interval. An explicit expression of adjacency relations on MSS sequences of given lengths is established.     

Super-visible codes

Upper bounds and constructions are given for super-visible codes. These are linear codes with the property that all words of minimum weight form a basis of the code. Optimal super-visible codes are summarized for small lengths and minimum distances.     

Generating and counting valid patterns in routes between two points

Given two points on a plane, any rectilinear route between them can be specified by directions and lengths of constituent line segments. A word (pattern) over the alphabetN, E, S, andW is defined to represent a sequence of directions. The length of each line segment is ignored. In this paper we characterize and count all valid words, that is, those words representing non-selfcrossing routes.Notation V _n The set of all valid words of lengthn. - P ⁿ The set of all words of lengthn.     

Length computation of matrix subalgebras of special type

Let {ie910-01} be a field and let {ie910-02} be a finite-dimensional {ie910-03}-algebra. We define the length of a finite generating set of this algebra as the smallest number k such that words of length not greater than k generate {ie910-04} as a vector space, and the length of the algebra is the maximum of the lengths of its generating sets. In this article, we give a series of examples of length computation for matrix subalgebras. In particular, we evaluate the lengths of certain upper triangular matrix subalgebras and their direct sums, and the lengths of classical commutative matrix subalgebras. The connection between the length of an algebra and the lengths of its subalgebras is also studied. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 13, No. 4, pp. 165–197, 2007.     

The entropies and periods of renewal systems

In this work the set of entropies of shifts of finite type is proved to be the same as the set of entropies of renewal systems that are shifts of finite type. The period of a finite set of words is the greatest common divisor of the lengths of the words. We show that the period of a renewal system as a shift space and the minimum of the periods of its generating sets coincide when the system is of finite type or mixing. This work was supported by grant No.R04-2004-000-10157-0 from the Basic Research Program of the Korea Research Foundation.     

Palindromic prefixes and episturmian words

Let w be an infinite word on an alphabet A. We denote by (ni)_i?1 the increasing sequence (assumed to be infinite) of all lengths of palindromic prefixes of w. In this text, we give an explicit construction of all words w such that ni+1?2ni+1 for all i, and study these words. Special examples include characteristic Sturmian words, and more generally standard episturmian words. As an application, we study the values taken by the quantity lim supni+1/ni, and prove that it is minimal (among all nonperiodic words) for the Fibonacci word.     

The Distribution of the Rational Points on the Unit Circle

In the paper, the explicit form of distribution function for the lengths of arcs connecting neighbouring rational points on the unit circle whose denominators do not exceed given value, is given.     

Classification of matrix subalgebras of length 1

We define the length of a finite system of generators of a given algebra $ \mathcal{A} $ as the smallest number k such that words of length not greater than k generate $ \mathcal{A} $ as a vector space, and the length of the algebra is the maximum of the lengths of its systems of generators. In this paper, we obtain a classification of matrix subalgebras of length 1 up to conjugation. In particular, we describe arbitrary commutative matrix subalgebras of length 1, as well as those that are maximal with respect to inclusion.     

On the three diagonals of a cyclic quadrilateral

If the side lengths of a non-degenerate cyclic quadrilateral are given, but not necessarily in cyclic order, then three diagonal lengths arise in the resulting three cyclic quadrilaterals, just as three possible pairs of supplementary angles arise as opposite vertices, and where the diagonals intersect, in each of the three configurations. We obtain a formula for the sum of the lengths of the three diagonals minus the sum of the four sides which enables us to deduce the geometric inequality that the sum of the side lengths is less than the sum of the lengths of the three diagonals. We obtain another formula when these lengths are replaced by their squares, and this yields a similar inequality. A proof of both formulas is given which uses algebraic geometry, but which proceeds by analysis of degenerate situations. Two alternative proofs of the linear version of the inequality (which implies the quadratic version) are supplied which use trigonometry and Lagrange multipliers respectively. An unusual feature of these results is that they refer not to one configuration, but rather concern three possible configurations.     

A linear time algorithm for Shortest Cyclic Cover of Strings

Merging words according to their overlap yields a superstring. This basic operation allows to infer long strings from a collection of short pieces, as in genome assembly. To capture a maximum of overlaps, the goal is to infer the shortest superstring of a set of input words. The Shortest Cyclic Cover of Strings (SCCS) problem asks, instead of a single linear superstring, for a set of cyclic strings that contain the words as substrings and whose sum of lengths is minimal. SCCS is used as a crucial step in polynomial time approximation algorithms for the notably hard Shortest Superstring problem, but it is solved in cubic time. The cyclic strings are then cut and merged to build a linear superstring. SCCS can also be solved by a greedy algorithm. Here, we propose a linear time algorithm for solving SCCS based on a Eulerian graph that captures all greedy solutions in linear space. Because the graph is Eulerian, this algorithm can also find a greedy solution of SCCS with the least number of cyclic strings. This has implications for solving certain instances of the Shortest linear or cyclic Superstring problems.     

On Vectors whose Span Contains a Given Linear Subspace

Estimates are given for the product of the lengths of integer vectors spanning a given linear subspace.     

The inverse spectral problem for a Stieltjes eight-shaped string

We consider a spectral problem generated by the Stieltjes string equation on a metric figure-of-eight graph and the corresponding inverse problem which is stated as follows. Values of the point masses located on one of the loops and the lengths of subintervals on it are given together with the spectrum of the spectral problem on the whole graph, the total length of the second loop and the length of the first subinterval on it, and a certain constant. Values of the masses and the lengths of subintervals on the second loop are to be found. Conditions sufficient for such a problem to be solvable are given in the implicit form. An algorithm for recovering the masses and the subintervals on the second loop is proposed.     

Inverse <Emphasis Type="Italic">p</Emphasis>-median problems with variable edge lengths

The inverse p-median problem with variable edge lengths on graphs is to modify the edge lengths at minimum total cost with respect to given modification bounds such that a prespecified set of p vertices becomes a p-median with respect to the new edge lengths. The problem is shown to be strongly NP{\mathcal{NP}}-hard on general graphs and weakly NP{\mathcal{NP}}-hard on series-parallel graphs. Therefore, the special case on a tree is considered: It is shown that the inverse 2-median problem with variable edge lengths on trees is solvable in polynomial time. For the special case of a star graph we suggest a linear time algorithm.     

The Steiner ratio of several discrete metric spaces

Steiner's Problem is the “Problem of shortest connectivity”, that means, given a finite set of points in a metric space (X,ρ), search for a network interconnecting these points with minimal length. This shortest network must be a tree and is called a Steiner Minimal Tree (SMT). It may contain vertices different from the points which are to be connected. Such points are called Steiner points. If we do not allow Steiner points, that means, we only connect certain pairs of the given points, we get a tree which is called a Minimum Spanning Tree (MST). Steiner's Problem is very hard as well in combinatorial as in computational sense, but, on the other hand, the determination of an MST is simple. Consequently, we are interested in the greatest lower bound for the ratio between the lengths of these both trees:

which is called the Steiner ratio (of (X,ρ)). We look for estimates and exact values for the Steiner ratio in several discrete metric spaces. Particularly, we determine the Steiner ratio for spaces of words, and we estimate the Steiner ratio for specific graphs.     

Inlet length by laminar flow of elastico-viscous liquids through straight channel and circular tube

The inlet lengths in a straight channel and a circular tube by the laminar flow of an elastico-viscous liquid have been determined in this paper. Expressions for the inlet lengths have been obtained by the kinetic energy end correction method. For a given pressure drop, the elasticity of the liquid increases the inlet length only if the liquid possesses cross-viscosity. But cross-viscosity which decreases the inlet length has an independent effect on it.     

The one-dimensional cutting stock problem with due dates

The one-dimensional cutting stock problem is the problem of cutting stock material into shorter lengths, in order to meet demand for these shorter lengths while minimizing waste. In industrial cutting operations, it may also be necessary to fill the orders for these shorter lengths before a given due date. We propose new optimization models and solution procedures which solve the cutting stock problem when orders have due dates. We evaluate our approach using data from a large manufacturer of reinforcement steel and show that we are able to solve industrial-size problems, while also addressing common cutting considerations such as aggregation of orders, multiple stock lengths and cutting different types of material on the same machine. In addition, we evaluate operational performance in terms of resulting waste and tardiness of orders using our model in a rolling horizon framework.     

A defect property of codes with unbounded delays

We show that if the code C with n words has unbounded delay in both directions then there exist n − 2 words such that the words of C are products of these words. Some other conditions which guarantee the same property are given.     

Generalizations of the Goulden–Jackson cluster method

We give several modifications of the Goulden–Jackson cluster method for finding generating functions for words avoiding a given set of forbidden words. Our modifications include functions which can take into account various ‘weights’ on words, including single letter probability distributions, double letter (i.e. pairwise) probability distributions, and triple letter probability distributions. We also describe an alternative, recursive approach to finding such generating functions. We describe Maple implementations of the various modifications. The accompanying Maple package is available at the website for this paper.     

多机器人协调吊运系统逆运动学分析及优化

针对紧耦合多机器人协调吊运系统的逆运动学问题进行了分析,首先利用几何关系和力旋量平衡方程建立了系统的运动学模型和动力学模型;然后对系统的逆运动学进行分析,将其分为变柔索长度和固定柔索长度两种情况分别进行分析;随后对运动学逆解在某一时刻存在无穷多解、多组解和无解的情况分别给出了解决方法,对存在多组解的情况,提出一优化目标求解最优解;最后结合软件UG/ADAMS/MATLAB建立了系统的实验平台,通过实例仿真计算验证了方法的有效性,为后续进一步研究系统运动稳定性、优化拉力分布和控制算法奠定了基础.     

How to determine a partition up to conjugation using multisets of hook lengths

If two partitions are conjugate, their multisets of hook lengths are the same. Then one may wonder whether the multiset of hook lengths of a partition determines a partition up to conjugation. The answer turns out to be no. However, we may add an extra condition under which a given multiset of hook lengths determines a partition uniquely up to conjugation. Herman-Chung, and later Morotti found such a condition. We give an alternative proof of Morotti’s theorem and generalize it.