Syntactic characterization of closure under connected limits

Summary We give a syntactic characterization of (finitary) theories whose categories of models are closed under the formation of connected limits (respectively the formation of pullbacks and substructures) in the category of all structures. They are also those theories whose consistent extensions by new atomic facts admit in each component an initial structure (respectively an initial term structure), and also thoseT for whichM(T) is locally finitely multi-presentable in a canonical way. We also show that these two properties of theories are nonuniform.     

Left versus right canonical Wiener-Hopf factorization and realization

For an arbitrary rational matrix function, not necessarily analytic at infinity, the existence of a right canonical Wiener-Hopf factorization is characterized in terms of a left canonical Wiener-Hopf factorization. Formulas for the factors in a right factorization are given in terms of the formulas for the factors in a given left factorization. All formulas are based on a special representation of a rational matrix function involving a quintet of matrices.     

On the maximum cardinality search lower bound for treewidth

The Maximum Cardinality Search (MCS) algorithm visits the vertices of a graph in some order, such that at each step, an unvisited vertex that has the largest number of visited neighbours becomes visited. A maximum cardinality search ordering (MCS-ordering) of a graph is an ordering of the vertices that can be generated by the MCS algorithm. The visited degree of a vertex v in an MCS-ordering is the number of neighbours of v that are before v in the ordering. The visited degree of an MCS-ordering ψ of G is the maximum visited degree over all vertices v in ψ. The maximum visited degree over all MCS-orderings of graph G is called its maximum visited degree. Lucena [A new lower bound for tree-width using maximum cardinality search, SIAM J. Discrete Math. 16 (2003) 345-353] showed that the treewidth of a graph G is at least its maximum visited degree.We show that the maximum visited degree is of size O(logn) for planar graphs, and give examples of planar graphs G with maximum visited degree k with O(k!) vertices, for all k∈N. Given a graph G, it is NP-complete to determine if its maximum visited degree is at least k, for any fixed k?7. Also, this problem does not have a polynomial time approximation algorithm with constant ratio, unless P=NP. Variants of the problem are also shown to be NP-complete.In this paper, we also propose some heuristics for the problem, and report on an experimental analysis of them. Several tiebreakers for the MCS algorithm are proposed and evaluated. We also give heuristics that give upper bounds on the value of the maximum visited degree of a graph, which appear to give results close to optimal on many graphs from real life applications.     

Effects of in situ thermal annealing on the structural, optical, and electrical properties in Hg0.7Cd0.3Te epilayers grown on CdTe buffer layers

Scanning electron microscopy (SEM), Fourier transform infrared (FTIR) transmission, and Hall effect measurements were performed to investigate the structural, optical, and electrical properties of as-grown and in situ-annealed Hg_0.7Cd_0.3Te epilayers grown on CdTe buffer layers by using molecular beam epitaxy. After the Hg_0.7Cd_0.3Te epilayers had been annealed in a Hg-cell flux atmosphere, the SEM images showed that the surface morphologies of the Hg_0.7Cd_0.3Te thin films were mirror-like with no indication of pinholes or defects, and the FTIR spectra showed that the transmission intensities had increased in comparison to that of the as-grown Hg_0.7Cd_0.3Te epilayer. Hall-effect measurements showed that n-Hg_0.7Cd_0.3Te epilayers were converted to p-Hg_0.7Cd_0.3Te epilayers. These results indicate that the surface, optical, and electrical properties of the Hg_1 − xCd_xTe epilayers are improved by annealing and that as-grown n-Hg_1 − xCd_xTe epilayers can be converted to p-Hg_1 − xCd_xTe epilayers by in situ annealing.     

