Finite-State Spell-Checking with Weighted Language and Error Models

In this paper we present simple methods for construction and evaluation of finite-state spell-checking tools using an existing finite-state lexical automaton, freely available finite-state tools and Internet corpora acquired from projects such as Wikipedia. As an example, we use a freely available open-source implementation of Finnish morphology, made with traditional finite-state morphology tools, and demonstrate rapid building of Northern Sámi and English spell checkers from tools and resources available from the Internet.

Algorithms for Routing and Centralized Scheduling in IEEE 802.16 Mesh Networks

IEEE 802.16 standards for Wireless Metropolitan Area Networks (WMANs) include a mesh mode of operation for improving the coverage and throughput of the network. In this paper, we consider the problem of routing and centralized scheduling for such networks. We first fix the routing, which reduces the network to a tree. We then present a finite horizon dynamic programming framework. Using it we obtain various scheduling algorithms depending upon the cost function. Next we consider simpler suboptimal algorithms and compare their performances.

Efficient and Fair Scheduling of Uplink and Downlink in IEEE 802.16 OFDMA Networks

We develop new scheduling algorithms for the IEEE 802.16d OFDMA/TDD based broadband wireless access system, in which radio resources of both time and frequency slots are dynamically shared by all users. Our objective is to provide a fair and efficient allocation to all the users to satisfy their quality of service.

Heuristic algorithms for scheduling of a batch processor in automobile gear manufacturing

