OpenRaiser/Intern-Atlas huggingface dataset:
Structural aspects of tilings
Venue: arXiv cs.OH 2008
Year: 2008

In this paper, we study the structure of the set of tilings produced by any given tile-set. For better understanding this structure, we address the set of finite patterns that each tiling contains. This set of patterns can be analyzed in two different contexts: the first one is combinatorial and the other topological. These two approaches have independent merits and, once combined, provide somehow surprising results. The particular case where the set of produced tilings is countable is deeply investigated while we prove that the uncountable case may have a completely different structure. We introduce a pattern preorder and also make use of Cantor-Bendixson rank. Our first main result is that a tile-set that produces only periodic tilings produces only a finite number of them. Our second main result exhibits a tiling with exactly one vector of periodicity in the countable case.
Understanding maximal repetitions in strings
Venue: arXiv cs.DS 2008
Year: 2008

The cornerstone of any algorithm computing all repetitions in a string of length n in O(n) time is the fact that the number of runs (or maximal repetitions) is O(n). We give a simple proof of this result. As a consequence of our approach, the stronger result concerning the linearity of the sum of exponents of all runs follows easily.
Trimmed Moebius Inversion and Graphs of Bounded Degree
Venue: arXiv cs.DS 2008
Year: 2008

We study ways to expedite Yates's algorithm for computing the zeta and Moebius transforms of a function defined on the subset lattice. We develop a trimmed variant of Moebius inversion that proceeds point by point, finishing the calculation at a subset before considering its supersets. For an $n$-element universe $U$ and a family $\scr F$ of its subsets, trimmed Moebius inversion allows us to compute the number of packings, coverings, and partitions of $U$ with $k$ sets from $\scr F$ in time within a polynomial factor (in $n$) of the number of supersets of the members of $\scr F$. Relying on an intersection theorem of Chung et al. (1986) to bound the sizes of set families, we apply these ideas to well-studied combinatorial optimisation problems on graphs of maximum degree $Δ$. In particular, we show how to compute the Domatic Number in time within a polynomial factor of $(2^{Δ+1-2)^{n/(Δ+1)$ and the Chromatic Number in time within a polynomial factor of $(2^{Δ+1-Δ-1)^{n/(Δ+1)$. For any constant $Δ$, these bounds are $O\bigl((2-ε)^n\bigr)$ for $ε>0$ independent of the number of vertices $n$.
Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound
Venue: arXiv cs.CC 2008
Year: 2008

We study the one-way number-on-the-forehead (NOF) communication complexity of the $k$-layer pointer jumping problem with $n$ vertices per layer. This classic problem, which has connections to many aspects of complexity theory, has seen a recent burst of research activity, seemingly preparing the ground for an $Ω(n)$ lower bound, for constant $k$. Our first result is a surprising sublinear -- i.e., $o(n)$ -- upper bound for the problem that holds for $k \ge 3$, dashing hopes for such a lower bound. A closer look at the protocol achieving the upper bound shows that all but one of the players involved are collapsing, i.e., their messages depend only on the composition of the layers ahead of them. We consider protocols for the pointer jumping problem where all players are collapsing. Our second result shows that a strong $n - O(\log n)$ lower bound does hold in this case. Our third result is another upper bound showing that nontrivial protocols for (a non-Boolean version of) pointer jumping are possible even when all players are collapsing. Our lower bound result uses a novel proof technique, different from those of earlier lower bounds that had an information-theoretic flavor. We hope this is useful in further study of the problem.
Trimming of Graphs, with Application to Point Labeling
Venue: arXiv cs.DM 2008
Year: 2008

