Saving Space by Fully Exploiting Invisible Transitions

Checking that a given finite state program satisfies a linear temporal logic property suffers from the state explosion problem. Often the resulting lack of available memory is more significant than any time limitations. One way to cope with this is to reduce the state graph used for model checking. We present an algorithm for constructing a state graph that is a projection of the program's state graph. The algorithm maintains the transitions and states that affect the truth of the property to be checked. Especially in conjunction with known partial order reduction algorithms, we show a substantial reduction in memory over using partial order methods alone, both in the precomputation stage, and in the result presented to a model checker. The price of the space reduction is a single additional traversal of the graph obtained with partial order reduction. As part of our space-saving methods, we present a new way to exploit Holzmann's Bit Hash Table, which assists us in solving the revisiting problem.     

On the hardness of approximating label-cover

The Label-Cover problem, defined by S. Arora, L. Babai, J. Stern, Z. Sweedyk [Proceedings of 34th IEEE Symposium on Foundations of Computer Science, 1993, pp. 724-733], serves as a starting point for numerous hardness of approximation reductions. It is one of six ‘canonical’ approximation problems in the survey of Arora and Lund [Hardness of Approximations, in: Approximation Algorithms for NP-Hard Problems, PWS Publishing Company, 1996, Chapter 10]. In this paper we present a direct combinatorial reduction from low error-probability PCP [Proceedings of 31st ACM Symposium on Theory of Computing, 1999, pp. 29-40] to Label-Cover showing it NP-hard to approximate to within 2^{(logn)1−o(1)}. This improves upon the best previous hardness of approximation results known for this problem.We also consider the Minimum-Monotone-Satisfying-Assignment (MMSA) problem of finding a satisfying assignment to a monotone formula with the least number of 1's, introduced by M. Alekhnovich, S. Buss, S. Moran, T. Pitassi [Minimum propositional proof length is NP-hard to linearly approximate, 1998]. We define a hierarchy of approximation problems obtained by restricting the number of alternations of the monotone formula. This hierarchy turns out to be equivalent to an AND/OR scheduling hierarchy suggested by M.H. Goldwasser, R. Motwani [Lecture Notes in Comput. Sci., Vol. 1272, Springer-Verlag, 1997, pp. 307-320]. We show some hardness results for certain levels in this hierarchy, and place Label-Cover between levels 3 and 4. This partially answers an open problem from M.H. Goldwasser, R. Motwani regarding the precise complexity of each level in the hierarchy, and the place of Label-Cover in it.     

The Synthesis,Crystal and Molecular Structure,and Oxidation State of Iron Complex from Pyridoxal Isonicotinoyl Hydrazone and Ferrous Sulphate

The reaction of isonicotinoyl hydrazone of pyridoxal (PIH), a biologically active iron-carrier, with FeSO₄-7H₂0 at pH ∼ 6 generates the delta, lamda species of the N,N-trans-O,O-cis-cis coordination isomer of an iron(III) complex with iron-to-ligand ratio of 1:2. The dark red-brown crystals are monoclinic, space group C2/c, with unit-cell dimensions a = 14.487(2), b = 18.586(2), c = 27.508(4) Å, β = 102.76(3)°, and Z = 8. The coordination around the metal is distorted octahedral and involves the protonated organic ligands, which are chelated through the phenolic oxygen [Fe-O1 1.941(6), Fe-O1′ 1.938(6)], an enolic form of the carbonyl oxygen [Fe-O3 2.017(6), Fe-O3′ 2.018(6)] and the azomethinic nitrogen [Fe-N2 2.133(8), Fe-N2′ 2.133(8)]. Packing is determined by systems of N-H….O and O-H….O hydrogen bonds involving the protonated pyridoxal nitrogens, the pyridoxal hydroxymethyl group, and the [SO₄]²⁻ group. The Mössbauer spectra at different temperatures (300 K, 88 K and 4.1 K) clearly prove that the iron atom in the complex is in a high-spin trivalent state.     

Boron and Sodium Doping of Polymeric Carbon Nitride Photoanodes for Photoelectrochemical Water Splitting

