bluuebunny/crossref_metadata_2025 huggingface dataset:
A HYBRID CONTINUOUS SPEECH RECOGNITION SYSTEM USING SEGMENTAL NEURAL NETS WITH HIDDEN MARKOV MODELS
Authors: ZAVALIAGKOS G. , AUSTIN S. , MAKHOUL J. , SCHWARTZ R.
Published: November 2004

Up till recently, state-of-the-art, large vocabulary, continuous speech recognition (CSR) had employed hidden Markov modeling (HMM) to model speech sounds. In an attempt to improve over HMM we developed a hybrid system that integrates HMM technology with neural networks.

We present the concept of a Segmental Neural Net (SNN) for phonetic modeling in CSR. By taking into account all the frames of a phonetic segment simultaneously, the SNN overcomes the well-known conditional-independence limitation of HMMs. We have developed a novel hybrid SNN/HMM system that combines the advantages of SNNs and HMMs using a multiple hypothesis (or N-best) paradigm. In this system, we generate likely phonetic segmentations from the HMM N-best list of word sequences, which are scored by the SNN. The HMM and SNN scores are then combined to optimize performance.

In several speaker-independent, 1000-word CSR tests, the error rate for the hybrid system dropped 20% from that of a state-of-the-art HMM system alone.
A PARALLEL THINNING ALGORITHM USING K×K MASKS
Authors: POTY VIRGINIE , UBEDA STÉPHANE
Published: November 2004

Thinning is a standard kernel in pattern recognition. Both serial and parallel algorithms have been investigated. Two classes of thinning algorithms can be defined: thinning techniques that use a raster-scanning of the whole image and a mask applied on each pixel, and thinning techniques that use a contour generation of the whole image as a basic operation of the thinning operation. The goal of this paper is to increase the speed of mask thinning algorithms by increasing the size of the thinning window.
AUTOMATIC COMPARISON OF SKELETONS BY SHAPE MATCHING METHODS
Authors: LAM LOUISA , SUEN CHING Y.
Published: November 2004

Whilst the design of skeletonization algorithms has been a very active research area, methodologies for an automatic evaluation of the quality of the results remain to be developed. The difficulty rests on the fact that certain geometric properties considered desirable in skeletons (especially for pattern recognition applications) are not easily quantifiable by means other than human vision. The attempt here is to develop distance measures based on shape matching methods, and to compare skeletons to references in terms of these distances. Three such methods have been adapted for this purpose, and the results are found to be highly correlated for the samples tested.
AUTOMATION IN MAMMOGRAPHY: COMPUTER VISION AND HUMAN PERCEPTION
Authors: ASTLEY SUE , HUTT IAN , MILLER PETER , ROSE PETER , TAYLOR CHRIS , BOGGIS CAROLINE , ADAMSON STEPHEN , VALENTINE TIM , DAVIES JACK , ARMSTRONG JANETTE
Published: November 2004

Mammographic screening programmes generate large numbers of highly variable, complex images, most of which are unequivocally normal. When present, abnormalities may be small or subtle. Two processes critical to the success of screening programmes are the perception of potential abnormalities and the subsequent analy-sis of each detected lesion to determine its clinical significance. The consequences of errors are costly, and in many screening centres, films are read by two radiologists in an attempt to reduce errors. The prime objective of our research is to improve the accuracy of the detection and analysis of breast lesions by providing radiologists with computer-aided digital image analysis tools. In this paper we focus on the detection and analysis of mammographic microcalcifications.

We describe a philosophy of research aimed at generating useful computer-based aids for radiologists. Firstly, it is necessary to accurately identify specific tasks which are difficult for the human observer. Having correctly identified a problem, appropriate computer vision methods must be developed and their performance evaluated. It is then important to determine effective ways of using such methods to aid radiologists, and it is essential to prove that the effect on radiologists’ performance is entirely beneficial.

We present results of experiments to determine factors affecting radiologists’ perception of microcalcifications, and to investigate the effects of attention-cueing on detection performance. Our results show that radiologists’ performance can be significantly improved with the use of prompts generated from automatically-detected microcalcification clusters.

We describe a new method for the delineation of mammographic abnormalities based on the analysis of multiple high quality X-ray projections of excised lesions. Biopsy specimens are secured inside a rigid tetrahedron, the edges of which provide a reference frame to which the locations of features can be related. A three-dimensional representation of an abnormality can be formed and rotated to resemble its appearance in the original mammogram.
ADAPTIVE NOISE EQUALIZATION AND RECOGNITION OF MICROCALCIFICATION CLUSTERS IN MAMMOGRAMS
Authors: KARSSEMEIJER NICO
Published: November 2004

A statistical method is described for detection of microcalcifications in digital mammograms. It is shown that the detection performance depends strongly on a preprocessing step, in which the images are rescaled to equalize image noise. A robust algorithm is proposed for rescaling, which can be used to determine a proper scale conversion from a phantom recording. The same algorithm, however, can also be applied to the image to be processed itself. Such an adaptive approach, in which noise characteristics are estimated from the image at hand, appeared to be the basis for far better results than could be obtained by using a fixed scale conversion. The method used for detection is based on Bayesian techniques. A random field model is used to model spatial relations between the labels in an iterative segmentation process. Results of an experimental study using a set of 65 mammographic images digitized at 2048×2048 are presented.
DETECTION AND CLASSIFICATION OF MAMMOGRAPHIC CALCIFICATIONS
Authors: SHEN LIANG , RANGAYYAN RANGARAJ M. , DESAUTELS J.E. LEO
Published: November 2004