For $t,g>0$, a vertex-weighted graph of total weight $W$ is $(t,g)$-trimmable if it contains a vertex-induced subgraph of total weight at least $(1-1/t)W$ and with no simple path of more than $g$ edges. A family of graphs is trimmable if for each constant $t>0$, there is a constant $g=g(t)$ such that every vertex-weighted graph in the family is $(t,g)$-trimmable. We show that every family of graphs of bounded domino treewidth is trimmable. This implies that every family of graphs of bounded degree is trimmable if the graphs in the family have bounded treewidth or are planar. Based on this result, we derive a polynomial-time approximation scheme for the problem of labeling weighted points with nonoverlapping sliding labels of unit height and given lengths so as to maximize the total weight of the labeled points. This settles one of the last major open questions in the theory of map labeling.
Computing Minimum Spanning Trees with Uncertainty
Venue: arXiv cs.DS 2008
Year: 2008

We consider the minimum spanning tree problem in a setting where information about the edge weights of the given graph is uncertain. Initially, for each edge $e$ of the graph only a set $A_e$, called an uncertainty area, that contains the actual edge weight $w_e$ is known. The algorithm can `update' $e$ to obtain the edge weight $w_e \in A_e$. The task is to output the edge set of a minimum spanning tree after a minimum number of updates. An algorithm is $k$-update competitive if it makes at most $k$ times as many updates as the optimum. We present a 2-update competitive algorithm if all areas $A_e$ are open or trivial, which is the best possible among deterministic algorithms. The condition on the areas $A_e$ is to exclude degenerate inputs for which no constant update competitive algorithm can exist. Next, we consider a setting where the vertices of the graph correspond to points in Euclidean space and the weight of an edge is equal to the distance of its endpoints. The location of each point is initially given as an uncertainty area, and an update reveals the exact location of the point. We give a general relation between the edge uncertainty and the vertex uncertainty versions of a problem and use it to derive a 4-update competitive algorithm for the minimum spanning tree problem in the vertex uncertainty model. Again, we show that this is best possible among deterministic algorithms.
Quantifying Homology Classes
Venue: arXiv cs.CG 2008
Year: 2008

We develop a method for measuring homology classes. This involves three problems. First, we define the size of a homology class, using ideas from relative homology. Second, we define an optimal basis of a homology group to be the basis whose elements' size have the minimal sum. We provide a greedy algorithm to compute the optimal basis and measure classes in it. The algorithm runs in $O(β^4 n^3 \log^2 n)$ time, where $n$ is the size of the simplicial complex and $β$ is the Betti number of the homology group. Third, we discuss different ways of localizing homology classes and prove some hardness results.
Cardinality and counting quantifiers on omega-automatic structures
Venue: arXiv cs.LO 2008
Year: 2008

We investigate structures that can be represented by omega-automata, so called omega-automatic structures, and prove that relations defined over such structures in first-order logic expanded by the first-order quantifiers `there exist at most $\aleph_0$ many', 'there exist finitely many' and 'there exist $k$ modulo $m$ many' are omega-regular. The proof identifies certain algebraic properties of omega-semigroups. As a consequence an omega-regular equivalence relation of countable index has an omega-regular set of representatives. This implies Blumensath's conjecture that a countable structure with an $ω$-automatic presentation can be represented using automata on finite words. This also complements a very recent result of Hjörth, Khoussainov, Montalban and Nies showing that there is an omega-automatic structure which has no injective presentation.
Fabrication of MEMS Resonators in Thin SOI
Venue: arXiv cs.OH 2008
Year: 2008

A simple and fast process for micro-electromechanical (MEM) resonators with deep sub-micron transduction gaps in thin SOI is presented in this paper. Thin SOI wafers are important for advanced CMOS technology and thus are evaluated as resonator substrates for future co-integration with CMOS circuitry on a single chip. As the transduction capacitance scales with the resonator thickness, it is important to fabricate deep sub-micron trenches in order to achieve a good capacitive coupling. Through the combination of conventional UV-lithography and focused ion beam (FIB) milling the process needs only two lithography steps, enabling therefore a way for fast prototyping of MEM-resonators. Different FIB parameters and etching parameters are compared in this paper and their effect on the process are reported.
Liquid Density Sensing Using Resonant Flexural Plate Wave Device with Sol-Gel PZT Thin Films
Venue: arXiv cs.OH 2008
Year: 2008

