OpenRaiser/Intern-Atlas huggingface dataset:
Instruction sequences with indirect jumps
Venue: arXiv cs.PL 2007
Year: 2007

We study sequential programs that are instruction sequences with direct and indirect jump instructions. The intuition is that indirect jump instructions are jump instructions where the position of the instruction to jump to is the content of some memory cell. We consider several kinds of indirect jump instructions. For each kind, we define the meaning of programs with indirect jump instructions of that kind by means of a translation into programs without indirect jump instructions. For each kind, the intended behaviour of a program with indirect jump instructions of that kind under execution is the behaviour of the translated program under execution on interaction with some memory device.
SWI-Prolog and the Web
Venue: arXiv cs.PL 2007
Year: 2007

Where Prolog is commonly seen as a component in a Web application that is either embedded or communicates using a proprietary protocol, we propose an architecture where Prolog communicates to other components in a Web application using the standard HTTP protocol. By avoiding embedding in external Web servers development and deployment become much easier. To support this architecture, in addition to the transfer protocol, we must also support parsing, representing and generating the key Web document types such as HTML, XML and RDF. This paper motivates the design decisions in the libraries and extensions to Prolog for handling Web documents and protocols. The design has been guided by the requirement to handle large documents efficiently. The described libraries support a wide range of Web applications ranging from HTML and XML documents to Semantic Web RDF processing. To appear in Theory and Practice of Logic Programming (TPLP)
Dynamic aspects of individual design activities. A cognitive ergonomics viewpoint
Venue: arXiv cs.HC 2007
Year: 2007

This paper focuses on the use of knowledge possessed by designers. Data collection was based on observations (by the cognitive ergonomics researcher) and simultaneous verbalisations (by the designers) in empirical studies conducted in the context of industrial design projects. The contribution of this research is typical of cognitive ergonomics, in that it provides data on actual activities implemented by designers in their actual work situation (rather than on prescribed and/or idealised processes and methods). Data presented concern global strategies (the way in which designers actually organise their activity) and local strategies (reuse in design). Results from cognitive ergonomics and other research that challenges the way in which people are supposed to work with existing systems are generally not received warmly. Abundant corroboration of such results is required before industry may consider taking them into account. The opportunistic organisation of design activity is taken here as an example of this reluctance. The results concerning this aspect of design have been verified repeatedly, but only prototypes and experimental systems implementing some of the requirements formulated on their basis, are under development.
On Minimal Tree Realizations of Linear Codes
Venue: arXiv cs.IT 2007
Year: 2007

A tree decomposition of the coordinates of a code is a mapping from the coordinate set to the set of vertices of a tree. A tree decomposition can be extended to a tree realization, i.e., a cycle-free realization of the code on the underlying tree, by specifying a state space at each edge of the tree, and a local constraint code at each vertex of the tree. The constraint complexity of a tree realization is the maximum dimension of any of its local constraint codes. A measure of the complexity of maximum-likelihood decoding for a code is its treewidth, which is the least constraint complexity of any of its tree realizations. It is known that among all tree realizations of a code that extends a given tree decomposition, there exists a unique minimal realization that minimizes the state space dimension at each vertex of the underlying tree. In this paper, we give two new constructions of these minimal realizations. As a by-product of the first construction, a generalization of the state-merging procedure for trellis realizations, we obtain the fact that the minimal tree realization also minimizes the local constraint code dimension at each vertex of the underlying tree. The second construction relies on certain code decomposition techniques that we develop. We further observe that the treewidth of a code is related to a measure of graph complexity, also called treewidth. We exploit this connection to resolve a conjecture of Forney's regarding the gap between the minimum trellis constraint complexity and the treewidth of a code. We present a family of codes for which this gap can be arbitrarily large.
Capacity as a Fundamental Metric for Mechanism Design in the Information Economy
Venue: arXiv cs.GT 2007
Year: 2007