We propose a detection and classification system for the analysis of mammo-graphic calcifications. First, a new multi-tolerance region growing method is proposed for the detection of potential calcification regions and extraction of their contours. The method employs a distance metric computed on feature sets including measures of shape, centre of gravity, and size obtained for various growth tolerance values in order to determine the most suitable parameters. Then, shape features from moments, Fourier descriptors, and compactness are computed based upon the contours of the regions. Finally, a two-layer perceptron is utilized for the purpose of classification of calcifications with the shape features. A new leave-one-out algorithm-based parameter determination procedure is included in the neural network training step. In our preliminary study, detection rates were 81% and 85±3%, and correct classification rates were 94% and 87% with a test set of 58 benign calcifications and 241±10 malignant calcifications, respectively. The proposed system should provide considerable help to radiologists in the diagnosis of breast cancer.
MAMMOGRAM SCREENING USING MULTIRESOLUTION-BASED IMAGE SEGMENTATION
Authors: BRZAKOVIC D. , NESKOVIC M.
Published: November 2004

This paper describes the design, implementation, and testing of an adaptive digital image segmentation method that detects cancerous changes in mammograms and can potentially aid medical experts in establishing the diagnosis. The essence of the method is hierarchical region growing that uses pyramidal multiresolution image representation. The relationships between pixels at different resolution levels are established using a fuzzy membership function, thus enabling detection of very small and/or low contrast objects in a highly textured background. The selection of the parameters of the fuzzy membership function allows for fine-tuning the method to specific segmentation objectives. This paper discusses two versions of the method: the first is aimed at the detection of microcalcifications and the second at the detection of benign and malignant nodules. The two versions are fully automated and differ in the procedure applied to automatically select the appropriate parameters of the fuzzy membership function. Both versions were evaluated in two ways: (i) using synthetically generated objects superimposed on normal mammograms and (ii) using mammogram images for which the corresponding truth images were generated by human experts. The objective of the first evaluation was to precisely determine the method’s capabilities and its sensitivity to object size, shape, and contrast. The objective of the second evaluation was to establish the method’s usefulness in helping medical experts to establish the diagnosis.
AN EXTENDED FORM OF SUB-BAND INTERPOLATION OF MULTI-DIMENSIONAL DISCRETE SIGNALS AND ITS APPLICATIONS
Authors: KIDA TAKURO
Published: November 2004

In this paper, we establish an extended form of the optimum sub-band interpolation for a family of n-dimensional discrete signals. We assume that the Fourier spectrums of these discrete signals have weighted L2 norms smaller than a given positive number.

It is assumed that the sample points of these discrete signals are identical with the whole vertices of an n-dimensional rectangular lattice in Rn. Among these sample points, certain subsets are used for the interpolation. Selecting appropriate subsets of the sample points, we can realize a wide variety of periodic arrangements of sample points for interpolation such as hexagonal and octagonal lattices or a set of sample points used in interlaces scanning of digital television.

The proposed method minimizes the measure of error which is equal to the envelope of the approximation errors with respect to the discrete signals.

In the following discussion, we assume initially that the corresponding approximation formula uses an infinite number of interpolation functions having limited supports and functional forms different from each other. However, it should be noted that the resultant optimum interpolation functions are expressed as the parallel shifts of the impulse responses of the finite number of n-dimensional FIR filters. Equivalent analog approximation formula corresponding to the proposed discrete approximation, is derived and interesting reciprocal relation in the approximation, is also discussed. A necessary and sufficient condition for the convergence of the corresponding analog approximation formula to the original band limited signal, is presented. An equivalent expression of the analog approximation formula in the frequency domain, is derived in relation to the convergence condition.
EIGENVALUE ANALYSIS OF COMPASS GRADIENT EDGE OPERATORS IN FOURIER DOMAIN
Authors: PARK RAE-HONG , CHOI WOO YOUNG
Published: November 2004

In this letter, we present a simple eigenvalue computation method of a transform matrix H introduced in a Fourier domain interpretation of the compass gradient edge operators.1 We derive the interrelation of three compass gradient edge operators in the spatial domain by explaining their eigenvalue structure in the transformed domain.
HIGH RESOLUTION MONOPULSE RADAR TRACKING SYSTEM
Authors: ALSAKA Y.A. , YOUNG L.A. , HAMID M.
Published: November 2004

High resolution radar techniques are applied to the problem of resolving a multiple target array and locating its geometric center without the usual biasing toward the brightest scatterer. This result is accomplished using monopulse radar techniques combined with high resolution stepped frequency pulse train signal processing in an angle tracking noncoherent high resolution radar. The center of each uniquely separated pair of point targets is calculated by examining the crosscorrelation function of the sum and difference channels. The autocorrelation of the sum channel is used to normalize the crosscorrelation data thereby eliminating the effects of the different targets’ radar cross sections (RCS). The zero separation term of the error function (dc term) remains biased toward the bigger scatterer, even after normalization. The nonzero terms (ac terms) are the cross range distances from the antenna’s boresight to each scatterer and are independent of their RCS. By simply dropping the zero separation term and averaging the remaining terms together, the aimpoint becomes the unbiased geometric center of the array.
FROM THE CHUA CIRCUIT TO THE GENERALIZED CHUA MAP
Authors: BROWN RAY
Published: November 2004