This paper presents the design, fabrication and preliminary experimental results of a flexure plate wave (FPW) resonator using sol-gel derived lead zirconate titanates (PZT) thin films. The resonator adopts a two-port structure with reflecting grates on the composite membrane of PZT and SiNx. The design of the reflecting grate is derived from a SAW resonator model using COM theory to produce a sharp resonant peak. The comparison between the mass and the viscosity effects from the theoretical expression illustrates the applications and the constraints of the proposed device in liquid sensing. Multiple coatings of sol-gel derived PZT films are adopted because of the cost advantage and the high electromechanical coupling effect over other piezoelectric films. The fabrication issues of the proposed material structure are addressed. Theoretical estimations of the mass and the viscosity effects are compared with the experimental results. The resonant frequency has a good linear correlation with the density of low viscosity liquids, which demonstrate the feasibility of the proposed device.
Design, Fabrication and Characterization of a Piezoelectric Microgenerator Including a Power Management Circuit
Venue: arXiv cs.OH 2008
Year: 2008

We report in this paper the design, fabrication and experimental characterization of a piezoelectric MEMS microgenerator. This device scavenges the energy of ambient mechanical vibrations characterized by frequencies in the range of 1 kHz. This component is made with Aluminum Nitride thin film deposited with a CMOS compatible process. Moreover we analyze two possible solutions for the signal rectification: a discrete doubler-rectifier and a full custom power management circuit. The ASIC developed for this application takes advantage of diodes with very low threshold voltage and therefore allows the conversion of extremely low input voltages corresponding to very weak input accelerations. The volume of the proposed generator is inferior to 1mm3 and the generated powers are in the range of 1$μ$W. This system is intended to supply power to autonomous wireless sensor nodes.
Gas Damping Coefficient Research for MEMS Comb Linear Vibration Gyroscope
Venue: arXiv cs.OH 2008
Year: 2008

Silicon-MEMS gyroscope is an important part of MEMS (Micro Electrical Mechanical System). There are some disturb ignored in traditional gyroscope that must be evaluated newly because of its smaller size (reach the level of micron). In these disturb, the air pressure largely influences the performance of MEMS gyroscope. Different air pressure causes different gas damping coefficient for the MEMS comb linear vibration gyroscope and different gas damping coefficient influences the quality factor of the gyroscope directive. The quality factor influences the dynamic working bandwidth of the MEMS comb linear vibration gyroscope, so it is influences the output characteristic of the MEMS comb linear vibration gyroscope. The paper shows the relationship between the air pressure and the output amplified and phase of the detecting axis through analyzing the air pressure influence on the MEMS comb linear vibration gyroscope. It discusses the influence on the frequency distribute and quality factor of the MEMS comb linear vibration gyroscope for different air pressure.
Biodegradable Polylactic Acid (PLA) Microstructures for Scaffold Applications
Venue: arXiv cs.OH 2008
Year: 2008

In this research, we present a simple and cost effective soft lithographic process to fabricate PLA scaffolds for tissue engineering. In which, the negative photoresist JSR THB-120N was spun on a glass subtract followed by conventional UV lithographic processes to fabricate the master to cast the PDMS elastomeric mold. A thin poly(vinyl alcohol) (PVA) layer was used as a mode release such that the PLA scaffold can be easily peeled off. The PLA precursor solution was then cast onto the PDMS mold to form the PLA microstructures. After evaporating the solvent, the PLA microstructures can be easily peeled off from the PDMS mold. Experimental results show that the desired microvessels scaffold can be successfully transferred to the biodegradable polymer PLA.
Tuneable Capacitor based on dual picks profile of the sacrificial layer
Venue: arXiv cs.OH 2008
Year: 2008

