A new neural network algorithm for planarization problems

To deal with the planarization problem widely used in many applications including routing very-large-scale integration （VLSI） circuits, this paper points out that only when its vertices are arranged in some specific order in a line can a planar graph be embedded on a line without any cross connections or cross edges. Energy function is proposed to meet the need of embedding a graph on a single line and route it correctly. A Hopfield network is designed according to the proposed energy function for such embedding and routing. The advantage of the proposed method is that it not only can detect if a graph is a planar one or not, but also can embed a planar graph or the maximal planar subgraph of a non-planar graph on a single line. In addition, simulated annealing is employed for helping the network to escape from local minima during the running of the Hopfield network. Experiments of the proposed method and its comparison with some existent conventional methods were performed and the results indicate that the proposed method is of great feasibility and effectiveness especially for the planarization problem of large graphs.     

Nanoparticle-based lift-off technique for ultra-thin nanoporous film preparation

Ultra-thin membrane with nanoscale through hole has great potential in biomedical applications, where precise controllability of porosity, pore size and film thickness is urgently required. The present work proposed a cost-effective way to prepare the ultra-thin nanoporous film with a promising controllability. Monodispersed nanoparticle, rather than photoresist, is used as the sacrificial material for this new lift-off process. By releasing the particles, holes can be achieved with predeter-mined characters. A 110 nm-thick nanoporous aluminum film with well-controlled pore＇s diameter was successfully fabricated to validate the technique. The technique has wider process window and better applicability than other nanofabrication methods.     

Primal or dual: which promises faster spatiotemporal search?

The existing predictive spatiotemporal indexes can be classified into two categories, depending on whether they are based on the primal or dual methodology. Although we have gained considerable empirical knowledge about various access methods, currently there is only limited understanding on the theoretical characteristics of the two methodologies. In fact, the experimental results in different papers even contradict each other, regarding the relative superiority of the primal and dual techniques. This paper presents a careful study on the query performance of general primal and dual indexes, and reveals important insight into the behavior of each technique. In particular, we mathematically establish the conditions that determine the superiority of each methodology, and provide rigorous justification for well-known observations that have not been properly explained in the literature. Our analytical findings also resolve the contradiction in the experiments of previous work.     

A comparison of finite elements for nonlinear beams: the absolute nodal coordinate and geometrically exact formulations

Two of the most popular finite element formulations for solving nonlinear beams are the absolute nodal coordinate and the geometrically exact approaches. Both can be applied to problems with very large deformations and strains, but they differ substantially at the continuous and the discrete levels. In addition, implementation and run-time computational costs also vary significantly. In the current work, we summarize the main features of the two formulations, highlighting their differences and similarities, and perform numerical benchmarks to assess their accuracy and robustness. The article concludes with recommendations for the choice of one formulation over the other.     

A new framework for understanding educational digital library use: re-examining digital divides in U.S. schools

Despite their decade of deployment, educational digital libraries have not achieved sustained use in elementary and secondary schools in the United States. Barriers to accessing the Internet and computers have been widely targeted by myriad initiatives, but efforts aimed at bridging this first-level “digital divide” have not led to increased use of the Internet and digital library resources in U.S. classrooms. In fact, such programs have revealed additional divides that affect educators’ use. This paper examines the additional digital divide levels and proposes a new framework for understanding technology innovation in schools that can improve development and outreach approaches by digital library developers.     

The election problem in asynchronous distributed systems with bounded faulty processes

Determining the “weakest” failure detectors is a central topic in solving many agreement problems such as Consensus, Non-Blocking Atomic Commit and Election in asynchronous distributed systems. So far, this has been studied extensively for several such fundamental problems. It is stated that Perfect Failure Detector P is the weakest failure detector to solve the Election problem with any number of faulty processes. In this paper, we introduce Modal failure detector M and show that to solve Election, M is the weakest failure detector to solve election when the number of faulty processes is less than ⌈n/2⌉. We also show that it is strictly weaker than P.

Optimal Control of Two-Stage Discrete Event Systems with Real-Time Constraints

We consider discrete event systems (DES) involving tasks with real-time constraints and seek to control processing times so as to minimize a cost function subject to each task meeting its own constraint. When tasks are processed over a single stage, it has been shown that there are structural properties of the optimal sample path that lead to very efficient solutions of such problems. When tasks are processed over multiple stages and are subject to end-to-end real-time constraints, these properties no longer hold and no obvious extensions are known. We consider a two-stage problem with homogeneous cost functions over all tasks at each stage and derive several new optimality properties. These properties lead to the idea of introducing “virtual” deadlines at the first stage, thus partially decoupling the stages so that the known efficient solutions for single-stage problems can be used. We prove that the solution obtained by an iterative virtual deadline algorithm (VDA) converges to the global optimal solution of the two-stage problem and illustrate the efficiency of the VDA through numerical examples.

Compositional pattern producing networks: A novel abstraction of development

Natural DNA can encode complexity on an enormous scale. Researchers are attempting to achieve the same representational efficiency in computers by implementing developmental encodings, i.e. encodings that map the genotype to the phenotype through a process of growth from a small starting point to a mature form. A major challenge in in this effort is to find the right level of abstraction of biological development to capture its essential properties without introducing unnecessary inefficiencies. In this paper, a novel abstraction of natural development, called Compositional Pattern Producing Networks (CPPNs), is proposed. Unlike currently accepted abstractions such as iterative rewrite systems and cellular growth simulations, CPPNs map to the phenotype without local interaction, that is, each individual component of the phenotype is determined independently of every other component. Results produced with CPPNs through interactive evolution of two-dimensional images show that such an encoding can nevertheless produce structural motifs often attributed to more conventional developmental abstractions, suggesting that local interaction may not be essential to the desirable properties of natural encoding in the way that is usually assumed.