We analytically derive a one-dimensional map from an ODE which produces a double scroll very similar to the Chua double scroll. Our analysis leads us to suggest a generalization of the Chua circuit to an n-dimensional system of ODEs that we will call the generalized Chua equations. The third order system of ODEs in this class contains the Chua equations as a special case. Parallel to the generalized Chua equations we define the generalized Chua maps. An important feature of these equations and maps is that the source of their nonlinearity is a sigmoid function, and functions very similar in their properties to the sigmoid function. We show that this class of equations contains examples of maps that reproduce the Lorenz and Rössler dynamics. We suggest that a general theory of these equations and maps, and their relationship to one-dimensional maps, is possible.

A benefit of our analysis shows that the dynamics of the maps of Rössler, Chua, and Lorenz maps can be traced to a common set of building blocks, and we conclude that the Chua map is the simplest of the three maps and therefore understanding the complexity in the Chua map provides a foundation for understanding chaos in a large class of n-dimensional equations that includes the maps of Rössler and Lorenz.
MAINTAINING STABILITY IN CHUA'S CIRCUIT DRIVEN INTO REGIONS OF OSCILLATION AND CHAOS
Authors: JOHNSON G. A. , HUNT E. R.
Published: November 2004

Systems often have limited operating regions at increased drive parameters because of the onset of oscillations and chaos. Chua's circuit is an electronic example of such a system, as it has a nonzero steady-state (d.c.) voltage output before breaking into oscillations and eventually chaos as the drive is increased. Using a new control technique, we are able to keep the system in the steady state in regions for which it would otherwise exhibit oscillations or chaos.
CONTROLLING CHUA'S CIRCUIT
Authors: CHEN GUANRONG , DONG XIAONING
Published: November 2004

The unified canonical feedback control strategy developed recently by the present authors for controlling chaotic systems is refined and applied to the well-known Chua's circuit, driving its orbits from the chaotic attractor to its unstable limit cycle. Simple sufficient conditions for the controllability of this particular circuit are established. Simulation results are included to visualize the control process. A circuit implementation of the designed feedback control is realized by adding a linear resistor and an appropriate periodic-signal generator to the original circuit.
A CMOS MONOLITHIC CHUA'S CIRCUIT
Authors: DELGADO-RESTITUTO M. , RODRÍGUEZ-VÁZQUEZ A.
Published: November 2004

This paper presents the schematics and layout for a 2.4 µm CMOS prototype of the Chua's circuit. Our design uses VCCSs, realized using the quasilinear region of the transfer characteristics of a differential pair. The global, nonlinear characteristics of this building block are exploited to realize the Chua's diode. The prototype occupies 0.35 mm 2 and consumes 1.6 mW for a symmetrical biasing of ±2.5 v . The HSPICE electrical simulation results of the extracted layout show bifurcation towards a double-scroll Chua's attractor by changing a bias current. The manufacturability of the prototype has been confirmed by Monte Carlo analysis. Measurements from the chip also show bifurcation towards the double-scroll.
SELF-SIMILARITY AND UNIVERSALITY IN CHUA'S CIRCUIT VIA THE APPROXIMATE CHUA'S 1-D MAP
Authors: KUZNETSOV A. P. , KUZNETSOV S. P. , SATAEV I. R. , CHUA L. O.
Published: November 2004

In this paper we investigate the features of the transition to chaos in a one-dimensional Chua's map which describes approximately the Chua's circuit. These features arise from the nonunimodality of this map. We show that there exists a variety of types of critical points, which are characterized by a universal self-similar topography in a neighborhood of each critical point in the parameter plane. Such universalities are associated with various cycles of Feigenbaum's renormalization group equation.
AN AUTONOMOUS CHAOTIC CELLULAR NEURAL NETWORK AND CHUA'S CIRCUIT
Authors: ZOU FAN , NOSSEK JOSEF A.
Published: November 2004

Cellular neural networks (CNN) are time-continuous nonlinear dynamical systems. Like in Chua's circuit, the nonlinearity of these networks is defined as a piecewise-linear function. For CNNs with at least three cells chaotic behavior may be possible in certain regions of parameter values. In this paper we report such a chaotic attractor with an autonomous three-cell CNN. It can be shown that the attractor has a structure very similar to the double-scroll Chua's attractor. Through some equivalent transformations this circuit, in three major subspaces of its state space, is shown to belong to Chua's circuit family, although originating from a completely different field.
THEORY OF GENERALIZED INTERPOLATORY APPROXIMATION OF MULTI-DIMENSIONAL SIGNALS
Authors: KIDA TAKURO
Published: November 2004

In this paper, we present a systematic theory of the optimum subband interpolation of a family of n-dimensional signals which are not necessarily band-limited. We assume that the Fourier spectrums of these signals have weighted L2 norms smaller than a given positive number.

The proposed method minimizes the measure of error which is equal to the envelope of the approximation errors with respect to the signals. In the following discussion, we assume initially that the infinite number of interpolation functions with different functional forms are used in the corresponding approximation formula. However, the resultant optimum interpolation functions are expressed as the parallel shifts of the finite number of the n-dimensional functions.

It should be noted that the optimum interpolation functions presented in this paper satisfy the generalized discrete orthogonality and, as a result, minimize the wide variety of measures of error at the same time. In the literature,6 a similar discussion is presented. However, it is assumed that the signal is band-limited and the interpolation functions are compulsorily time-limited. Hence, these interpolation functions cannot minimize other measures of error except the proposed one.

