Testing primitivity on partial words

Primitive words, or strings over a finite alphabet that cannot be written as a power of another string, play an important role in numerous research areas including formal language theory, coding theory, and combinatorics on words. Testing whether or not a word is primitive can be done in linear time in the length of the word. Indeed, a word is primitive if and only if it is not an inside factor of its square. In this paper, we describe a linear time algorithm to test primitivity on partial words which are strings that may contain a number of “do not know” symbols. Our algorithm is based on the combinatorial result that under some condition, a partial word is primitive if and only if it is not compatible with an inside factor of its square. The concept of special, related to commutativity on partial words, is foundational in the design of our algorithm. A World Wide Web server interface at http://www.uncg.edu/mat/primitive/ has been established for automated use of the program.     

Investigating undergraduate students’ proof schemes and perspectives about combinatorial proof

Combinatorics is an area of mathematics with accessible, rich problems and applications in a variety of fields. Combinatorial proof is an important topic within combinatorics that has received relatively little attention within the mathematics education community, and there is much to investigate about how students reason about and engage with combinatorial proof. In this paper, we use Harel and Sowder’s (1998) proof schemes to investigate ways that students may characterize combinatorial proofs as different from other types of proof. We gave five upper-division mathematics students combinatorial-proof tasks and asked them to reflect on their activity and combinatorial proof more generally. We found that the students used several of Harel and Sowder’s proof schemes to characterize combinatorial proof, and we discuss whether and how other proof schemes may emerge for students engaging in combinatorial proof. We conclude by discussing implications and avenues for future research.     

Cone dominance and efficiency in DEA

This paper incorporates cones on virtual multipliers of inputs and outputs into DEA analysis. Cone DEA models are developed to generalize the dual of the BCC models as well as congestion models. Input-output data and/or numbers of DMUs for BCC models are inadequate to capture many aspects where judgments, expert opinions, and other external information should be taken into analysis. Cone DEA models, on the other hand, offer improved definitions of efficiency over general cone and polyhedral cone structures. The relationships between cone models and BCC models as well as those between cone models and congestion models are discussed in the development. Two numerical examples are provided to illustrate our findings.     

A model of students’ combinatorial thinking

Combinatorial topics have become increasingly prevalent in K-12 and undergraduate curricula, yet research on combinatorics education indicates that students face difficulties when solving counting problems. The research community has not yet addressed students’ ways of thinking at a level that facilitates deeper understanding of how students conceptualize counting problems. To this end, a model of students’ combinatorial thinking was empirically and theoretically developed; it represents a conceptual analysis of students’ thinking related to counting and has been refined through analyzing students’ counting activity. In this paper, the model is presented, and relationships between formulas/expressions, counting processes, and sets of outcomes are elaborated. Additionally, the usefulness and potential explanatory power of the model are demonstrated through examining data both from a study the author conducted, and from existing literature on combinatorics education.     

双(环戊二烯基)二氯化锆催化合成乙烯-笼型倍半硅氧烷杂化共聚物及其结构表征

通过双(环戊二烯基)二氯化锆(Cp₂ZrCl₂)催化剂和改良的甲基铝氧烷(MMAO)助催化剂, 合成了无机-有机杂化共聚物. 研究了2种具有不同单乙烯基反应基团的笼型倍半硅氧烷(POSS)与乙烯的聚合. 对共聚产物的结构、 热力学性质、 分子量及其分布等进行了研究. 共聚单体(POSS)的插入率在0.01%~0.30%之间, 随着共聚单体在共聚物中摩尔分数的增大, 聚合物的熔点和熔解热降低. 共聚物的热重分析结果显示, 乙烯-POSS共聚物拥有更高的热分解温度以及较高的热分解残留量. 随着POSS的加入, 聚合物的分子量明显提高, 聚合物的分子量分布变宽.     

Stability of polyhedral borane anions and carboranes

Polyhedral borane anions and carboranes that can be constructed formally from the interaction of rings and caps will be stable with six interstitial electrons. Interstitial electron count is obtained by summing the number of π electrons of the ring and the electrons of the caps involved in ring cap binding. Thus B₇H₇ ⁻² (D_5h) has 6 interstitial electrons (none from the B₅H₅ ring, two each from the twobh caps and two negative charge),mndo calculations on isoelectronic pyramidal molecules B₆H₆ ⁻⁴ (C_5v), B₅H₅CH⁻³ (C_5v), B₅H₅ ⁻⁴ (C_4v), B₄H₄CH⁻³ (C_4v), B₄H₄ ⁻⁴ (T _d) and B₃H₃CH⁻³ (C_3v) suggests a criterion based on the out-of-plane bendings of the ring B-H bonds to select the best combination of borocycles and BH or CH caps. Three-membered borocycle prefers CH cap, five-membered borocycle prefers BH cap. The preference of four-membered ring for BH or CH cap is not as pronounced. The extra stability of B₁₂H₁₂ ⁻² arises from the geometry of the icosahedron. The relative stabilities ofnido andcloso carboranes follow from these rules.     

多面齐聚倍半硅氧烷——高分子材料的多功能性新组分

综述了多面齐聚倍半硅氧烷(POSS)的结构、性能及其类型,分析和讨论了以反应型POSS制得的均聚物和共聚物及以非反应型POSS制得的聚合物/POSS纳米复合材料的特点及其应用,简要介绍了目前国外POSS及其相关物的生产及市场。     

Facets of the polytope of the asymmetric travelling salesman problem with replenishment arcs

The Asymmetric Travelling Salesman Problem with Replenishment Arcs (RATSP) is a new class of problems arising from work related to aircraft routing. Given a digraph with cost on the arcs, a solution of the RATSP, like that of the Asymmetric Travelling Salesman Problem, induces a directed tour in the graph which minimises total cost. However the tour must satisfy additional constraints: the arc set is partitioned into replenishment arcs and ordinary arcs, each node has a non-negative weight associated with it, and the tour cannot accumulate more than some weight limit before a replenishment arc must be used. To enforce this requirement, constraints are needed. We refer to these as replenishment constraints.In this paper, we review previous polyhedral results for the RATSP and related problems, then prove that two classes of constraints developed in V. Mak and N. Boland [Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs, Technical Report TR M05/03, School of Information Technology, Deakin University, 2005] are, under appropriate conditions, facet-defining for the RATS polytope.     

On Polyhedral Projection and Parametric Programming

This paper brings together two fundamental topics: polyhedral projection and parametric linear programming. First, it is shown that, given a parametric linear program (PLP), a polyhedron exists whose projection provides the solution to the PLP. Second, the converse is tackled and it is shown how to formulate a PLP whose solution is the projection of an appropriately defined polyhedron described as the intersection of a finite number of halfspaces. The input to one operation can be converted to an input of the other operation and the resulting output can be converted back to the desired form in polynomial time—this implies that algorithms for computing projections or methods for solving parametric linear programs can be applied to either problem class. E.C. Kerrigan’s research was supported in part by the Royal Academy of Engineering, UK.