Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts

A generalized Davenport-Schinzel sequence is one over a finite alphabet whose subsequences are not isomorphic to a forbidden subsequence σ. What is the maximum length of such a σ-free sequence, as a function of its alphabet size n? Is the extremal function linear or nonlinear? And what characteristics of σ determine the answers to these questions? It is known that such sequences have length at most n⋅²(α(n))^O(1), where α is the inverse-Ackermann function and the O(1) depends on σ.We resolve a number of open problems on the extremal properties of generalized Davenport-Schinzel sequences. Among our results:

1.

We give a nearly complete characterization of linear and nonlinear σ∈^?{a,b,c} over a three-letter alphabet. Specifically, the only repetition-free minimally nonlinear forbidden sequences are ababa and abcacbc.

2.

We prove there are at least four minimally nonlinear forbidden sequences.

3.

We prove that in many cases, doubling a forbidden sequence has no significant effect on its extremal function. For example, Nivasch?s upper bounds on alternating sequences of the form t(ab) and t(ab)a, for t?3, can be extended to forbidden sequences of the form t(aabb) and t(aabb)a.

4.

Finally, we show that the absence of simple subsequences in σ tells us nothing about σ?s extremal function. For example, for any t, there exists a σt avoiding ababa whose extremal function is Ω(n⋅²αt(n)).

Most of our results are obtained by translating questions about generalized Davenport-Schinzel sequences into questions about the density of 0-1 matrices avoiding certain forbidden submatrices. We give new and often tight bounds on the extremal functions of numerous forbidden 0-1 matrices.     

Rating high‐throughput screening results via h‐index

The quantification of both the impact and quality of a scientist's publication record is an essential step in making decisions concerning hiring, promotion, and allocation of funding. In an attempt to resolve this problem, Hirsh proposed the “h‐index,” a single‐number criterion incorporating both the number of publications and the number of citations per publication. This value facilitates rating of a scientist's performance and is now one of the most commonly used matrices. Here, we would like to propose the rating of high‐throughput screening (HTS) result by the h‐index. Rating HTS result is to estimate how the HTS result is preferred by a medicinal chemist. In this study, we applied the h‐index for rating HTS results and observed an enhanced rating of preferred starting points for drug development. In addition, we developed a new index, the maximum common structure (MCS) index, which is more effective than the h‐index. Copyright © 2014 John Wiley & Sons, Ltd.     

BAND STRUCTURE AND TRANSMISSION CHARACTERISTICS CALCULATION OF PHONONIC CRYSTALS BASED ON MULTI-LEVEL SUBSTRUCTURE TECHNIQUE

基于多重多级子结构方法提出一种快速的声子晶体能带与传输特性的计算策略. 主要思想是将声子晶体划分成多层级子结构有限元模型,在能带计算中采用静凝聚和子结构周游树技术将子结构的内部刚度阵凝聚到Bloch 边界上. 由于内部刚度阵并不随着简约波矢变化,所以这种计算策略可以大大降低求解规模并提高计算效率,并不对整体有限元模型引入近似. 在传输特性计算中同样采用该策略,由于声子晶体单胞具有周期性,所以各个单胞的系数矩阵是相同的,从而减少计算量,并且可以灵活地选择是否回代求解单胞内部自由度. 数值算例以三维局域共振型声子晶体和二维Bragg 散射型声子晶体为例,计算结果验证了这种求解策略的正确性和高效性,并适用于复杂声子晶体分析.     

无网格模型的子结构分析

提出一种无网格模型的子结构分析方法。基于界带分析方法,处理无网格模型子结构之间的连接,能够保证各个子结构之间无缝连接,从而使无网格子结构模型与原无网格模型等价,同时还能够降低无网格刚度方程的计算规模。数值算例表明,本文方法是正确可靠的,可以保证各个子结构之间无缝连接。     

基于多重多级动力子结构的瞬态分析方法

提出利用多重多级子结构技术与Newmark算法求解结构动力学方程的高精度算法.该算法利用静凝聚技术列式简单,在凝聚过程中并不引入任何近似的优点,采用子结构周游树技术,分别对每个子结构求解Newmark等效平衡方程,最后通过回代求解得到整体结构的响应.由于该算法考虑了子结构内部自由度对整体求解的贡献,算法实施不受子结构划分方式的限制,因此可以得到系统高阶模态对响应分析的影响.该算法计算精度与传统的全结构求解相当,计算效率高,消耗计算机资源少,且可构造为统一的多重多级子结构综合分析算法框架.数值算例验证了该算法的正确性和有效性.     

OpenSees 混合模拟试验技术发展与应用

将现代结构地震性能模拟与试验分为整体结构模拟试验和子结构模拟试验两类. 在此基础之上详细 讨论了混合模拟试验的基本概念背景及其应用与发展现状. 结合面相对象有限元程序OpenSees 的高层程序 架构和并行计算程序架构, 详细论述了基于OpenSees 的4 种混合模拟试验系统, 并简要介绍了多尺度一体化 混合建模的概念与应用. 证明基于商业或非商业有限元软件平台开展混合模拟试验是可行的; 混合模拟试验 所要处理的核心问题是如何将不同的有限元软件平台以及各个试验站点的设备联系起来, 并实现相互之间的 协同工作. 混合模拟试验在强震作用下结构连续倒塌问题的研究中具有一定的优势. 指出混合模拟试验这一 新技术的实质性发展离不开目前所强调的多学科之间的无缝融合.      

相同子结构串的本征对问题及展开解法

本文讲述了串连式子结构的分析计算方法,它相当于结构分析中按横截面展开的方法。文中讲述了移位不变法以及初参数与传递矩阵法两个方面,并指明了两种方法的联合运用及相互关系,截面上本征值问题的计算以及按本征向量展开等问题。     

碰撞激发弹塑性波传播的动态子结构方法

通过建立弹塑性碰撞动态子结构模型, 推导了模态坐标下的控制方程,提出了模拟柔性结构碰撞激发弹塑性波传播的动态子结构方法, 并对其中的主模态的存在性和主模态截断的收敛性进行了证明. 通过对柔性杆纵向碰撞和柔性梁横向碰撞两个算例的计算, 并将计算结果与理论解和三维动力有限方法计算结果进行了对比, 验证了该方法的数值收敛性和计算碰撞弹塑性波传播的有效性.      

轨道系统高频振动分析的动态子结构法

提出了包含钢轨断面弹性变形、轨下不连续支承、横垂向交叉导的轨道高频振动分析模型。根据轮轨特点,提出适合轮轨高频振动分析的阻抗聚缩法。预测结果与试验结果吻合较好。分析表明约８００Ｈｚ以下,钢轨振动表现为整体振动,再高频率钢轨发生断面弹性变形的振动。我国轨道系统第一、第二、阶二振频率分别为１５０Ｈｚ和３２０Ｈｚ,ｐｉｎｎｅｄ－ｐｉｎｎｅｄ共振频率的１２８０Ｈｚ。