Interesting reciprocal relation in the approximation, is also discussed. An equivalent expression of the approximation formula in the frequency domain is derived.
THE GEOMETRY AND COMPUTATION OF THE DYNAMICS OF COUPLED PENDULA
Authors: HENDERSON M. E. , LEVI M. , ODEH F.
Published: November 2004

In this paper, we analyze the dynamics of a system consisting of two torsionally coupled pendula with dissipation and with external forcing. In addition to several general results about the periodic solutions of the system, we prove that a family of homoclinic solutions exists in part of the parameter space, and give computational evidence that part of this family is the type considered by Shil'nikov. The existence of such orbits generates rich dynamics, which we describe qualitatively and illustrate with computed solutions.
RESONANCE PHENOMENA IN AN ADAPTIVELY-CONTROLLED SYSTEM
Authors: FROUZAKIS CHRISTOS E. , ADOMAITIS RAYMOND A. , KEVREKIDIS IOANNIS G.
Published: November 2004

This paper considers the problem of maintaining a linear, discrete-time system at a desired state using a model-reference, self-adapting, feedback control scheme. In particular, we focus on the dynamics introduced by the (nonlinear) controller and observe how the behavior of the system changes as the type and magnitude of plant/reference model mismatch vary. The desired fixed point of the system loses local stability via both period-doubling and Hopf bifurcations. Starting from these local instabilities, this paper presents a computer-assisted study of the dynamic behavior of the system, and, in particular, of the resonance structures associated with the Hopf bifurcation. Special emphasis is given to undesired dynamic features, such as multiple attractors and long transients which, because of the subcritical nature of this bifurcation, coexist with a locally stable fixed point.
GENERALIZING THE TWIST-AND-FLIP PARADIGM
Authors: BROWN RAY , CHUA LEON
Published: November 2004

In this paper we generalize the horseshoe twist theorem of Brown and Chua [1991] and derive a wide class of ODEs, with and without dissipation terms, for which the Poincare map can be expressed in closed form as FTFT where T is a generalized twist. We show how to approximate the Poincaré maps of nonlinear ODEs with continuous periodic forcing by Poincare maps which have a closed-form expression of the form FT 1 T 2 … T n where the T i are twists. We extend the twist-and-flip map to three dimensions with and without damping. Further, we demonstrate how to use the square-wave analysis to argue for the existence of a twist-and-flip paradigm for the Poincare map of the van der Pol equation with square-wave forcing. We apply this analysis to the cavitation bubble oscillator that appears in Parlitz et al. [1991] and prove a variation of the horseshoe twist theorem for the twist-and-shift map, which models the cavitation bubble oscillator. We present illustrations of the diversity of the dynamics that can be found in the generalized twist-and-flip map, and we use a pair of twist maps to provide a specific and very simple illustration of the Smale horseshoe. Finally, we use the twist-and-shift map of the cavitation bubble oscillators to demonstrate that the addition of sufficient linear damping to a dynamical system having PBS (Poincaré–Birkhoff–Smale) chaos may cause the chaos to become detectable in computer simulations.
STEADY STATES, LIMIT CYCLES, AND CHAOS IN MODELS OF COMPLEX BIOLOGICAL NETWORKS
Authors: LEWIS JOHN E. , GLASS LEON
Published: November 2004

Theoretical models of neural and genetic control networks consisting of N interacting elements are cast in the form of an N-dimensional system of piecewise linear (PL) ordinary differential equations. The state transition diagram of this system, which represents transitions between distinct volumes in the N-dimensional phase space, is given as a directed graph on an N-dimensional hypercube in which each edge has only one orientation. Analytical results establish steady-states and limit cycles in these systems, and numerical results have identified chaotic dynamics for N ≥ 6.
AN OBJECT-ORIENTED SOFTWARE REQUIREMENTS ANALYSIS METHOD
Authors: POO DANNY C. C.
Published: November 2004

This paper discusses an object-oriented software requirements analysis method. The approach adopted here draws clear distinction between a system's basic structure (i.e. the object model) and its functionalities. The analysis model generated is a description of a problem domain; it consists of a set of primary and secondary objects that characterize the problem domain, and a set of pseudo objects that define the functional requirements of a system.

There are two stages of analysis in the proposed method: Object Modelling and Functional Requirements Modelling. These two stages are built upon one another. The aim of the object modelling stage is to derive a model of the problem domain in terms of objects, their classification and inter-relationships with one another. The functional requirements modelling stage builds upon this initial object model to complete the requirement analysis specification.

This paper uses a real-life library environment to illustrate how the method can be applied in the specification of an object-oriented software system.
RIGOROUS ENGINEERING PRACTICE AND FORMAL REASONING OF DEEP DOMAIN KNOWLEDGE—THE BASIS OF DEPENDABLE KNOWLEDGE BASED SYSTEMS FOR PROCESS PLANT CONTROL
Authors: BOLOGNA SANDRO , SIVERTSEN TERJE , VÄLISUO HEIKKI
Published: November 2004

Knowledge based systems are often used to replace humans in solving problems for which only heuristic knowledge on the solution is available. However, there are also important application areas where nonheuristic knowledge is available e.g. in technical documents but where efficient use of the knowledge is impossible without the techniques provided by artificial intelligence. High dependability of these kinds of applications can be achieved if domain knowledge can be represented in a language providing both adequate representational constructs and the required level of formality. In addition, the language should be supported by powerful tools assisting in the verification process.