In this paper we address a scheduling problem for minimising total weighted tardiness. The motivation for the paper comes from the automobile gear manufacturing process. We consider the bottleneck operation of heat treatment stage of gear manufacturing. Real life scenarios like unequal release times, incompatible job families, non-identical job sizes and allowance for job splitting have been considered. A mathematical model taking into account dynamic starting conditions has been developed. Due to the NP-hard nature of the problem, a few heuristic algorithms have been proposed. The performance of the proposed heuristic algorithms is evaluated: (a) in comparison with optimal solution for small size problem instances, and (b) in comparison with `estimated optimal solution' for large size problem instances. Extensive computational analyses reveal that the proposed heuristic algorithms are capable of consistently obtaining near-optimal solutions (that is, statistically estimated one) in very reasonable computational time.

Past Queue Length Based Low-Overhead Link Scheduling in Multi-beam Wireless Mesh Networks

Wireless mesh networks with multi-beam capability at each node through the use of multi-antenna beamforming are becoming practical and attracting increased research attention. Increased capacity due to spatial reuse and increased transmission range are potential benefits in using multiple directional beams in each node. In this paper, we are interested in low-complexity scheduling algorithms in such multi-beam wireless networks. In particular, we present a scheduling algorithm based on queue length information of the past slots in multi-beam networks, and prove its stability. We present a distributed implementation of this proposed algorithm. Numerical results show that significant improvement in delay performance is achieved using the proposed multi-beam scheduling compared to omni-beam scheduling. In addition, the proposed algorithm is shown to achieve a significant reduction in the signaling overhead compared to a current slot queue length approach.

Dynamic scheduling in manufacturing systems using brownian approximations

Recently, Brownian networks have emerged as an effective stochastic model to approximate multiclass queueing networks with dynamic scheduling capability, under conditions of balanced heavy loading. This paper is a tutorial introduction to dynamic scheduling in manufacturing systems using Brownian networks. The article starts with motivational examples. It then provides a review of relevant weak convergence concepts, followed by a description of the limiting behaviour of queueing systems under heavy traffic. The Brownian approximation procedure is discussed in detail and generic case studies are provided to illustrate the procedure and demonstrate its effectiveness. This paper places emphasis only on the results and aspires to provide the reader with an up-to-date understanding of dynamic scheduling based on Brownian approximations.

Effective action and adiabatic expansions for the 1-D and 2-D hubbard models at half-filling

We analyze here the occurrence of antiferromagnetic (AFM) correlations in the half-filled Hubbard model in one and two space dimensions using a natural fermionic representation of the model and a newly proposed way of implementing the half-filling constraint. We find that our way of implementing the constraint is capable of enforcing it exactly already at the lowest levels of approximation. We discuss how to develop a systematic adiabatic expansion for the model and how Berry's phase contributions arise quite naturally from the adiabatic expansion. At low temperatures and in the continuum limit the model gets mapped onto an O(3) nonlinear sigma model (NLsigma). A topological, Wess-Zumino term is present in the effective action of the ID NLsigma as expected, while no topological terms are present in 2D. Some specific difficulties that arise in connection with the implementation of an adiabatic expansion scheme within a thermodynamic context are also discussed, and we hint at possible solutions.

Electrochemical phase formation involving multicomponents: hemispherical overlap models for varied nucleation and growth conditions

The phenomenological theory of hemispherical growth in the context of phase formation with more than one component is presented. The model discusses in a unified manner both instantaneous and progressive nucleation (at the substrate) as well as arbitrary growth rates (e.g. constant and diffusion controlled growth rates). A generalized version of Avrami ansatz (a mean field description) is used to tackle the ''overlap'' aspects arising from the growing multicentres of the many components involved, observing that the nucleation is confined to the substrate plane only. The time evolution of the total extent of macrogrowth as well as those of the individual components are discussed explicitly for the case of two phases. The asymptotic expressions for macrogrowth are derived. Such analysis depicts a saturation limit (i.e. the maximum extent of growth possible) for the slower growing component and its dependence on the kinetic parameters which, in the electrochemical context, can be controlled through potential. The significance of this model in the context of multicomponent alloy deposition and possible future directions for further development are pointed out.

An Efficient Simulated Annealing With a Valid Solution Mechanism For TDMA Brodcast Scheduling problem

This paper presents an efficient Simulated Annealing with valid solution mechanism for finding an optimum conflict-free transmission schedule for a broadcast radio network. This is known as a Broadcast Scheduling Problem (BSP) and shown as an NP-complete problem, in earlier studies. Because of this NP-complete nature, earlier studies used genetic algorithms, mean field annealing, neural networks, factor graph and sum product algorithm, and sequential vertex coloring algorithm to obtain the solution. In our study, a valid solution mechanism is included in simulated annealing. Because of this inclusion, we are able to achieve better results even for networks with 100 nodes and 300 links. The results obtained using our methodology is compared with all the other earlier solution methods.

Verifying scalings for bending rigidity of bilayer membranes using mesoscale models

The bending rigidity kappa of bilayer membranes was studied with coarse grained soft repulsive potentials using dissipative particle dynamics (DPD) simulations. Using a modified Andersen barostat to maintain the bilayers in a tensionless state, the bending rigidity was obtained from a Fourier analysis of the height fluctuations. From simulations carried out over a wide range of membrane thickness, the continuum scaling relation kappa proportional to d(2) was captured for both the L-alpha and L-beta phases. For membranes with 4 to 6 tail beads, the bending rigidity in the L-beta phase was found to be 10-15 times higher than that observed for the L-alpha phase. From the quadratic scalings obtained, a six fold increase in the area stretch modulus, k(A) was observed across the transition. The magnitude of increase in both kappa and k(A) from the L-alpha to the L-beta phase is consistent with current experimental observations in lipid bilayers and to our knowledge provides for the first time a direct evaluation of the mechanical properties in the L-beta phase.

Field evaluation of unsaturated hydraulic conductivity models and parameter estimation from retention data

Predictions of two popular closed-form models for unsaturated hydraulic conductivity (K) are compared with in situ measurements made in a sandy loam field soil. Whereas the Van Genuchten model estimates were very close to field measured values, the Brooks-Corey model predictions were higher by about one order of magnitude in the wetter range. Estimation of parameters of the Van Genuchten soil moisture characteristic (SMC) equation, however, involves the use of non-linear regression techniques. The Brooks-Corey SMC equation has the advantage of being amenable to application of linear regression techniques for estimation of its parameters from retention data. A conversion technique, whereby known Brooks-Corey model parameters may be converted into Van Genuchten model parameters, is formulated. The proposed conversion algorithm may be used to obtain the parameters of the preferred Van Genuchten model from in situ retention data, without the use of non-linear regression techniques.

Critical earthquake input power spectral density function models for engineering structures

The problem of determining optimal power spectral density models for earthquake excitation which satisfy constraints on total average power, zero crossing rate and which produce the highest response variance in a given linear system is considered. The solution to this problem is obtained using linear programming methods. The resulting solutions are shown to display a highly deterministic structure and, therefore, fail to capture the stochastic nature of the input. A modification to the definition of critical excitation is proposed which takes into account the entropy rate as a measure of uncertainty in the earthquake loads. The resulting problem is solved using calculus of variations and also within linear programming framework. Illustrative examples on specifying seismic inputs for a nuclear power plant and a tall earth dam are considered and the resulting solutions are shown to be realistic.

Sibling rivalry between seeds within a fruit: Some population genetic models

Competition between seeds within a fruit for parental resources is described using one-locus-two-allele models. While a �normal� allele leads to an equitable distribution of resources between seeds (a situation which also corresponds to the parental optimum), the �selfish� allele is assumed to cause the seed carrying it to usurp a higher proportion of the resources. The outcome of competition between �selfish� alleles is also assumed to lead to an asymmetric distribution of resources, the �winner� being chosen randomly. Conditions for the spread of an initially rare selfish allele and the optimal resource allocation corresponding to the evolutionarily stable strategy, derived for species with n-seeded fruits, are in accordance with expectations based on Hamilton�s inclusive fitness criteria. Competition between seeds is seen to be most intense when there are only two seeds, and decreases with increasing number of seeds, suggesting that two-seeded fruits would be rarer than one-seeded or many-seeded ones. Available data from a large number of plant species are consistent with this prediction of the model.