The auction theory literature has so far focused mostly on the design of mechanisms that takes the revenue or the efficiency as a yardstick. However, scenarios where the {\it capacity}, which we define as \textit{``the number of bidders the auctioneer wants to have a positive probability of getting the item''}, is a fundamental concern are ubiquitous in the information economy. For instance, in sponsored search auctions (SSA's) or in online ad-exchanges, the true value of an ad-slot for an advertiser is inherently derived from the conversion-rate, which in turn depends on whether the advertiser actually obtained the ad-slot or not; thus, unless the capacity of the underlying auction is large, key parameters, such as true valuations and advertiser-specific conversion rates, will remain unknown or uncertain leading to inherent inefficiencies in the system. In general, the same holds true for all information goods/digital goods. We initiate a study of mechanisms, which take capacity as a yardstick, in addition to revenue/efficiency. We show that in the case of a single indivisible item one simple way to incorporate capacity constraints is via designing mechanisms to sell probability distributions, and that under certain conditions, such optimal probability distributions could be identified using a Linear programming approach. We define a quantity called {\it price of capacity} to capture the tradeoff between capacity and revenue/efficiency. We also study the case of sponsored search auctions. Finally, we discuss how general such an approach via probability spikes can be made, and potential directions for future investigations.
An analysis of a random algorithm for estimating all the matchings
Venue: arXiv cs.CC 2007
Year: 2007

Counting the number of all the matchings on a bipartite graph has been transformed into calculating the permanent of a matrix obtained from the extended bipartite graph by Yan Huo, and Rasmussen presents a simple approach (RM) to approximate the permanent, which just yields a critical ratio O($nω(n)$) for almost all the 0-1 matrices, provided it's a simple promising practical way to compute this #P-complete problem. In this paper, the performance of this method will be shown when it's applied to compute all the matchings based on that transformation. The critical ratio will be proved to be very large with a certain probability, owning an increasing factor larger than any polynomial of $n$ even in the sense for almost all the 0-1 matrices. Hence, RM fails to work well when counting all the matchings via computing the permanent of the matrix. In other words, we must carefully utilize the known methods of estimating the permanent to count all the matchings through that transformation.
A Geometric Interpretation of Fading in Wireless Networks: Theory and Applications
Venue: arXiv cs.IT 2007
Year: 2007

In wireless networks with random node distribution, the underlying point process model and the channel fading process are usually considered separately. A unified framework is introduced that permits the geometric characterization of fading by incorporating the fading process into the point process model. Concretely, assuming nodes are distributed in a stationary Poisson point process in $\R^d$, the properties of the point processes that describe the path loss with fading are analyzed. The main applications are connectivity and broadcasting.
Bi-capacities -- Part II: the Choquet integral
Venue: arXiv cs.DM 2007
Year: 2007

Bi-capacities arise as a natural generalization of capacities (or fuzzy measures) in a context of decision making where underlying scales are bipolar. They are able to capture a wide variety of decision behaviours, encompassing models such as Cumulative Prospect Theory (CPT). The aim of this paper in two parts is to present the machinery behind bi-capacities, and thus remains on a rather theoretical level, although some parts are firmly rooted in decision theory, notably cooperative game theory. The present second part focuses on the definition of Choquet integral. We give several expressions of it, including an expression w.r.t. the Möbius transform. This permits to express the Choquet integral for 2-additive bi-capacities w.r.t. the interaction index.
Mise en place de scénarios pour la conception d'outils en Chirurgie Minimalement Invasive
Venue: arXiv cs.HC 2007
Year: 2007

Nowadays, more and more surgical interventions are carried out in Minimally Invasive Surgery, to make the post-operative constraints less painful for the patient. Actually, new surgical tools or medical products are designed after informal discussions between surgeons and designers. The user requirements documents are the main document used by the mechanical designers to design and improve the product. Medical terms, often used by surgeons and employed to explain their needs, don't allow for an instantaneous understanding by designers. Unfortunately, this relation causes a dysfunction in the definition cycle of the product. Our aim is to work on the design process, its assistance thanks to methods and tools and on its organisation for better understandings and more complementarities between surgeons and designers. We propose on this article a design method already tested in the informatics domain: User Centred Design which takes the user into account more effectively in the process design. We already propose a scenario oriented design method centred on the user and represented as a scenario (Scenario-Based Design). We start in this article by clarifying these concepts before detailing their implementation for the design of a new surgical tool.
Proof nets for display logic
Venue: arXiv cs.CL 2007
Year: 2007

This paper explores several extensions of proof nets for the Lambek calculus in order to handle the different connectives of display logic in a natural way. The new proof net calculus handles some recent additions to the Lambek vocabulary such as Galois connections and Grishin interactions. It concludes with an exploration of the generative capacity of the Lambek-Grishin calculus, presenting an embedding of lexicalized tree adjoining grammars into the Lambek-Grishin calculus.
Interference Alignment on the Deterministic Channel and Application to Fully Connected AWGN Interference Networks
Venue: arXiv cs.IT 2007
Year: 2007

An interference alignment example is constructed for the deterministic channel model of the $K$ user interference channel. The deterministic channel example is then translated into the Gaussian setting, creating the first known example of a fully connected Gaussian $K$ user interference network with single antenna nodes, real, non-zero and contant channel coefficients, and no propagation delays where the degrees of freedom outerbound is achieved. An analogy is drawn between the propagation delay based interference alignment examples and the deterministic channel model which also allows similar constructions for the 2 user $X$ channel as well.
Finding a Feasible Flow in a Strongly Connected Network
Venue: arXiv cs.DS 2007
Year: 2007

We consider the problem of finding a feasible single-commodity flow in a strongly connected network with fixed supplies and demands, provided that the sum of supplies equals the sum of demands and the minimum arc capacity is at least this sum. A fast algorithm for this problem improves the worst-case time bound of the Goldberg-Rao maximum flow method by a constant factor. Erlebach and Hagerup gave an linear-time feasible flow algorithm. We give an arguably simpler one.
Parity Forwarding for Multiple-Relay Networks
Venue: arXiv cs.IT 2007
Year: 2007

This paper proposes a relaying strategy for the multiple-relay network in which each relay decodes a selection of transmitted messages by other transmitting terminals, and forwards parities of the decoded codewords. This protocol improves the previously known achievable rate of the decode-and-forward (DF) strategy for multirelay networks by allowing relays to decode only a selection of messages from relays with strong links to it. Hence, each relay may have several choices as to which messages to decode, and for a given network many different parity forwarding protocols may exist. A tree structure is devised to characterize a class of parity forwarding protocols for an arbitrary multirelay network. Based on this tree structure, closed-form expressions for the achievable rates of these DF schemes are derived. It is shown that parity forwarding is capacity achieving for new forms of degraded relay networks.
Maximizing PageRank via outlinks
Venue: arXiv cs.IR 2007
Year: 2007

We analyze linkage strategies for a set I of webpages for which the webmaster wants to maximize the sum of Google's PageRank scores. The webmaster can only choose the hyperlinks starting from the webpages of I and has no control on the hyperlinks from other webpages. We provide an optimal linkage strategy under some reasonable assumptions.
Estimation of fuzzy anomalies in Water Distribution Systems
Venue: arXiv cs.NE 2007
Year: 2007

State estimation is necessary in diagnosing anomalies in Water Demand Systems (WDS). In this paper we present a neural network performing such a task. State estimation is performed by using optimization, which tries to reconcile all the available information. Quantification of the uncertainty of the input data (telemetry measures and demand predictions) can be achieved by means of robust estate estimation. Using a mathematical model of the network, fuzzy estimated states for anomalous states of the network can be obtained. They are used to train a neural network capable of assessing WDS anomalies associated with particular sets of measurements.
Parasitic Effects Reduction for Wafer-Level Packaging of RF-Mems
Venue: arXiv cs.OH 2007
Year: 2007

In RF-MEMS packaging, next to the protection of movable structures, optimization of package electrical performance plays a very important role. In this work, a wafer-level packaging process has been investigated and optimized in order to minimize electrical parasitic effects. The RF-MEMS package concept used is based on a wafer-level bonding of a capping silicon substrate to an RF-MEMS wafer. The capping silicon substrate resistivity, substrate thickness and the geometry of through-substrate electrical interconnect vias have been optimized using finite-element electromagnetic simulations (Ansoft HFSS). Test structures for electrical characterization have been designed and after their fabrication, measurement results will be compared with simulations.
Electromechanical Reliability Testing of Three-Axial Silicon Force Sensors
Venue: arXiv cs.OH 2007
Year: 2007

This paper reports on the systematic electromechanical characterization of a new three-axial force sensor used in dimensional metrology of micro components. The siliconbased sensor system consists of piezoresistive mechanicalstress transducers integrated in thin membrane hinges supporting a suspended flexible cross structure. The mechanical behavior of the fragile micromechanical structure isanalyzed for both static and dynamic load cases. This work demonstrates that the silicon microstructure withstands static forces of 1.16N applied orthogonally to the front-side of the structure. A statistical Weibull analysis of the measured data shows that these values are significantly reduced if the normal force is applied to the back of the sensor. Improvements of the sensor system design for future development cycles are derived from the measurement results.
An Active Chaotic Micromixer Integrating Thermal Actuation Associating PDMS and Silicon Microtechnology
Venue: arXiv cs.OH 2007
Year: 2007

Due to scaling laws, in microfluidic, flows are laminar. Consequently, mixing between two liquids is mainly obtained by natural diffusion which may take a long time or equivalently requires centimetre length channels. To reduce time and length for mixing, it is possible to generate chaotic-like flows either by modifying the channel geometry or by creating an external perturbation of the flow. In this paper, an active micromixer is presented consisting on thermal actuation with heating resistors. In order to disturb the liquid flow, an oscillating transverse flow is generated by heating the liquid. Depending on the value of boiling point, either bubble expansion or volumetric dilation controlled the transverse flow amplitude. A chaotic like mixing is then induced under particular conditions depending on volume expansion, liquid velocity, frequency of actuation... This solution presents the advantage to achieve mixing in a very short time (1s) and along a short channel distance (channel width). It can also be integrated in a more complex device due to actuator integration with microfluidics.
Packaging of RF Mems Switching Functions on Alumina Substrate
Venue: arXiv cs.OH 2007
Year: 2007

Recently the strong demands in wireless communication requires expanding development for the application of RF MEMS (Radio Frequency micro electro mechanical systems) sensing devices such as micro-switches, tunable capacitors because it offers lower power consumption, lower losses, higher linearity and higher Q factors compared with conventional communications components. To accelerate commercialisation of RF MEMS products, development for packaging technologies is one of the most critical issues should be solved beforehand.
Influence of Micro-Cantilever Geometry and Gap on Pull-in Voltage
Venue: arXiv cs.OH 2007
Year: 2007

In this paper, we study the behaviour of a microcantilever beam under electrostatic actuation using finite difference method. This problem has a lot of applications in MEMS based devices like accelerometers, switches and others. In this paper, we formulated the problem of a cantilever beam with proof mass at its end and carried out the finite difference solution. we studied the effects of length, width, and the gap size on the pull-in voltage using data that are available in the literature. Also, the stability limit is compared with the single degree of freedom commonly used in the earlier literature as an approximation to calculate the pull-in voltage.
A Novel Contact Resistance Model of Anisotropic Conductive Film for FPD Packaging
Venue: arXiv cs.OH 2007
Year: 2007

In this research, a novel contact resistance model for the flat panel display (FPD) packaging based on the within layer parallel and between layers series resistance concepts was proposed. The FJ2530 anisotropic conductive films (ACF) by Sony Inc. containing the currently smallest 3micron conductive particles was used to conduct the experiments to verify the accuracy of the proposed model. Calculated resistance of the chip-on-glass (COG) packaging by the proposed model is 0.163Ω. It is found that the gold bump with 0.162Ωresistance play the major role of the overall resistance. Although the predicted resistance by the proposed model is only one third of the experimentally measured value, it has been three-fold improvement compared to the existing models.
Scaling Effects for Electromagnetic Vibrational Power Generators
Venue: arXiv cs.OH 2007
Year: 2007

This paper investigates how the power generated by electromagnetic based vibrational power generators scales with the dimension of the generator. The effects of scaling on the magnetic fields, the coil parameters and the electromagnetic damping are presented. An analysis is presented for both wire-wound coil technology and micro-fabricated coils.
Au-SN Flip-Chip Solder Bump for Microelectronic and Optoelectronic Applications
Venue: arXiv cs.OH 2007
Year: 2007

As an alternative to the time-consuming solder pre-forms and pastes currently used, a co-electroplating method of eutectic Au-Sn alloy was used in this study. Using a co-electroplating process, it was possible to plate the Au-Sn solder directly onto a wafer at or near the eutectic composition from a single solution. Two distinct phases, Au5Sn and AuSn, were deposited at a composition of 30at.%Sn. The Au-Sn flip-chip joints were formed at 300 and 400 degrees without using any flux. In the case where the samples were reflowed at 300 degrees, only an (Au,Ni)3Sn2 IMC layer formed at the interface between the Au-Sn solder and Ni UBM. On the other hand, two IMC layers, (Au,Ni)3Sn2 and (Au,Ni)3Sn, were found at the interfaces of the samples reflowed at 400 degrees. As the reflow time increased, the thickness of the (Au,Ni)3Sn2 and (Au,Ni)3Sn IMC layers formed at the interface increased and the eutectic lamellae in the bulk solder coarsened.
A resource-based Korean morphological annotation system
Venue: arXiv cs.CL 2007
Year: 2007

We describe a resource-based method of morphological annotation of written Korean text. Korean is an agglutinative language. The output of our system is a graph of morphemes annotated with accurate linguistic information. The language resources used by the system can be easily updated, which allows us-ers to control the evolution of the per-formances of the system. We show that morphological annotation of Korean text can be performed directly with a lexicon of words and without morpho-logical rules.
An FPT Algorithm for Directed Spanning k-Leaf
Venue: arXiv cs.DS 2007
Year: 2007

An out-branching of a directed graph is a rooted spanning tree with all arcs directed outwards from the root. We consider the problem of deciding whether a given directed graph D has an out-branching with at least k leaves (Directed Spanning k-Leaf). We prove that this problem is fixed parameter tractable, when k is chosen as the parameter. Previously this was only known for restricted classes of directed graphs. The main new ingredient in our approach is a lemma that shows that given a locally optimal out-branching of a directed graph in which every arc is part of at least one out-branching, either an out-branching with at least k leaves exists, or a path decomposition with width O(k^3) can be found. This enables a dynamic programming based algorithm of running time 2^{O(k^3 \log k)} n^{O(1)}, where n=|V(D)|.