Knowledge Based Systems, despite the different technology employed, are still nothing more than a computer program. Unfortunately, quite a few people building knowledge based systems seem to ignore the many good programming practices that have evolved over the years for producing traditional computer programs. What we need is a framework for the modelling of the KBSs development.

In our work, it is claimed that these requirements can be met by utilizing and combining ideas from control engineering, software engineering and artificial intelligence.
OBJECT-ORIENTED ANALYSIS: CRITERIA AND CASE STUDY
Authors: DRAKE J. , TSAI W.T. , LEE H.J. , ZUALKERNAN I.
Published: November 2004

Three object-oriented analysis techniques: Shlaer & Mellor, Coad & Yourdon, and Document-Driven Analysis were evaluated. Criteria for comparison of analysis techniques were developed. These criteria state that an analysis technique should (1) cover data, transformation, and control perspectives of the problem, (2) address large problems through partitioning, bounding the problem, and supporting prototypes and incremental analysis, (3) provide approaches for verification and validation, and (4) support configuration control. A case study in a software engineering class was conducted using the three OOA techniques. Through the case study we found that (1) identifying objects is affected by notation and flexibility of object models, (2) visualizing global data, transformations, and control are necessary to capture end-user’s processes, (3) emphasizing hierarchical structures and third normal form divert the analyst’s attention from analysis to implementation, (4) an explicit representation of relationships is necessary, (5) peer review is useful in improving selection of objects and methods to support end-user processes, and (6) supporting a standard document from OOA products is not easy.
THE “KVAZAR” PACKAGE FOR PATTERN RECOGNITION AND ITS APPLICATIONS
Authors: KAZANTSEV VLADIMIR S.
Published: November 2004

The package of applied programs named KVAZAR has been elaborated to be used for classification, diagnostic, predicative, experimental data analysis problems. The package may be used in medicine, biology, geology, economics, engineering and some other problems. The algorithmical base of the package is the method of pattern recognition, based on the linear inequalities and committee constructions. Other algorithms are used too. The package KVAZAR is intended to be used with IBM PC AT/XT. The range of processing data is bounded by 40,000 numbers.
MODELING UNDER LOCAL STRUCTURE HYPOTHESES
Authors: PLOTNIKOV SERGE V.
Published: November 2004

A mathematical model of a typical problem of pattern recognition is described. Its characteristic property is that it pays special attention to a priori information concerning the local structure of the object under investigation. Algorithmic backgrounds (using convex analytic tools) of the suggested approach are presented.
DETERMINATION OF SOLVABILITY BOUNDARIES OF OPTIMIZATION PROBLEMS IN PARAMETER SPACE
Authors: CHERENKOV A.P. , MIKHAILENKO V.V. , SHUSTERMAN B.S.
Published: November 2004

This paper is devoted to the determination of parameter values of optimization problems for which they are solvable. In relation to this, the concept of monotone solvability with respect to parameter is essentially used. The procedure of construction of solvability boundaries in parameter space is realized, and it is essentially reduced to decipher the monotone function. This procedure is used for the consideration of a dynamic model of simulative control of the geological-prospecting process (the resource allocation between stages of geological-prospecting work). On the basis of this procedure using the standard package of linear programming, the complex program of decision-making for personal computers compatible with IBM XT/AT is implemented.
THE UNIVERSAL SOLUTIONS OF INTERVAL SYSTEMS OF LINEAR ALGEBRAICAL EQUATIONS
Authors: ASCHEPKOV L.T. , DOLGY D.V.
Published: November 2004

The new concepts of ε-solutions and universal solutions for systems of linear equations with interval coefficients are introduced. To find these solutions some constructive methods using linear programming technics are proposed.
IMPROVED SELECTION IN TOTALLY MONOTONE ARRAYS
Authors: MANSOUR YISHAY , PARK JAMES K. , SCHIEBER BARUCH , SEN SANDEEP
Published: November 2004

This paper's main result is an [Formula: see text]-time algorithm for computing the kth smallest entry in each row of an m×n totally monotone array. (A two-dimensional array A={a[i, j]} is totally monotone if for all i1<i2 and j1<j2, a[i1, j1]<a[i1, j2] implies a[i2, j1]<a[i2, j2].) For large values of k (in particular, for k=⌈n/2⌉), this algorithm is significantly faster than the O(k(m + n))-time algorithm for the same problem due to Kravets and Park. An immediate consequence of this result is an O(n3/2 lg 1/2 n)-time algorithm for computing the kth nearest neighbor of each vertex of a convex n-gon. In addition to the main result, we also give an O(n lg m)-time algorithm for computing an approximate median in each row of an m×n totally monotone array; this approximate median is an entry whose rank in its row lies between ⌊n/4⌋ and ⌈3n/4⌉ − 1.
A SIMPLIFIED TECHNIQUE FOR HIDDEN-LINE ELIMINATION IN TERRAINS
Authors: PREPARATA FRANCO P. , VITTER JEFFREY SCOTT
Published: November 2004

In this paper we give a practical and efficient output-sensitive algorithm for constructing the display of a polyhedral terrain. It runs in O((d+n) log 2 n) time and uses O(nα(n)) space, where d is the size of the final display, and α(n) is a (very slowly growing) functional inverse of Ackermann’s function. Our implementation is especially simple and practical, because we try to take full advantage of the specific geometrical properties of the terrain. The asymptotic speed of our algorithm has been improved upon theoretically by other authors, but at the cost of higher space usage and/or high overhead and complicated code. Our main data structure maintains an implicit representation of the convex hull of a set of points that can be dynamically updated in O( log 2 n) time. It is especially simple and fast in our application since there are no rebalancing operations required in the tree.
AN ON-LINE ALGORITHM FOR NAVIGATING IN AN UNKNOWN ENVIRONMENT
Authors: CHAN KWONG-FAI , LAM TAK WAH
Published: November 2004