In this paper, we present a novel dual gap tuneable capacitor process based on the profile of the sacrificial layer. This profile involves a tri-layer photo-resist process with only one mask level. This realization is based on a special profile of the sacrificial layer designed by two picks. The mechanism of the sacrificial layer realisation is dependent on resist thickness, resist formulation (viscosity, type of polymer and/or solvent, additives...), design of the patterned layer (size or width) and the conditions under which this layer is prepared: thermal treatment, etch back processes... In this communication we demonstrate influence of the later parameters and discuss how a dual pick profile was achieved.
Analysis of Asymmetric Piezoelectric Composite Beam
Venue: arXiv cs.OH 2008
Year: 2008

This paper deals with the vibration analysis of an asymmetric composite beam composed of glass a piezoelectric material. The Bernoulli's beam theory is adopted for mechanical deformations, and the electric potential field of the piezoelectric material is assumed such that the divergence-free requirement of the electrical displacements is satisfied. The accuracy of the analytic model is assessed by comparing the resonance frequencies obtained by the analytic model with those obtained by the finite element method. The model developed can be used as a tool for designing piezoelectric actuators such as micro-pumps.
0-level Vacuum Packaging RT Process for MEMS Resonators
Venue: arXiv cs.OH 2008
Year: 2008

A new Room Temperature (RT) 0-level vacuum package is demonstrated in this work, using amorphous silicon (aSi) as sacrificial layer and SiO2 as structural layer. The process is compatible with most of MEMS resonators and Resonant Suspended-Gate MOSFET [1] fabrication processes. This paper presents a study on the influence of releasing hole dimensions on the releasing time and hole clogging. It discusses mass production compatibility in terms of packaging stress during back-end plastic injection process. The packaging is done at room temperature making it fully compatible with IC-processed wafers and avoiding any subsequent degradation of the active devices.
Modeling of T-Shaped Microcantilever Resonators
Venue: arXiv cs.OH 2008
Year: 2008

The extensive research and development of micromechanical resonators is trying to allow the use of these devices for highly sensitive applications. Microcantilevers are some of the simplest MEMS structure and had been proved to be a good platform due to its excellent mechanical properties. A cantilever working in dynamic mode, adjust its resonance frequency depending on changes in both the spring constant (k) and mass (m) of the resonator. The aim of this work was to model a cantilever structure to determine the optimal dimensions in which the resonance frequency would be a function dominated by mass changes and not stiffness changes. In order to validate the model a set of microcantilevers were fabricated and characterized.
One MEMS Design Tool with Maximal Six Design Flows
Venue: arXiv cs.OH 2008
Year: 2008

This paper presents one MEMS design tool with total six design flows, which makes it possible that the MEMS designers are able to choose the most suitable design flow for their specific devices. The design tool is divided into three levels and interconnected by six interfaces. The three levels are lumped-element model based system level, finite element analysis based device level and process level, which covers nearly all modeling and simulation functions for MEMS design. The six interfaces are proposed to automatically transmit the design data between every two levels, thus the maximal six design flows could be realized. The interfaces take the netlist, solid model and layout as the data inlet and outlet for the system, device and process level respectively. The realization of these interfaces are presented and verified by design examples, which also proves that the enough flexibility in the design flow can really increase the design efficiency.
Use of Rapid Probabilistic Argumentation for Ranking on Large Complex Networks
Venue: arXiv cs.AI 2008
Year: 2008

We introduce a family of novel ranking algorithms called ERank which run in linear/near linear time and build on explicitly modeling a network as uncertain evidence. The model uses Probabilistic Argumentation Systems (PAS) which are a combination of probability theory and propositional logic, and also a special case of Dempster-Shafer Theory of Evidence. ERank rapidly generates approximate results for the NP-complete problem involved enabling the use of the technique in large networks. We use a previously introduced PAS model for citation networks generalizing it for all networks. We propose a statistical test to be used for comparing the performances of different ranking algorithms based on a clustering validity test. Our experimentation using this test on a real-world network shows ERank to have the best performance in comparison to well-known algorithms including PageRank, closeness, and betweenness.
Spreadsheet Errors: What We Know. What We Think We Can Do
Venue: arXiv cs.SE 2008
Year: 2008