室温下压致铁钴镍合金的bcc→hcp相变

 本文采用高压X光衍射方法在金刚石对顶压砧中在位地（in situ）研究了Fe₆₈Co₂₄Ni₈（wt%）合金在室温下的压致bcc→hcp结构相变和直到40.5 GPa的等温压缩行为。实验结果表明该合金在常压下为bcc结构，晶格常数a₀=(0.287 0±0.000 1) nm，体积V₀=(7.119±0.007) cm³/mol，密度ρ₀=(7.981±0.008) g/cm³；在20.9 GPa附近出现bcc→hcp结构相变，两相共存压力区约10 GPa，在此区域内有晶面间距d(002)_hcp=d(110)_bcc，且原子平面(002)_hcp//(110)_bcc，hcp相比bcc相体积减小(0.33±0.02) cm³/mol；高压相hcp结构的晶格参数比值c/a=1.608±0.004；相变后原子配位数的增加使得hcp相(002)平面内及(002)平面间的最近邻原子间距比bcc相最近邻原子间距分别增大约1.6%和0.5%；用Murnaghan状态方程对实验数据进行最小二乘法拟合，得到bcc相B₀=(130±13) GPa，B₀'=12.6±0.5；hcp相V₀=(6.62±0.04) cm³/mol，B₀=(243±21) GPa，B₀'=6.8±0.3；对于该合金的bcc→fcp相变时的结构转变机制做了详细的讨论。     

An analytic approach for the analysis of rotations in fringe-balanced binary search trees

This paper presents an analytic approach to the construction cost of fringe-balanced binary search trees. In [7], Mahmoud used a bottom-up approach and an urn model of Pólya. The present method is top-down and uses differential equations and Hwang's quasi-power theorem to derive the asymptotic normality of the number of rotations needed to construct such afringe balanced search tree. We also obtain the exact expectation and variance with this method. Although Pólya's urn model is no longer needed, we also present an elegant analysis of it based on an operator calculus as in [4].This research was supported by the Austrian Research Society (FWF) under the project number P12599-MAT.     

Eliminating graphs by means of parallel knock-out schemes

In 1997 Lampert and Slater introduced parallel knock-out schemes, an iterative process on graphs that goes through several rounds. In each round of this process, every vertex eliminates exactly one of its neighbors. The parallel knock-out number of a graph is the minimum number of rounds after which all vertices have been eliminated (if possible). The parallel knock-out number is related to well-known concepts like perfect matchings, hamiltonian cycles, and 2-factors.We derive a number of combinatorial and algorithmic results on parallel knock-out numbers: for families of sparse graphs (like planar graphs or graphs of bounded tree-width), the parallel knock-out number grows at most logarithmically with the number n of vertices; this bound is basically tight for trees. Furthermore, there is a family of bipartite graphs for which the parallel knock-out number grows proportionally to the square root of n. We characterize trees with parallel knock-out number at most 2, and we show that the parallel knock-out number for trees can be computed in polynomial time via a dynamic programming approach (whereas in general graphs this problem is known to be NP-hard). Finally, we prove that the parallel knock-out number of a claw-free graph is either infinite or less than or equal to 2.     

Preemptive scheduling of interval orders is polynomial

In 1979, Papadimitriou and Yannakakis gave a polynomial time algorithm for the scheduling of jobs requiring unit completion times when the precedence constraints form an interval order. The authors solve here the corresponding problem, for preemptive scheduling (a job can be interrupted to work on more important tasks, and completed at a later time, subject to the usual scheduling constraints.) The m-machine preemptive scheduling problem is shown to have a polynomial algorithm, for both unit time and variable execution times as well, when the precedence constraints are given by an interval order.     

The structure of an Fe monolayer on the Ni (111) surface. A density-functional study using the generalized gradient approximation

Using a density-functional method that employs linear combinations of atomic orbitals as basis sets, nonlocal norm-conserving pseudopotentials and the generalized gradient approximation for exchange and correlation, we found that at 0 K the atoms of an Fe monolayer on the Ni (111) surface occupy hcp rather than fcc sites, in keeping with previous predictions made using the ab initio all-electron full-potential linearized augmented plane wave method with the local spin density approximation.     

Deciding Frattini is NP-complete

We show that it is a NP-complete problem to decide whether a finite poset arises as the (Birkhoff) dual of the Frattini sublattice of some finite distributive lattice.This work was supported in part by Swiss NSF grant 20-32644.91.