Polymeric carbon nitride is a promising photoanode material for water-splitting and organic transformation-based photochemical cells. Despite achieving significant progress in performance, these materials still exhibit low photoactivity compared to inorganic photoanodic materials because of a moderate visible light response, poor charge separation, and slow oxidation kinetics. Here, the synthesis of a sodium- and boron-doped carbon nitride layer with excellent activity as a photoanode in a water-splitting photoelectrochemical cell is reported. The new synthesis consists of the direct growth of carbon nitride (CN) monomers from a hot precursor solution, enabling control over the monomer-to-dopant ratio, thus determining the final CN properties. The introduction of Na and B as dopants results in a dense CN layer with a packed morphology, better charge separation thanks to the in situ formation of an electron density gradient, and an extended visible light response up to 550 nm. The optimized photoanode exhibits state-of-the-art performance: photocurrent densities with and without a hole scavenger of about 1.5 and 0.9 mA cm⁻² at 1.23 V versus reversible hydrogen electrode (RHE), and maximal external quantum efficiencies of 56% and 24%, respectively, alongside an onset potential of 0.3 V.     

Planar CMOS to multi-gate layout conversion for maximal fin utilization

Multi-gate transistors enable the pace of Moore's Law for another decade. In its 22 nm technology node Intel switched to multi-gate transistors called TriGate, whereas IBM, TSMC, Samsung and others will do so in their 20 nm and 14 nm nodes with multi-gate transistors called FinFET. Several recent publications studied the drawing of multi-gate transistors layout. Designing new VLSI cell libraries and blocks requires massive re-drawing of layout. Hard-IP reuse is an alternative method taking advantage of existing source layout by automatically mapping it into new target technology, which was used in Intel's Tick-Tock marketing strategy for several product generations. This paper presents a cell-level hard-IP reuse algorithm, converting planar transistors to multi-gate ones. We show an automatic, robust transformation of bulk diffusion polygons into fins, while addressing the key requirements of cell libraries, as maximizing performance and interface compatibility across a variety of driving strength. We present a layout conversion flow comprising time-efficient geometric manipulations and discrete optimization algorithms, while generating manually drawn layout quality. Those can easily be used in composing larger functional blocks.     

A Mechanized Proof Environment for the Convenient Computations Proof Method

A mechanized verification environment made up of theories over the deductive mechanized theorem prover PVS is presented, which allows taking advantage of the convenient computations method. This method reduces the conceptual difficulty of proving a given property for all the possible computations of a system by separating two different concerns: (1) proving that special convenient computations satisfy the property, and (2) proving that every computation is related to a convenient one by a relation which preserves the property. The approach is especially appropriate for applications in which the first concern is trivial once the second has been shown, e.g., where the specification itself is that every computation reduces to a convenient one. Two examples are the serializability of transactions in distributed databases, and sequential consistency of distributed shared memories. To reduce the repetition of effort, a clear separation is made between infrastructural theories to be supplied as a proof environment PVS library to users, and the specification and proof of particular examples. The provided infrastructure formally defines the method in its most general way. It also defines a computation model and a reduction relation—the equivalence of computations that differ only in the order of finitely many independent operations. One way to prove that this relation holds between every computation and some convenient one involves the definition of a measure function from computations into a well-founded set. Two possible default measures, which can be applied in many cases, are also defined in the infrastructure, along with useful lemmas that assist in their usage. We show how the proof environment can be used, by a step-by-step explanation of an application example.     

Computing occluding and transparent motions

Computing the motions of several moving objects in image sequences involves simultaneous motion analysis and segmentation. This task can become complicated when image motion changes significantly between frames, as with camera vibrations. Such vibrations make tracking in longer sequences harder, as temporal motion constancy cannot be assumed. The problem becomes even more difficult in the case of transparent motions.A method is presented for detecting and tracking occluding and transparent moving objects, which uses temporal integration without assuming motion constancy. Each new frame in the sequence is compared to a dynamic internal representation image of the tracked object. The internal representation image is constructed by temporally integrating frames after registration based on the motion computation. The temporal integration maintains sharpness of the tracked object, while blurring objects that have other motions. Comparing new frames to the internal representation image causes the motion analysis algorithm to continue tracking the same object in subsequent frames, and to improve the segmentation.