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.     

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.     

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.     

Steady state analysis of an M/G/1 queue with two phase service and Bernoulli vacation schedule under multiple vacation policy

This paper examines the steady state behaviour of a batch arrival queue with two phases of heterogeneous service along and Bernoulli schedule vacation under multiple vacation policy, where after two successive phases service or first vacation the server may go for further vacations until it finds a new batch of customer in the system. We carry out an extensive stationary analysis of the system, including existence of stationary regime, queue size distribution of idle period process, embedded Markov chain steady state distribution of stationary queue size, busy period distribution along with some system characteristics.     

The effect of surface modification with silane coupling agent on suppressing the photo-catalytic activity of fine TiO2 particles as inorganic UV filter

The effect of surface modification with 3-aminopropyltriethoxysilane (APTES) and n-propyltriethoxysilane (PTES) on photo-catalytic activity and UV-shielding ability of fine TiO₂ particles were investigated. The number of surface groups (N_R) [nm⁻²] which shows the density of modifier on TiO₂ surface was calculated from the results of elemental analysis and BET measurement. The modified samples of which N_R are different were obtained by changing the concentration of modifier. When the photo-catalytic activity and UV-shielding ability of modified samples were evaluated, it was found that APTES was more effective modifier than PTES to obtained samples with low photo-catalytic activity and high UV-shielding ability. This is probably because the adsorption mechanisms on TiO₂ surface between modifiers were different and N_R is a key factor to control the performances of fine TiO₂ particles. The result of zeta potential showed that surface character of modified samples was varied by changing N_R. It suggested from these results that N_R affected the photo-catalytic activity and UV-shielding ability because N_R changed surface character of modified samples.     

Cycles throughk vertices in bipartite tournaments

We give a simple proof that everyk-connected bipartite tournament has a cycle through every set ofk vertices. This was conjectured in [4].This research was done while the first author was visiting Laboratoire de Recherche en Informatique, universite Paris-Sud whose hospitality and financial support is gratefully acknowledged     

Query complexity,or why is it difficult to separateNP A ∩coNP A fromP A by random oraclesA?

By thequery-time complexity of a relativized algorithm we mean the total length of oracle queries made; thequery-space complexity is the maximum length of the queries made. With respect to these cost measures one can define polynomially time- or space-bounded deterministic, nondeterministic, alternating, etc. Turing machines and the corresponding complexity classes. It turns out that all known relativized separation results operate essentially with this cost measure. Therefore, if certain classes do not separate in the query complexity model, this can be taken as an indication that their relativized separation in the classical cost model will require entirely new principles.A notable unresolved question in relativized complexity theory is the separation of NP^A6813895866760x/xxlarge8745.gif" alt="cap" align="MIDDLE" BORDER="0"> 6813895866760x/xxlarge8745.gif" alt="cap" align="MIDDLE" BORDER="0"> co NP^A fromP ^A under random oraclesA. We conjecture that the analogues of these classes actually coincide in the query complexity model, thus indicating an answer to the question in the title. As a first step in the direction of establishing the conjecture, we prove the following result, where polynomial bounds refer to query complexity.If two polynomially query-time-bounded nondeterministic oracle Turing machines accept precisely complementary (oracle dependent) languages L^A and {0, 1}^*6813895866760x/xxlarge8726.gif" alt="setmn" align="MIDDLE" BORDER="0">L^A under every oracle A then there exists a deterministic polynomially query-time-bounded oracle Turing machine that accept L^A. The proof involves a sort of greedy strategy to selecting deterministically, from the large set of prospective queries of the two nondeterministic machines, a small subset that suffices to perform an accepting computation in one of the nondeterministic machines. We describe additional algorithmic strategies that may resolve the same problem when the condition holds for a (1–6813895866760x/xxlarge949.gif" alt="epsi" align="BASELINE" BORDER="0">) fraction of the oracles A, a step that would bring us to a non-uniform version of the conjecture. Thereby we reduce the question to a combinatorial problem on certain pairs of sets of partial functions on finite sets.     

On the width of an orientation of a tree

There are 2 ^n-1 ways in which a tree on n vertices can be oriented. Each of these can be regarded as the (Hasse) diagram of a partially ordered set. The maximal and minimal widths of these posets are determined. The maximal width depends on the bipartition of the tree as a bipartite graph and it can be determined in time O(n). The minimal width is one of [/2] or [/2]+1, where is the number of leaves of the tree. An algorithm of execution time O(n + ² log ) to construct the minimal width orientation is given.This research was partially funded by the National Science and Engineering Research Council of Canada under Grant Number A4219.     

Dual vectors and lower bounds for the nearest lattice point problem

We prove that given a point 686/493_2005_Article_BF02122554_TeX2GIFIE1.gif" alt=" $$\overline z $$ " align="middle" border="0"> outside a given latticeL then there is a dual vector which gives a fairly good estimate for how far from the lattice the vector is. To be more precise, there is a set of translated hyperplanesH _i, such thatL686/xxlarge8834.gif" alt="sub" align="MIDDLE" BORDER="0">686/xxlarge8746.gif" alt="cup" align="MIDDLE" BORDER="0"> _iH_i andd( 686/493_2005_Article_BF02122554_TeX2GIFIE2.gif" alt=" $$\overline z $$ " align="middle" border="0"> 686/xxlarge8746.gif" alt="cup" align="MIDDLE" BORDER="0">_iH_i)686/xxlarge8807.gif" alt="gE" align="MIDDLE" BORDER="0">(6n ²+1)^–1 d( 686/493_2005_Article_BF02122554_TeX2GIFIE3.gif" alt=" $$\overline z $$ " align="middle" border="0"> ,L).Supported by an IBM fellowship.