Coherent confluence modulo relations and double groupoids

A coherent presentation of an n-category is a presentation by generators, relations and relations among relations. Confluent and terminating rewriting systems generate coherent presentations, whose relations among relations are defined by confluence diagrams of critical branchings. This article introduces a procedure to compute coherent presentations when the rewrite relations are defined modulo a set of axioms. Our coherence results are formulated using the structure of n-categories enriched in double groupoids, whose horizontal cells represent rewriting paths, vertical cells represent the congruence generated by the axioms and square cells represent coherence cells induced by diagrams of confluence modulo. We illustrate our constructions on rewriting systems modulo commutation relations in commutative monoids, isotopy relations in pivotal monoidal categories, and inverse relations in groups.     

A term rewriting characterization of the functions computable in polynomial space

We give a term rewriting characterization of the polyspace functions. Our work follows investigations on term rewriting characterizations of some classes of (sub-) recursive functions as initiated by Cichon and Weiermann [4] and continued by Beckmann and Weiermann [1]. The main novelty of this paper is a technique for reformulating recursion schemes. The aim of this technique is to provide rewriting rules which give rise to rewriting chains whose terms are suitably bounded. This bounding is crucial when dealing with computational classes with space constraints. Received: 14 December 1998 / Published online: 12 December 2001     

Rewriting Systems and Geometric Three-Manifolds

The fundamental groups of most (conjecturally, all) closed three-manifolds with uniform geometries have finite complete rewriting systems. The fundamental groups of a large class of amalgams of circle bundles also have finite complete rewriting systems. The general case remains open.     

More efficient left-to-right matching for overlapping pattern

Pattern matching is a fundamental feature in many applications such as functional programming, logic programming, theorem proving, term rewriting and rule-based expert systems. Usually, patterns are pre-processed into a deterministic finite automaton. Using such an automaton allows one to determine the matched pattern(s) by a single scan of the input term. The matching automaton is typically based on left-to-right traversal of patterns. In this paper, we propose a method to build such an automaton. Then, we propose an incremental method to build a deterministic concise automaton for non-necessarily sequential rewriting systems. With ambiguous patterns a subject term may be an instance of more than one pattern. To select the pattern to use, a priority rule is usually engaged. The pre-processing of the patterns adds new patterns, which are instances of the original ones. When the original patterns are ambiguous, some of the instances supplied may be irrelevant for the matching process. They may cause an unnecessary increase in the space requirements of the automaton and may also reduce the time efficiency of the matching process. Here, we devise a new pre-processing operation that recognises and avoids such irrelevant instances. Hence improves space and time requirements for the matching automaton.     

关于两类具有不同基函数的标准模糊系统逼近精度问题的研究

在标准模糊系统的基础上提出了以正规二次多项式和正规三角函数为基函数的两类标准模糊系统.通过采用数值分析中的余项与辅助函数方法,对这两类模糊系统进行了误差精度的分析,给出了从SISO到MISO的误差界公式.同时,对这两类模糊系统误差界进行了比较,指出了两类模糊系统的优劣.最后,通过算例验证了理论结果的正确性.     

Control Synthesis for Čaplygin Polynomial Systems

This paper discusses new control synthesis for certain cascade type polynomial systems addressed in the paper as aplygin systems. A numerical control synthesis as well as characterization of reachability set are presented. The results of the paper are important for various branches of system theory, where the control synthesis is concerned.     

Hopf Cyclicity of a Class of Li\'{e}nard-Type Systems

The Hopf cyclicities of some smooth polynomial, rational polynomial and piecewise smooth Li\''{e}nard systems are studied. For two Li\''{e}nard systems with the same damping term and different restoring (or potential) terms, we provide sufficient conditions that the two systems have the same Hopf cyclicity. Then, some examples are given to illustrate the efficiency and applicability of our results.     

信号处理中一类非线性方程组的快速求解

在声纳和雷达信号处理中,需要求解一类维数可变的非线性方程组,这类方程组具有混合三角多项式方程组形式.由于该问题有很多解,且其对应的最小二乘问题有很多局部极小点,用牛顿法等传统的迭代法很难找到有物理意义的解.若把它化为多项式方程组,再用解多项式方程组的符号计算方法或现有的同伦方法求解,由于该问题规模太大而不能在规定的时间内求解,而当考虑的问题维数较大时,利用已有的方法甚至根本无法求解.综合利用我们提出的解混合三角多项式方程组的混合同伦方法和保对称的系数参数同伦方法,我们给出该类问题一种有效的求解方法.利用这种方法,可以达到实时求解的目的,满足实际问题的需要.     

Resonance and marginal instability of switching systems

We analyze the so-called Marginal Instability of linear switching systems, both in continuous and discrete time. This is a phenomenon of unboundedness of trajectories when the Lyapunov exponent is zero. We disprove two recent conjectures of Chitour, Mason and Sigalotti (2012) stating that for generic systems, the resonance is sufficient for marginal instability and for polynomial growth of the trajectories. The concept of resonance originated with the same authors is modified. A characterization of marginal instability under some mild assumptions on the system is provided. These assumptions can be verified algorithmically and are believed to be generic. Finally, we analyze possible types of fastest asymptotic growth of trajectories. An example of a marginally unstable pair of matrices with non-polynomial growth is given.     