Suppose that a robot is required to traverse a two-dimensional scene with impenetrable rectangular obstacles. The robot has no information about the obstacles in advance and the size, location, and orientation of each obstacle in the scene are arbitrary, yet the robot can see and move in any direction. In this paper we construct an on-line algorithm for the robot to determine an obstacle-free path to its destination dynamically. The primary concern for such on-line algorithm is the competitiveness coefficient which essentially compares the actual distance traversed to the length of the shortest path. We show that if the aspect ratio of every rectangular obstacle in the scene is bounded by a constant r, then our algorithm achieves the optimal competitiveness coefficient which is r/2+1.
AN OPTIMAL CONSTRUCTION METHOD FOR GENERALIZED CONVEX LAYERS
Authors: LENHOF HANS-PETER , SMID MICHIEL
Published: November 2004

Let P be a set of n points in the Euclidean plane and let C be a convex figure. In 1985, Chazelle and Edelsbrunner presented an algorithm, which preprocesses P such that for any query point q, the points of P in the translate C+q can be retrieved efficiently. Assuming that constant time suffices for deciding the inclusion of a point in C, they provided a space and query time optimal solution. Their algorithm uses O(n) space. A query with output size k can be solved in O( log n+k) time. The preprocessing step of their algorithm, however, has time complexity O(n2). We show that the usage of a new construction method for layers reduces the preprocessing time to O(n log n). We thus provide the first space, query time and preprocessing time optimal solution for this class of point retrieval problems. Besides, we present two new dynamic data structures for these problems. The first dynamic data structure allows on-line insertions and deletions of points in O(( log n)2) time. In this dynamic data structure, a query with output size k can be solved in O( log n+k( log n)2) time. The second dynamic data structure, which allows only semi-online updates, has O(( log n)2) amortized update time and O( log n+k) query time.
DYNAMIC PROGRAMMING ON INTERVALS
Authors: ASANO TAKAO
Published: November 2004

We consider problems on intervals which can be solved by dynamic programming. Specifically, we give an efficient implementation of dynamic programming on intervals. As an application, an optimal sequential partition of a graph G=(V, E) can be obtained in O(m log n) time, where n=|V| and m=|E|. We also present an O(n log n) time algorithm for finding a minimum weight dominating set of an interval graph G=(V, E), and an O(m log n) time algorithm for finding a maximum weight clique of a circular-arc graph G=(V, E), provided their intersection models of n intervals (arcs) are given.
COMPUTATIONAL GEOMETRY COLUMN 20
Authors: O’ROURKE JOSEPH
Published: November 2004

Open problems from the Ninth ACM Symposium on Computational Geometry (May 1993) are listed tersely.
ON THE WORD PROBLEM IN PERIODIC GROUP VARIETIES
Authors: SAPIR M. V.
Published: November 2004

It is shown that there is a finitely based periodic group variety with unsolvable word problem. This uses the solution by Novikov and Adian of the Burnside problem and solves a subsequent problem raised by Adian and Makanin.
A DESCRIPTION OF SOLUTIONS OF QUADRATIC EQUATIONS IN HYPERBOLIC GROUPS
Authors: GRIGORCHUK R.I. , LYSIONOK I.G.
Published: November 2004

A description is given for the set of solutions of a quadratic equation in a hyperbolic group. It consists of a finite set of parametric solutions of the equation which generates all solutions by the action of a group which may be interpreted as a special mapping class group of a compact surface.
DEFORMATIONS OF S(0, n) AND H(0, n)
Authors: HIJLIGENBERG N.V.D. , KOTCHETKOV Y. , POST G.
Published: November 2004

We prove that S(0, n) and H(0, n) possess deformations for all n. Furthermore, we show that there are 2 infinite sequences of simple finite-dimensional Lie superalgebras, that are not rigid.
IDENTITIES OF FINITE INVERSE SEMIGROUPS
Authors: SAPIR MARK V.
Published: November 2004

Inverse semigroups are considered as algebras with two operations: multiplication and inversion. We prove that there are no inherently non-finitely based finite inverse semigroups. In constrast, if we consider inverse semigroups as semigroups (one binary operation) then it was proved by the author that almost all finite inverse semigroups are inherently non-finitely based.
ON ABELIAN POWER-FREE MORPHISMS
Authors: CARPI ARTURO
Published: November 2004

In this paper, an effective sufficient condition for a morphism to preserve abelian nth power-free words is given. This condition is shown to be an effective characterization of morphisms preserving abelian nth power-free words, defined on alphabets with 6 or more letters.
CONJUGACY IN FREE INVERSE MONOIDS
Authors: CHOFFRUT CHRISTIAN
Published: November 2004

We give the equation xz=zy in free inverse monoids the best possible solution by showing, with a technical restriction, that whenever x and y satisfy such an equation for some z, then there exists a finite chain of words, starting in x and ending in y, for which two consecutive words are of the form uv and vu. We also prove, given x and y, that testing whether or not there exists an element z such that the equation xz=zy holds, is linear in the lengths of some representatives of x and y. This naturally extends the corresponding result in free monoids.

