On finite automata with limited nondeterminism

We develop a new algorithm for determining if a given nondeterministic finite automaton is limited in nondeterminism. From this, we show that the number of nondeterministic moves of a finite automaton, if limited, is bounded by where is the number of states. If the finite automaton is over a one-letter alphabet, using Gohon's result the number of nondeterministic moves, if limited, is less than . In both cases, we present families of finite automata demonstrating that the upper bounds obtained are almost tight. We also show that the limitedness problem of the number of nondeterministic moves of finite automata is PSPACE-hard. Since the problem is already known to be in PSPACE, it is therefore PSPACE-complete. Received: 14 June 1994 / 3 December 1997     

Design of fuzzy controllers for uncertain nonlinear systems using stability and robustness analyses

This paper analyzes the stability and robustness of uncertain nonlinear systems and shows that the analysis results provide an efficient technique for the design of fuzzy controllers. Based on a fuzzy plant model describing an uncertain nonlinear plant, this design involves the derivation of a stability criterion and a robust area in the uncertain parameter space in terms of some measures of the closed-loop control system matrices. An application example on balancing an inverted pendulum is given to illustrate the simple design methodology, the stability and the robustness of the feedback system incorporated with the proposed fuzzy controller.     

Approximation algorithms for multi-agent scheduling to minimize total weighted completion time

We consider a multi-agent scheduling problem on a single machine in which each agent is responsible for his own set of jobs and wishes to minimize the total weighted completion time of his own set of jobs. It is known that the unweighted problem with two agents is NP-hard in the ordinary sense. For this case, we can reduce our problem to a Multi-Objective Shortest-Path (MOSP) problem and this reduction leads to several results including Fully Polynomial Time Approximation Schemes (FPTAS). We also provide an efficient approximation algorithm with a reasonably good worst-case ratio.     

Approaches to attribute reduction in concept lattices induced by axialities

This paper investigates approaches to attribute reduction in concept lattices induced by axialities. Based on an axiality, a type of covariant Galois connection between power sets, or equivalently a binary relation between the ground sets, the lattice of all concepts associated with a formal context is studied. Some judgment theorems for attribute reduction in such a lattice are proposed and proved. Extended from the idea of knowledge reduction in rough set theory, a Boolean approach to calculating all reducts of a context is formulated via the use of discernibility function. Finally, all attributes are classified into three types by their significance in constructing the concept lattice. The characteristics of these types of attributes are also analyzed.     

The dynamic optimization approach to locomotion dynamics: human-like gaits from a minimally-constrained biped model

This work presents a unifying framework to study energy-efficient optimal gaits for a bipedal model without elastic elements. The model includes a torso, flat feet, and telescoping legs, equipped with rotational hip and ankle joints. Two general types of gaits are studied: with and without a flight phase. The support surface can be level ground, sloped, or staircase. The algorithm achieves the optimum within the admissible space by using a minimal set of realistic physical constraints, and avoiding a priori assumptions on kinetic and kinematic parameters such as extended or instantaneous double-support, collisional or collisionless foot-ground contact, step length, step period, etc. The gait optimization for this simple model predicts many features of human locomotion including the optimality of pendular walking and impulsive running at slow and fast progression speeds, ankle push-off prior to touch-down, swing leg retraction, landing on a near vertical leg in gaits with flight phase, and burst hip torques at both ends of the swing phase.     

A Lagrangian relaxation-based method and models evaluation for multi-level lot sizing problems with backorders

The capacitated multi-level lot sizing problem with backorders has received a great deal of attention in extant literature on operations and optimization. The facility location model and the classical inventory and lot sizing model with (?$?$, S) cuts have been proposed to formulate this problem. However, their comparative effectiveness has not yet been explored and is not known. In this paper, we demonstrate that on linear programming relaxation, the facility location formulation yields tighter lower bounds than classical inventory and lot sizing model. It further shows that the facility location formulation is computationally advantageous for deriving both lower and upper bounds. The results are expected to provide guidelines for choosing an effective formulation during the development of solution procedures. We also propose a Lagrangian relaxation-based heuristic along with computational results that indicate its competitiveness with other heuristics and a prominent commercial solver, Cplex 11.2.     

Factors contributing to officers' fatigue in high-speed maritime craft operations

The purpose of this study was to investigate the difference in the level of fatigue induced by high-speed maritime craft operation between the day- and night-shift officers. The demographic and work-related factors that contribute to fatigue were also explored. A total of 93 high-speed maritime craft officers participated in the survey, of whom 35 worked a day shift (Mean age=48.3 years) and 58 worked a night shift (Mean age=45.8 years). Fatigue experience was measured with the Chinese version of the Swedish Occupational Fatigue Inventory (SOFI-C) at the beginning, in the middle and at the end of the work shift. Information on age, work experience, perceived voyage difficulty and duty schedule was obtained. The study found that the night-shift officers seemed to manifest an overall higher level of perceived fatigue than the day-shift officers, while the day-shift officers demonstrated a fatigue carry-over effect across the two workdays. Besides the shift pattern, age, experience in operating high-speed maritime craft and perceived voyage difficulty were the significant factors contributing to the officers' fatigue experience. The finding that the fatigue experience associated with high-speed maritime craft operation has a rapid and accumulative nature suggests that different occupational safety and health guidelines should be devised for these two groups of officers.     

Top-k typicality queries and efficient query answering methods on large databases

Finding typical instances is an effective approach to understand and analyze large data sets. In this paper, we apply the idea of typicality analysis from psychology and cognitive science to database query answering, and study the novel problem of answering top-k typicality queries. We model typicality in large data sets systematically. Three types of top-k typicality queries are formulated. To answer questions like “Who are the top-k most typical NBA players?”, the measure of simple typicality is developed. To answer questions like “Who are the top-k most typical guards distinguishing guards from other players?”, the notion of discriminative typicality is proposed. Moreover, to answer questions like “Who are the best k typical guards in whole representing different types of guards?”, the notion of representative typicality is used. Computing the exact answer to a top-k typicality query requires quadratic time which is often too costly for online query answering on large databases. We develop a series of approximation methods for various situations: (1) the randomized tournament algorithm has linear complexity though it does not provide a theoretical guarantee on the quality of the answers; (2) the direct local typicality approximation using VP-trees provides an approximation quality guarantee; (3) a local typicality tree data structure can be exploited to index a large set of objects. Then, typicality queries can be answered efficiently with quality guarantees by a tournament method based on a Local Typicality Tree. An extensive performance study using two real data sets and a series of synthetic data sets clearly shows that top-k typicality queries are meaningful and our methods are practical.     

A Performance Tradeoff Function for Evaluating Suggested Parameters in the Reactive Ion Etching Process

Reactive ion etching (RIE) is a process in the fabrication of semiconductor devices. The ability to predict the influence of the process parameters of RIE is crucial in terms of machine performance as they may have a serious impact on product quality as well as on the probability of machine failure. To address this issue, this correspondence paper presents a novel performance tradeoff function for evaluating the overall suitability of adopting the predicted control parameters suggested by domain experts, taking into full consideration their impact on the performance of the machine involved. An experiment using the RIE machine is provided to validate the practicability of the proposed approach.