Termination orders for three-dimensional rewriting

This paper studies 3-polygraphs as a framework for rewriting on two-dimensional words. A translation of term rewriting systems into 3-polygraphs with explicit resource management is given, and the respective computational properties of each system are studied. Finally, a convergent 3-polygraph for the (commutative) theory of Z/2Z-vector spaces is given. In order to prove these results, it is explained how to craft a class of termination orders for 3-polygraphs.     

A generalization of the inertia theorem for quadratic matrix polynomials

We show that the inertia of a quadratic matrix polynomial is determined in terms of the inertia of its coefficient matrices if the leading coefficient is Hermitian and nonsingular, the constant term is Hermitian, and the real part of the coefficient matrix of the first degree term is definite. In particular, we prove that the number of zero eigenvalues of such a matrix polynomial is the same as the number of zero eigenvalues of its constant term. We also give some new results for the case where the real part of the coefficient matrix of the first degree term is semidefinite.     

On Bombieri's asymptotic sieve

We improve the error term in the Bombieri asymptotic sieve when the summation is restricted to integers having at most two prime factors. This results in a refined bilinear decomposition for the characteristic function of the primes that enables us to get a best possible estimate for the trigonometric polynomial over primes.     

Convergence of Stochastic Particle Systems Undergoing Advection and Coagulation

The convergence of stochastic particle systems representing physical advection, inflow, outflow, and coagulation is considered. The problem is studied on a bounded spatial domain such that there is a general upper bound on the residence time of a particle. The laws on the appropriate Skorohod path space of the empirical measures of the particle systems are shown to be relatively compact. The paths charged by the limits are characterised as solutions of a weak equation restricted to functions taking the value zero on the outflow boundary. The limit points of the empirical measures are shown to have densities with respect to Lebesgue measure when projected on to physical position space. In the case of a discrete particle type space a strong form of the Smoluchowski coagulation equation with a delocalised coagulation interaction and an inflow boundary condition is derived. As the spatial discretisation is refined in the limit equations, the delocalised coagulation term reduces to the standard local Smoluchowski interaction.     

时间可逆系统的等时中心问题

若在中心附近的闭轨线都具有相同的周期,则此中心称为等时中心. 时间可逆多项式系统的等时中心问题是一类公开问题. 为了构造性地解决这一难题,讨论一类范围更广的时间可逆解析动力系统, 给出相应横截交换系统的递推公式,此公式可以用于等时中心条件的推导. 在递推公式的基础上,以吴特征集方法为工具,给出一类时间可逆三次系统具有横截交换系统的充要条件.     

切换多项式非线性系统的输入-状态稳定性

利用耗散不等式研究了切换多项式非线性系统的输入-状态稳定性分析问题,在任意切换信号下,给出了使得切换多项式非线性系统输入-状态稳定的充分条件.采用平方和分解方法来寻找切换多项式非线性系统的输入-状态稳定共同Lyapunov函数.数值算例验证了所提方法的可行性.     

Energy decay for Timoshenko systems of memory type

Linear systems of Timoshenko type equations for beams including a memory term are studied. The exponential decay is proved for exponential kernels, while polynomial kernels are shown to lead to a polynomial decay. The optimality of the results is also investigated.     

Randomized Preprocessing of Homogeneous Linear Systems of Equations

Our randomized preprocessing enables pivoting-free and orthogonalization-free solution of homogeneous linear systems of equations. In the case of Toeplitz inputs, we decrease the estimated solution time from quadratic to nearly linear, and our tests show dramatic decrease of the CPU time as well. We prove numerical stability of our approach and extend it to solving nonsingular linear systems, inversion and generalized (Moore-Penrose) inversion of general and structured matrices by means of Newton’s iteration, approximation of a matrix by a nearby matrix that has a smaller rank or a smaller displacement rank, matrix eigen-solving, and root-finding for polynomial and secular equations and for polynomial systems of equations. Some by-products and extensions of our study can be of independent technical intersest, e.g., our extensions of the Sherman-Morrison-Woodbury formula for matrix inversion, our estimates for the condition number of randomized matrix products, and preprocessing via augmentation.     

Linearizability of planar polynomial Hamiltonian systems

Isochronicity and linearizability of two-dimensional polynomial Hamiltonian systems are revisited and new results are presented. We give a new computational procedure to obtain the necessary and sufficient conditions for the linearization of a polynomial system. Using computer algebra systems we provide necessary and sufficient conditions for linearizability of Hamiltonian systems with homogeneous non-linearities of degrees 5, 6 and 7. We also present some sufficient conditions for systems with nonhomogeneous nonlinearities of degrees two, three and five.     

Asymptotic behavior of polynomial Pitman estimators

The asymptotic normality of polynomial Pitman estimators for the location parameter is proved, the principal term of the formula for the variance of these estimators is obtained, and certain characterization problems are considered that occur in the study of polynomial Pitman estimators.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 43, pp. 30–39, 1974.