Résumé: nous donnons de l'équation xz=zy la meilleure solution possible en montrant que si deux mots x et y satisfont une telle équation pour un certain z, alors sous une hypothèse faible, il existe une chaine finie et non bornée de mots débutant en x et terminant en y, telle que deux mots consécutifs soient de la forme uv et vu. Nous prouvons aussi que décider si deux éléments x et y satisfont xz=zy pour un certain z, est linéaire en la longueur de représentants de x et y. Ceci étend de façon naturelle le résultat correspondant pour les monoides libres.
CAYLEY GRAPHS OF VIRTUALLY FREE GROUPS
Authors: D’AGOSTINO GIOVANNA
Published: November 2004

A geometrical characterization of the Cayley graphs of certain presentations of virtually free and plain groups is given.
COMPUTING HALL EXPONENTS IN THE FREE GROUP
Authors: MELANÇON GUY , REUTENAUER CHRISTOPHE
Published: November 2004

Nous donnons une généralisation de la décomposition de M. Hall des éléments du groupe libre en produits décroissant de commutateurs de Hall. Nous généralisons les identités de Thérien, qui expriment les exposants de la décomposition comme des sommes à coefficients entiers positifs de fonctions sous-mots. Nous étudions l’algèbre des fonctions sous-mots et nous montrons que cette algèbre est librement engendrée par les fonctions qui donnent ces exposants; nous montrons aussi la continuité de ces fonctions pour la topologie de Hall sur le groupe libre. De plus, nous donnons de nouvelles preuves de résultats connus, entre autres les théorèmes de Magnus et Witt qui caractérisent les éléments de la série centrale descendante du grouple libre.

We give the generalization of M. Hall’s expansion of each element of the free group as a decreasing product of Hall commutators. We also prove the generalization of Therien’s identities expressing the Hall exponents as nonnegative linear combinations of subword functions. We study the algebra of subword functions and show that it is freely generated by the Hall exponents functions; we also prove the continuity of these functions for the Hall topology on the free group. Besides these results, we give new proofs of known results, especially of the theorem of Magnus and Witt on the lower central series of the free group.
ESSENTIALITY OF FRACTAL IDEALS
Authors: ROSENMANN AMNON
Published: November 2004

The question of essentiality of decreasing and increasing fractal ideals is investigated, mostly for fractal ideals built from the agumentation ideal of free group rings. It is shown that this question can be answered in terms of the structure of the trees representing the fractal ideals.
THE ORBIT STRUCTURE OF FINITE MONOIDS
Authors: CARSCADDEN ROB
Published: November 2004

Let M be a finite monoid with unit group G. We consider a refinement, [Formula: see text] of the Green’s relation [Formula: see text]. The [Formula: see text]-classes, denoted [Formula: see text] are the G×G orbits, GHG, of the ℋ-classes, H, of M. With an orbit [Formula: see text] we associate a local monoid [Formula: see text] and determine the structure of these local monoids. The theory is applied to the full transformation semigroup [Formula: see text] and we see that the number of orbits [Formula: see text] in [Formula: see text] is equal to the number of partitions of n.
OPTICAL STARK EFFECTS ON THE STACKING FAULT EXCITONS IN BiI3
Authors: AKAI I. , KARASAWA T. , KOMATSU T.
Published: November 2004

A study is made of the optical Stark effects on quasi two-dimensional excitons localized at a stacking fault in layered crystal BiI 3. The dynamic coupling of the driven ground states and driven multiple exciton states by the strong photon field occurs for a wide frequency range of light, from negative to positive detuning. For the positive detuning excitation, an additional nonlinear effect peculiar to condensed matter was also observed. Time-resolved measurements in the sub-nanosecond and picosecond time domains confirmed ultrafast switching between the optical Stark effect and the additional nonlinear effect. From the dependence of the optical Stark shift on the excitation intensity, it is shown that the quasi two-dimensional excition transition has a very large dipole matrix element and third-order nonlinear susceptibility χ(3).
STUDY OF TIME-DELAY FOUR-WAVE MIXING WITH INCOHERENT LIGHT IN ABSORPTION BANDS II: EXPERIMENT
Authors: ZHANG RUIHUA , MI XIN , ZHOU HAITIAN , JIANG QIAN , YE PEIXIAN
Published: November 2004

A series of experiments of time-delay four-wave mixing with incoherent light (TDFWM-IL) in absorption bands of ruby and dye molecules at 300 K-20 K are reported, which demonstrate that two-level theory fails in the interpretation of the results, and that our multilevel theory of TDFWM-IL should be applied. The following experimental results are emphasized: the normalized delay-time dependences of the signal intensity IS (τ) are not dependent on the sample temperature from 80 K to 300 K for the pump-beam wavelengths not closed to the zero-phonon line or the absorption edge as the power spectrum S0(ω) of the incoherent light source kept invariable; at low temperature of 20 K, IS(τ) is modulated periodically with a period equal to the interval of two adjacent vibrational transitions in the absorption band 4T2 of ruby, as predicted by the multilevel theory. The experiments performed at the zero-phonon line of ruby and at the absorption edge of Cresyl Violet in PMMA demonstrate that the effective two-level model is suitable to approximately analyze not only the experimental results of TDFWM-IL in the unresolved continuous absorption bands with homogeneous broadening, but also the effects of inhomogeneous broadening on the behavior of TDFWM-IL in these bands. Additionally, some data of the subpicosecond dephasing processes of these materials are also obtained for the first time.
THIRD HARMONIC GENERATION BY A PUMP FOCUSED ON THE BOUNDARY OF TOTAL INTERNAL REFLECTION
Authors: SAVCHENKO A. YU. , ZEL’DOVICH B. YA.
Published: November 2004