Fifteen years of research studies have concluded unanimously that spreadsheet errors are both common and non-trivial. Now we must seek ways to reduce spreadsheet errors. Several approaches have been suggested, some of which are promising and others, while appealing because they are easy to do, are not likely to be effective. To date, only one technique, cell-by-cell code inspection, has been demonstrated to be effective. We need to conduct further research to determine the degree to which other techniques can reduce spreadsheet errors.
It Ain't What You View, But The Way That You View It: documenting spreadsheets with Excelsior, semantic wikis, and literate programming
Venue: arXiv cs.HC 2008
Year: 2008

I describe preliminary experiments in documenting Excelsior versions of spreadsheets using semantic wikis and literate programming. The objective is to create well-structured and comprehensive documentation, easy to use by those unfamiliar with the spreadsheets documented. I discuss why so much documentation is hard to use, and briefly explain semantic wikis and literate programming; although parts of the paper are Excelsior-specific, these sections may be of more general interest.
Establishing A Minimum Generic Skill Set For Risk Management Teaching In A Spreadsheet Training Course
Venue: arXiv cs.HC 2008
Year: 2008

Past research shows that spreadsheet models are prone to such a high frequency of errors and data security implications that the risk management of spreadsheet development and spreadsheet use is of great importance to both industry and academia. The underlying rationale for this paper is that spreadsheet training courses should specifically address risk management in the development process both from a generic and a domain-specific viewpoint. This research specifically focuses on one of these namely those generic issues of risk management that should be present in a training course that attempts to meet good-practice within industry. A pilot questionnaire was constructed showing a possible minimum set of risk management issues and sent to academics and industry practitioners for feedback. The findings from this pilot survey will be used to refine the questionnaire for sending to a larger body of possible respondents. It is expected these findings will form the basis of a risk management teaching approach to be trialled in a number of selected ongoing spreadsheet training courses.
Voice-controlled Debugging of Spreadsheets
Venue: arXiv cs.HC 2008
Year: 2008

Developments in Mobile Computing are putting pressure on the software industry to research new modes of interaction that do not rely on the traditional keyboard and mouse combination. Computer users suffering from Repetitive Strain Injury also seek an alternative to keyboard and mouse devices to reduce suffering in wrist and finger joints. Voice-control is an alternative approach to spreadsheet development and debugging that has been researched and used successfully in other domains. While voice-control technology for spreadsheets is available its effectiveness has not been investigated. This study is the first to compare the performance of a set of expert spreadsheet developers that debugged a spreadsheet using voice-control technology and another set that debugged the same spreadsheet using keyboard and mouse. The study showed that voice, despite its advantages, proved to be slower and less accurate. However, it also revealed ways in which the technology might be improved to redress this imbalance.
Wavelet and Curvelet Moments for Image Classification: Application to Aggregate Mixture Grading
Venue: arXiv cs.CV 2008
Year: 2008

We show the potential for classifying images of mixtures of aggregate, based themselves on varying, albeit well-defined, sizes and shapes, in order to provide a far more effective approach compared to the classification of individual sizes and shapes. While a dominant (additive, stationary) Gaussian noise component in image data will ensure that wavelet coefficients are of Gaussian distribution, long tailed distributions (symptomatic, for example, of extreme values) may well hold in practice for wavelet coefficients. Energy (2nd order moment) has often been used for image characterization for image content-based retrieval, and higher order moments may be important also, not least for capturing long tailed distributional behavior. In this work, we assess 2nd, 3rd and 4th order moments of multiresolution transform -- wavelet and curvelet transform -- coefficients as features. As analysis methodology, taking account of image types, multiresolution transforms, and moments of coefficients in the scales or bands, we use correspondence analysis as well as k-nearest neighbors supervised classification.