OpenRaiser/Intern-Atlas huggingface dataset:
Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs
Venue: arXiv cs.DS 2008
Year: 2008

We present a deterministic way of assigning small (log bit) weights to the edges of a bipartite planar graph so that the minimum weight perfect matching becomes unique. The isolation lemma as described in (Mulmuley et al. 1987) achieves the same for general graphs using a randomized weighting scheme, whereas we can do it deterministically when restricted to bipartite planar graphs. As a consequence, we reduce both decision and construction versions of the matching problem to testing whether a matrix is singular, under the promise that its determinant is 0 or 1, thus obtaining a highly parallel SPL algorithm for bipartite planar graphs. This improves the earlier known bounds of non-uniform SPL by (Allender et al. 1999) and $NC^2$ by (Miller and Naor 1995, Mahajan and Varadarajan 2000). It also rekindles the hope of obtaining a deterministic parallel algorithm for constructing a perfect matching in non-bipartite planar graphs, which has been open for a long time. Our techniques are elementary and simple.
An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines
Venue: arXiv cs.DS 2008
Year: 2008

We study the scheduling problem on unrelated machines in the mechanism design setting. This problem was proposed and studied in the seminal paper (Nisan and Ronen 1999), where they gave a 1.75-approximation randomized truthful mechanism for the case of two machines. We improve this result by a 1.6737-approximation randomized truthful mechanism. We also generalize our result to a $0.8368m$-approximation mechanism for task scheduling with $m$ machines, which improve the previous best upper bound of $0.875m(Mu'alem and Schapira 2007).
On Geometric Spanners of Euclidean and Unit Disk Graphs
Venue: arXiv cs.DS 2008
Year: 2008

We consider the problem of constructing bounded-degree planar geometric spanners of Euclidean and unit-disk graphs. It is well known that the Delaunay subgraph is a planar geometric spanner with stretch factor $C_{del\approx 2.42$; however, its degree may not be bounded. Our first result is a very simple linear time algorithm for constructing a subgraph of the Delaunay graph with stretch factor $ρ=1+2π(k\cos{\frac{π{k)^{-1$ and degree bounded by $k$, for any integer parameter $k\geq 14$. This result immediately implies an algorithm for constructing a planar geometric spanner of a Euclidean graph with stretch factor $ρ\cdot C_{del$ and degree bounded by $k$, for any integer parameter $k\geq 14$. Moreover, the resulting spanner contains a Euclidean Minimum Spanning Tree (EMST) as a subgraph. Our second contribution lies in developing the structural results necessary to transfer our analysis and algorithm from Euclidean graphs to unit disk graphs, the usual model for wireless ad-hoc networks. We obtain a very simple distributed, {\em strictly-localized algorithm that, given a unit disk graph embedded in the plane, constructs a geometric spanner with the above stretch factor and degree bound, and also containing an EMST as a subgraph. The obtained results dramatically improve the previous results in all aspects, as shown in the paper.
Succinctness of the Complement and Intersection of Regular Expressions
Venue: arXiv cs.CC 2008
Year: 2008

We study the succinctness of the complement and intersection of regular expressions. In particular, we show that when constructing a regular expression defining the complement of a given regular expression, a double exponential size increase cannot be avoided. Similarly, when constructing a regular expression defining the intersection of a fixed and an arbitrary number of regular expressions, an exponential and double exponential size increase, respectively, can in worst-case not be avoided. All mentioned lower bounds improve the existing ones by one exponential and are tight in the sense that the target expression can be constructed in the corresponding time class, i.e., exponential or double exponential time. As a by-product, we generalize a theorem by Ehrenfeucht and Zeiger stating that there is a class of DFAs which are exponentially more succinct than regular expressions, to a fixed four-letter alphabet. When the given regular expressions are one-unambiguous, as for instance required by the XML Schema specification, the complement can be computed in polynomial time whereas the bounds concerning intersection continue to hold. For the subclass of single-occurrence regular expressions, we prove a tight exponential lower bound for intersection.
New Horizontal Frustum Optical Waveguide Fabrication Using UV Proximity Printing
Venue: arXiv cs.OH 2008
Year: 2008

This paper presents a novel method to fabricate the horizontal frustum structure as a planar optical waveguide by using the proximity printing technique. A horizontal frustum optical waveguide with a both lateral and vertical taper structure was produced. The orthogonal and inclined masks with the diffraction effect were employed in lithography process. This method can precisely control each horizontal frustum optical waveguide geometric profile in the fabrication process. The horizontal frustum optical waveguide and its array with the same inclined angle were generated. The beam propagation simulation software (BPM_CAD) was used to modeling the optical performance. The simulation results reveal that the mode profile matched into horizontal frustum optical waveguide and fiber from the laser diode. The optical loss of horizontal hemi-frustum structure of optical waveguides was less than 0.2dB. The horizontal hemifrustum waveguide will be used for fiber coupling on boards for further optical communication systems.
A Fully Parameterized Fem Model for Electromagnetic Optimization of an RF Mems Wafer Level Package
Venue: arXiv cs.OH 2008
Year: 2008

In this work, we present a fully parameterized capped transmission line model for electromagnetic optimization of a wafer level package (WLP) for RF MEMS applications using the Ansoft HFSS-TM electromagnetic simulator. All the degrees of freedom (DoF's) in the package fabrication can be modified within the model in order to optimize for losses and mismatch (capacitive and inductive couplings) introduced by the cap affecting the MEMS RF behaviour. Ansoft HFSS-TM was also validated for the simulation of capped RF MEMS devices by comparison against experimental data. A test run of capped 50 transmission lines and shorts was fabricated and tested.
Characterisation of an Electrostatic Vibration Harvester
Venue: arXiv cs.OH 2008
Year: 2008

Harvesting energy from ambient vibration is proposed as an alternative to storage based power supplies for autonomous systems. The system presented converts the mechanical energy of a vibration into electrical energy by means of a variable capacitor, which is polarized by an electret. A lumped element model is used to study the generator and design a prototype. The device has been micromachined in silicon, based on a two-wafer process. The prototype was successfully tested, both using an external polarization source and an electret.
Surface Generation Analysis in Micro End-Milling Considering the Influences of Grain
Venue: arXiv cs.OH 2008
Year: 2008

Micro end-milling method is a universal micro manufacturing method, which can be used to fabricating complex 3D structures and parts with many materials. But compared with their micrometer order size, their surface roughness quality is not satisfied. In this paper, the different metal phase grains influences are researched, and the micro end-milling process is described while the material is anisotropic. In this paper, the physical characteristics of different grains, especially friction coefficient and elastic module, are very critical to determine the chip formation process and surface generation. The chip is often discontinues because of the grain boundary effect. Through the micro end-milling experiment, the bottom surface results correlate very well with the theory analysis.
An Integrated Circuit Compatible Compact Package for Thermal Gas Flowmeters
Venue: arXiv cs.OH 2008
Year: 2008

An original packaging method suitable for integrated thermal mass flow sensors is presented. The method consists in the application of a plastic transparent adapter to the chip surface. The adapter is sealed to the chip surface by means of a thermal procedure. By this approach it is possible to selectively convey the fluid flow to reduced chip areas, avoiding contact with the pads. Fabrication and testing of a very compact flow sensor is described.
Formation of Embedded Microstructures by Thermal Activated Solvent Bonding
Venue: arXiv cs.OH 2008
Year: 2008

We present a thermal activated solvent bonding technique for the formation of embedded microstrucutres in polymer. It is based on the temperature dependent solubility of polymer in a liquid that is not a solvent at room temperature. With thermal activation, the liquid is transformed into a solvent of the polymer, creating a bonding capability through segmental or chain interdiffusion at the bonding interface. The technique has advantages over the more commonly used thermal bonding due to its much lower operation temperature (30 degrees C lower than the material's Tg), lower load, as well as shorter time. Lap shear test indicated bonding shear strength of up to 2.9 MPa. Leak test based on the bubble emission technique showed that the bonded microfluidic device can withstand at least 6 bars (87 psi) of internal pressure (gauge) in the microchannel. This technique can be applied to other systems of polymer and solvent.
Micromachined Polycrystalline Sige-Based Thermopiles for Micropower Generation on Human Body
Venue: arXiv cs.OH 2008
Year: 2008

This paper presents a polycrystalline silicon germanium (poly-SiGe) thermopile specially designed for thermoelectric generators used on human body. Both the design of the single thermocouple and the arrangement of the thermocouple array have been described. A rim structure has been introduced in order to increase the temperature difference across the thermocouple junctions. The modeling of the thermocouple and the thermopile has been performed analytically and numerically. An output power of about 1 $μ$W at an output voltage of more than 1 V is expected from the current design of thermopiles in a watch-size generator. The key material properties of the poly-SiGe have been measured. The thermopile has been fabricated and tested. Experimental results clearly demonstrate the advantage of the rim structure in increasing output voltage. In presence of forced convection, the output voltage of a non-released thermopile can increase from about 53 mV/K/cm2 to about 130 mV/K/cm2 after the rim structure is formed. A larger output voltage from the thermopile is expected upon process completion.
Simulation of valveless micropump and mode analysis
Venue: arXiv cs.OH 2008
Year: 2008

In this work, a 3-D simulation is performed to study for the solid-fluid coupling effect driven by piezoelectric materials and utilizes asymmetric obstacles to control the flow direction. The result of simulation is also verified. For a micropump, it is crucial to find the optimal working frequency which produce maximum net flow rate. The PZT plate vibrates under the first mode, which is symmetric. Adjusting the working frequency, the maximum flow rate can be obtained. For the micrpump we studied, the optimal working frequency is 3.2K Hz. At higher working frequency, say 20K Hz, the fluid-solid membrane may come out a intermediate mode, which is different from the first mode and the second mode. It is observed that the center of the mode drifts. Meanwhile, the result shows that a phase shift lagging when the excitation force exists in the vibration response. Finally, at even higher working frequency, say 30K Hz, a second vibration mode is observed.
Monotonic and fatigue testing of spring-bridged freestanding microbeams application for MEMS
Venue: arXiv cs.OH 2008
Year: 2008

Microelectromechanical systems (MEMS) technologies are developing rapidly with increasing study of the design, fabrication and commercialization of microscale systems and devices. Accurate knowledge on the mechanical behaviors of thin film materials used for MEMS is important for successful design and development of MEMS. Here a novel electroplating spring-bridge micro-tensile specimen integrates pin-pin align holes, misalignment compensate spring, load sensor beam and freestanding thin film is demonstrated and fabricated. The specimen is fit into a specially designed micro-mechanical apparatus to carry out a series of monotonic tensile testing on sub-micron freestanding thin films. Certain thin films applicable as structure or motion gears in MEMS were tested including sputtered gold, copper and tantalum nitride thin films. Metal specimens were fabricated by sputtering; for tantalum nitride film samples, nitrogen gas was introduced into the chamber during sputtering tantalum films on the silicon wafer. The sample fabrication method involves three steps of lithography and two steps of electroplating copper to hold a dog bone freestanding thin film. Using standard wet etching or lift off techniques, a series of microtensile specimens were patterned in metal thin films, holes, and seed layer for spring and frame structure on the underlying silicon oxide coated silicon substrate. Two steps of electroplating processing to distinct spring and frame portion of the test chip. Finally, chemical etched away the silicon oxide to separated electroplated specimen and silicon substrate.
A Reconfigurable Impedance Matching Network Employing RF-MEMS Switches
Venue: arXiv cs.OH 2008
Year: 2008

We propose the design of a reconfigurable impedance matching network for the lower RF frequency band, based on a developed RF-MEMS technology. The circuit is composed of RF-MEMS ohmic relays, metal-insulator-metal (MIM) capacitors and suspended spiral inductors, all integrated on a high resistivity Silicon substrate. The presented circuit is well-suited for all applications requiring adaptive impedance matching between two in principle unknown cascaded RF-circuits. The fabrication and testing of a monolithic integrated prototype in RF-MEMS technology from ITC-irst is currently underway.
Modeling of a piezoelectric micro-scanner
Venue: arXiv cs.OH 2008
Year: 2008

Micro-scanners have been widely used in many optical applications. The micro-scanner presented in this paper uses multimorph-type bending actuators to tilt a square plate mirror. This paper presents a complete analytical model of the piezoelectric micro-scanner. This theoretical model based on strength of material equations calculates the force generated by the multimorphs on the mirror, the profile of the structure and the angular deflection of the mirror. The proposed model, used to optimize the design of the piezoelectric silicon micro-scanner, is intended for further HDL integration, allowing in this way system level simulation and optimization.
A novel method for fatigue testing of MEMS devices containing movable elements
Venue: arXiv cs.OH 2008
Year: 2008

In this paper we present an electronic circuit for position or capacitance estimation of MEMS electrostatic actuators based on a switched capacitor technique. The circuit uses a capacitive divider configuration composed by a fixed capacitor and the variable capacitance of the electrostatic actuator for generating a signal that is a function of the input voltage and capacitive ratio. The proposed circuit can be used to actuate and to sense position of an electrostatic MEMS actuator without extra sensing elements. This approach is compatible with the requirements of most analog feedback systems and the circuit topology of pulsed digital oscillators (PDO).
Experimental Characterization of the static behaviour of microcatntilevers electrostatically actuated
Venue: arXiv cs.OH 2008
Year: 2008

This paper concerns the experimental validation of some mathematical models previously developed by the authors, to predict the static behaviour of microelectrostatic actuators, basically free-clamped microbeams. This layout is currently used in RF-MEMS design operation or even in material testing at microscale. The analysis investigates preliminarily the static behaviour of a set of microcantilevers bending in-plane. This investigation is aimed to distinguish the geometrical linear behaviour, exhibited under small displacement assumption, from the geometrical nonlinearity, caused by large deflection. The applied electromechanical force, which nonlinearly depends on displacement, charge and voltage, is predicted by a coupled-field approach, based on numerical methods and herewith experimentally validated, by means of a Fogale Zoomsurf 3D. Model performance is evaluated on pull-in prediction and on the curve displacement vs. voltage. In fact, FEM nonlinear solution performed by a coupled-field approach, available on commercial codes, and by a FEM non-incremental approach are compared with linear solution, for different values of the design parameters.
Bridge configurations in piezoresistive two-axis accelerometers
Venue: arXiv cs.OH 2008
Year: 2008

In piezoresisitive two-axis accelerometers with two proof masses suspended by cantilever beams, there are generally many ways to configure the Wheatstone bridges. The configurations are different both with respect to functionality and performance. The main distinction is between bridges that contain resistors belonging to both proof masses, and the one bridge that doesn't. We compare the different bridge configurations by analytical calculations of bridge non-linearity, robustness towards manufacturing variations and electronic noise. We consider accelerometers where the ratio between the sensitivity to acceleration normal and parallel to the chip plane vary over a wide range. For numerical examples we use representative values for p-type silicon. The performance of the configuration with one bridge connected to each proof mass is superior to those that combine resistors belonging to different proof masses.
Design and Implementation of Aggregate Functions in the DLV System
Venue: arXiv cs.AI 2008
Year: 2008

Disjunctive Logic Programming (DLP) is a very expressive formalism: it allows for expressing every property of finite structures that is decidable in the complexity class SigmaP2 (= NP^NP). Despite this high expressiveness, there are some simple properties, often arising in real-world applications, which cannot be encoded in a simple and natural manner. Especially properties that require the use of arithmetic operators (like sum, times, or count) on a set or multiset of elements, which satisfy some conditions, cannot be naturally expressed in classic DLP. To overcome this deficiency, we extend DLP by aggregate functions in a conservative way. In particular, we avoid the introduction of constructs with disputed semantics, by requiring aggregates to be stratified. We formally define the semantics of the extended language (called DLP^A), and illustrate how it can be profitably used for representing knowledge. Furthermore, we analyze the computational complexity of DLP^A, showing that the addition of aggregates does not bring a higher cost in that respect. Finally, we provide an implementation of DLP^A in DLV -- a state-of-the-art DLP system -- and report on experiments which confirm the usefulness of the proposed extension also for the efficiency of computation.
General Algorithms for Testing the Ambiguity of Finite Automata
Venue: arXiv cs.CC 2008
Year: 2008

This paper presents efficient algorithms for testing the finite, polynomial, and exponential ambiguity of finite automata with $ε$-transitions. It gives an algorithm for testing the exponential ambiguity of an automaton $A$ in time $O(|A|_E^2)$, and finite or polynomial ambiguity in time $O(|A|_E^3)$. These complexities significantly improve over the previous best complexities given for the same problem. Furthermore, the algorithms presented are simple and are based on a general algorithm for the composition or intersection of automata. We also give an algorithm to determine the degree of polynomial ambiguity of a finite automaton $A$ that is polynomially ambiguous in time $O(|A|_E^3)$. Finally, we present an application of our algorithms to an approximate computation of the entropy of a probabilistic automaton.
Turán Graphs, Stability Number, and Fibonacci Index
Venue: arXiv cs.DM 2008
Year: 2008

The Fibonacci index of a graph is the number of its stable sets. This parameter is widely studied and has applications in chemical graph theory. In this paper, we establish tight upper bounds for the Fibonacci index in terms of the stability number and the order of general graphs and connected graphs. Turán graphs frequently appear in extremal graph theory. We show that Turán graphs and a connected variant of them are also extremal for these particular problems.
PVM-Distributed Implementation of the Radiance Code
Venue: arXiv cs.DC 2008
Year: 2008

The Parallel Virtual Machine (PVM) tool has been used for a distributed implementation of Greg Ward's Radiance code. In order to generate exactly the same primary rays with both the sequential and the parallel codes, the quincunx sampling technique used in Radiance for the reduction of the number of primary rays by interpolation, must be left untouched in the parallel implementation. The octree of local ambient values used in Radiance for the indirect illumination has been shared among all the processors. Both static and dynamic image partitioning techniques which replicate the octree of the complete scene in all the processors and have load-balancing, have been developed for one frame rendering. Speedups larger than 7.5 have been achieved in a network of 8 workstations. For animation sequences, a new dynamic partitioning distribution technique with superlinear speedups has also been developed.
Sketch-Based Estimation of Subpopulation-Weight
Venue: arXiv cs.DB 2008
Year: 2008

Summaries of massive data sets support approximate query processing over the original data. A basic aggregate over a set of records is the weight of subpopulations specified as a predicate over records' attributes. Bottom-k sketches are a powerful summarization format of weighted items that includes priority sampling and the classic weighted sampling without replacement. They can be computed efficiently for many representations of the data including distributed databases and data streams. We derive novel unbiased estimators and efficient confidence bounds for subpopulation weight. Our estimators and bounds are tailored by distinguishing between applications (such as data streams) where the total weight of the sketched set can be computed by the summarization algorithm without a significant use of additional resources, and applications (such as sketches of network neighborhoods) where this is not the case. Our rigorous derivations are based on clever applications of the Horvitz-Thompson estimator, and are complemented by efficient computational methods. We demonstrate their benefit on a wide range of Pareto distributions.
An Empirical Study of End-User Behaviour in Spreadsheet Error Detection & Correction
Venue: arXiv cs.HC 2008
Year: 2008

Very little is known about the process by which end-user developers detect and correct spreadsheet errors. Any research pertaining to the development of spreadsheet testing methodologies or auditing tools would benefit from information on how end-users perform the debugging process in practice. Thirteen industry-based professionals and thirty-four accounting & finance students took part in a current ongoing experiment designed to record and analyse end-user behaviour in spreadsheet error detection and correction. Professionals significantly outperformed students in correcting certain error types. Time-based cell activity analysis showed that a strong correlation exists between the percentage of cells inspected and the number of errors corrected. The cell activity data was gathered through a purpose written VBA Excel plug-in that records the time and detail of all cell selection and cell change actions of individuals.