Phase velocity mismatching leads to zero output intensity of E(3ω) for the case when the focal waist of the pump E(ω) is totally embedded inside the medium. Focusing of the pump on the boundary of total internal reflection is considered, and 4-fold raise of 3ω-intensity is predicted for certain incidence angle θ in comparison with the case θ=0.
OPTICAL SWITCHING AND CONTROLLED SELF DIFFRACTION WITH POLYMER DISPERSED LIQUID CRYSTALS
Authors: SIMONI F. , BLOISI F. , VICARI L.
Published: November 2004

Self-transparency due to thermal nonlinearities is presented as basic switching effect in polymer dispersed liquid crystals. The main consequences of this phenomenon on wave mixing are opto-optical switch and self-diffraction with threshold, How this threshold behavior can be exploited to drive self-diffraction by an external voltage applied to the sample, coupling in an original way thermal nonlinearities of the liquid crystal with its orientational properties is explained here. The possibility of obtaining a transient amplitude grating in these materials is also discussed.
TYPE-II SUPERLATTICES AND VARIABLE OVERLAP SUPERLATTICES IN TOTAL INTERNAL REFLECTION SWITCHES FOR THE LONGWAVE INFRARED
Authors: YOUNGDALE E.R. , MEYER J.R. , HOFFMAN C.A. , BARTOLI F.J. , WANG W.I.
Published: November 2004

We derive explicit criteria for the properties required of a semiconductor nonlinear medium suitable for use in all-optical switching devices employing total internal reflection. Transmission as a function of laser intensity and film thickness has been calculated using a realistic model for penetration of the evanescent beam under TIR conditions. Requirements based on these results include a large nonlinear refractive index, large index change at saturation and small absorption coefficient. We show that unlike previously-studied semimetals and narrow-gap semiconductors, Type-II superlattices such as InAs-GaSb and variable-overlap superlattices (variants of Type-II which include a spacer between the layer containing the conduction-band minimum and that containing the valence band maximum) such as InAs-AlSb-GaSb hold prospects for satisfying all of these requirements simultaneously. As the free carrier lifetime will have a crucial influence on device performance, we have initiated a systematic experimental study of electron-hole recombination in InAs-based superlattices. From degenerate and nondegenerate four-wave mixing experiments, we have also determined nonlinear optical coefficients as a function of difference frequency and intensity. An InAs-GaSb superlattice has been found to display a refractive index change of ≈ 0.1, as well as device figures of merit which slightly surpasses any previously reported for weakly-saturating nonlinearities at CO 2 wavelengths. It is anticipated that future experiments on Type-II superlattices with longer lifetimes may yield nearly two orders of magnitude additional improvement in the nonlinear refractive index.
CHARACTERISTICS OF A LOW F-NUMBER BROADBAND VISIBLE THERMAL OPTICAL LIMITER
Authors: SWARTZLANDER G.A. , JUSTUS B.L. , HUSTON A.L. , CAMPILLO A.J. , LAW C.T.
Published: November 2004

The operation of a wide field-of-view optical limiter is described for self-defocusing type nonlinear refractive materials, and design strategies were developed with the aid of numerical modeling. Experiments with a cell thickness on the order of the Rayleigh length (25–100 µm) were conducted with 6 and 30 nsec pulse lengths (single shot) at a wavelength of 532 nm. Broadband optical limiting with the transmitted fluence below the eye MPE (maximum permissible exposure) level was achieved using nigrosin dye dissolved in CS 2, owing to the large thermal nonlinearity of the solvent, and the large changes in the refractive index allowed by a liquid. The device performance was accurately predicted by the numerical model up to the point of dielectric breakdown. Using 6 nsec pulses, we measured a limiting threshold energy of 40 nJ, which corresponds to a fluence of only 100 mJ/cm 2 in the solution, in an f/5 optical system with neutral gray transmission of ~ 50%.
AN EXPERT SYSTEM FOR FIRE–CODE CHECKING: DESIGN, IMPLEMENTATION AND GEOMETRIC ALGORITHMS
Authors: DELIS ETHYMIOS A. , DELIS ALEXIOS
Published: November 2004

Engineering design is an iterative and time-consuming process that requires expertise from diverse fields. An important part of the design process is devoted to checking the compliance of a design with one or more codes that might result from legislation. The code-checking process requires deep knowledge of the codes, awareness of their continuous changes, good understanding of the design process and, most importantly, skillful personnel. Automatic intelligent fire–code checking is examined in this paper. A general approach is considered wherein engineering code requirements are encoded in a knowledge-based expert system which evaluates a design for overall conformance. The system termed as Fire–Code Analyzer (FCA) consists of a frame system, a rule system, and a set of geometric algorithms. The frame-based system is used to represent the various three–dimensional objects of an application model and their relations. Each frame includes a number of slots that take values regarding property information. The knowledge base of the rule-based system includes a set of rules in the IF/THEN form, and its purpose is to provide all the necessary information in order to achieve compliance with a particular code. A number of geometric algorithms are discussed. These algorithms elicit knowledge from the frame representation of the various building objects. Finally, the system identifies code violations and generates a report listing them.