bluuebunny/crossref_metadata_2025 huggingface dataset:
ADAPTIVE, FREQUENCY DOMAIN, 2-D MODELING USING SPATIOTEMPORAL SIGNALS
Authors: MIKHAEL WASFY B. , YU HAOPING
Published: October 2004

In this paper, an adaptive, frequency domain, steepest descent algorithm for two-dimensional (2-D) system modeling is presented. Based on the equation error model, the algorithm, which characterizes the 2-D spatially linear and invariant unknown system by a 2-D auto-regressive, moving-average (ARMA) process, is derived and implemented in the 3-D spatiotemporal domain. At each iteration, corresponding to a given pair of input and output 2-D signals, the algorithm is formulated to minimize the error-function’s energy in the frequency domain by adjusting the 2-D ARMA model parameters. A signal dependent, optimal convergence factor, referred to as the homogeneous convergence factor, is developed. It is the same for all the coefficients but is updated once per iteration. The resulting algorithm is called the Two-Dimensional, Frequency Domain, with Homogeneous µ*, Adaptive Algorithm (2D-FD-HAA). In addition, the algorithm is implemented using the 2-D Fast Fourier Transform (FFT) to enhance the computational efficiency. Computer simulations demonstrate the algorithm’s excellent adaptation accuracy and convergence speed. For illustration, the proposed algorithm is successfully applied to modeling a time varying 2-D system.
GASBOR: A GENETIC ALGORITHM APPROACH FOR SOLVING THE SWITCHBOX ROUTING PROBLEM
Authors: LIENIG JENS , THULASIRAMAN K.
Published: October 2004

A new genetic algorithm for switchbox routing in the physical design process of integrated circuits is presented. Our algorithm, called GASBOR (Genetic Algorithm for SwitchBOx Routing), is based on a three-dimensional representation of the switchbox and problem-specific genetic operators. The performance of the algorithm is tested on different benchmarks and it is shown that the results obtained using the proposed algorithm are either qualitatively similar to or better than the best published results.
ANALYSIS OF MULTICOMPONENT CHIRP SIGNALS USING FREQUENCY-SHEAR REPRESENTATION
Authors: YAO SUSU , HE ZHENYA
Published: October 2004

This paper is concerned with the problem of multicomponent chirp signal analysis. The traditional analysis tool is time-frequency distribution which has been paid more attention in deterministic nonstationary signal processing. However, for chirp signals, it is difficult to find a best time-frequency representation that has high auto component concentration and cross-term suppression. Generally, any time-frequency representation based on rectangular resolution cell will not result in good performance for signals with time-varying frequency content. In this paper we propose a new representation for analyzing multicomponent chirp signals using resolution cell that shears in the timefrequency plane. In our approach, the kernel function with its shape adapted to the local structure of the chirp signal is used so that the signal components can be clearly mapped onto the frequency-shear plane. It is shown that the frequency-shear representation can reduce spurious values and concentrate on the auto components. Several signals including sinusoidal signals and chirp signals are analyzed and simulated using the proposed approach in comparison with the results by the Wigner distribution.
AN INTERCONNECT ALLOCATION ALGORITHM FOR PERFORMANCE-DRIVEN DATAPATH SYNTHESIS
Authors: KIM YOUNG-NO , LEE HAE DONG , HWANG SUN YOUNG
Published: October 2004

This paper presents the design of a performance-driven interconnect allocation algorithm. The proposed algorithm is based on the idea that the data transfer time can be reduced by balancing the load for specific hardware modules on possible critical path, such that the clock period can be minimized. By performing load balancing for only the communication lines on critical paths, the proposed algorithm generates interconnection structures with minimum delays. Experimental results confirm the effectiveness of the algorithm by constructing the interconnection structures with minimized clock periods for several benchmark circuits available from the literature.
A CONVERSE OF DUAL TELLEGEN’S THEOREM
Authors: CEL J.
Published: October 2004

Let [Formula: see text] and [Formula: see text] be directed networks having the same number of branches labeled correspondingly. It is proved that if [Formula: see text] for all vectors of corresponding branch voltages [Formula: see text] and currents [Formula: see text] satisfying Kirchhoff’s voltage and current laws in every loop and cutset of [Formula: see text] and [Formula: see text] then the imposed correspondence of branches is the dual isomorphism of networks, so that in particular [Formula: see text] and [Formula: see text] are both planar. This establishes the converse to the dual of Tellegen’s famous theorem.
A METHOD FOR CALCULATING THE RADIUS OF CONVERGENCE OF AN EQUILIBRIUM POINT OF A CONTINUOUS FEEDBACK NEURAL NETWORK
Authors: SHI YU-HUI , HE ZHEN-YA , SWAMY M.N.S. , AHMAD M.O.
Published: October 2004

For a continuous feedback neural network to be used as associative memory, it is important for us to know the radii of convergence of its equilibrium points. In this letter, a method for calculating the radius of convergence of an equilibrium point of a continuous feedback neural network is derived.
PERFORMANCE ANALYSIS OF FREQUENCY-HOPPED SPREAD-SPECTRUM PACKET RADIO NETWORKS PART I: SLOTTED MULTIPLE-ACCESS
Authors: MOHAMED KHAIRI ASHOUR , PAP LÁSZLÓ
Published: October 2004

This paper is concerned with the performance analysis of slotted frequency-hopped packet radio networks with Reed-Solomon forward error control coding. Both random and one coincidence frequency hopping patterns are considered. A new concept of the pair-wise hit patterns and the effective multiple-access interference are introduced. The joint probability generating functions of these interference vectors are determined for both synchronous and asynchronous hopping. Closed form expressions for packet capture probabilities and throughput are derived in terms of these joint generating functions. Finally a direct proof is given that hits in different symbols are asymptotically independent.
PERFORMANCE ANALYSIS OF FREQUENCY-HOPPED SPREAD-SPECTRUM PACKET RADIO NETWORKS PART II: UNSLOTTED MULTIPLE-ACCESS
Authors: MOHAMED KHAIRI ASHOUR , PAP LÁSZLÓ
Published: October 2004

This paper is concerned with the performance analysis of unslotted frequency-hopped spread spectrum packet radio networks with Reed-Solomon forward error control coding. The following different network alternatives are analyzed in a unified manner

(i) random/one-coincidence frequency hopping patterns,

(ii) one/several code symbols per dwell interval,

(iii) independent/dependent packet arrival processes,

(iv) fixed/variable length packets.

Joint probability generating functions for the pair-wise hit patterns and the effective multiple-access interference vector are determined for the different alternatives. Closed form formulae and expressions for packet capture probabilities are readily obtained from these generating functions. A direct proof is given that in the case of single symbol/dwell packets symbol errors, are asymptotically independent. Numerical results indicate that the unslotted networks outperform the corresponding slotted ones at low to moderate traffic levels, and the difference between the two networks is diminishing when the number of frequency bins is large.
COMPARING DUAL CURRENT-CONVEYOR CONFIGURATIONS
Authors: HAYATLEH K. , LIDGEY F.J. , PORTA S.
Published: October 2004

Composite current-conveyors formed by connecting monolithic dual devices to operate as a single CCII are examined in detail. Comparisons between the two common configurations show that the net performance favors one or the other depending upon the particular application requirements.
DESIGN AND FPGA IMPLEMENTATION OF DIGIT-SERIAL MODIFIED BOOTH MULTIPLIERS
Authors: SATYANARAYANA JANARDHAN H. , NOWROUZIAN BEHROUZ
Published: October 2004

This paper presents a comprehensive approach to the ASIC design of general digit-size digit-serial modified Booth multipliers, together with corresponding hardware implementations employing the Actel 1.2 µ FPGA technology. The proposed design is based on a decomposition of the N-bit multiplier and the M-bit multiplicand each into a unique set of D radix-2D components. The decomposed multiplicand components are then combined with the modified Booth encoded multiplier components to form the desired product. Analytical expressions are derived for the total number of gate-equivalents in the corresponding FPGA implementations in terms of D and N. Similarly, by using a critical path analysis, analytical expressions are derived for the maximum possible bit-clock rate in terms of D. These results are then combined to arrive at the efficiency of the implementation quantified by the throughput per unit area as a function of the digit-size D (with the wordlength L being taken as a parameter). It is shown that for wordlengths in the range 16≤L≤22, the digit-size falls somewhere in the range 3≤D≤8 for optimal throughput per unit area, where L=min{M, N}. Viewlogic simulation results are presented to verify the proposed digit-serial modified Booth multipliers.
FUZZY BI- AND MULTI-PARTITIONING FOR CIRCUITS REPRESENTED BY HYPERGRAPHS
Authors: BALL CARSTEN F. , MLYNSKI DIETER A.
Published: October 2004

A new strategy for partitioning hypergraphs in complex LSI and VLSI circuits is presented. A new fuzzy net-cut model has been developed to treat multi-pin-nets without splitting into two-pin-nets. The combinatorial optimization algorithm is derived from statistical physics. The circuit graph is modeled as a highly coupled spin system and the mean field approximation is used to achieve linear time complexity. Fuzzy partitioning enables a qualitative and macroscopic approach by interpreting the mean values of the spin system as fuzzy membership degrees. The proposed strategy is tested with MCNC benchmark problems and compared to results achieved recently. The performance of the new algorithm is comparable with neural networks and simulated annealing, but much faster, because of its linear time complexity. Furthermore, the partitioning algorithm has been implemented in an industrial CAD design tool and results are given.
FAULT TOLERANT RING EMBEDDING IN TETRAVALENT CAYLEY NETWORK GRAPHS
Authors: VADAPALLI PREMKUMAR , SRIMANI PRADIP K
Published: October 2004

Our purpose in the present paper is to investigate the structural properties of the newly proposed Cayley networks of constant node degree 4. We show that the graph contains rings of maximal length in the presence of multiple faults. Our results provide further evidence to the usefulness and robustness of these network graphs.
ULTRAHIGH DENSITY VLSI INNER PRODUCT COMPUTATIONS
Authors: CARD HOWARD
Published: October 2004

This paper discusses some of the limitations to matrix computations performed by special-purpose VLSI systems on a chip as the minimum feature size of CMOS technology is reduced to below 1.0 µ m . Limits to computation rates are imposed by power dissipation and by having a maximum number of pins or input/output ports on the package. The analysis applies to regular networks of array multipliers performing binary integer arithmetic at various bit precisions.
RADIX MODULAR MULTIPLICATION ALGORITHM
Authors: MEKHALLALATI M.C. , ASHUR A.S. , IBRAHIM M.K.
Published: October 2004

In this paper, the concept of a new Radix Modular Multiplication Algorithm (MMA) is proposed. The novelty of the new Radix-2n MMA is that the intermediate partial sums (IPSs) are not restricted to be less than the modulus M, but only to be represented by N bits, where N is the number of bits needed to represent the modulus M. Hence, the IPSs become redundant to the modulus M.

Two new Radix-2n MMAs (for n=2 and 4) based on the proposed concept are considered in detail as well. It is shown that a parallel multiplier based on the new Radix-4 MMA achieves twice the speed of a parallel multiplier based on a recent Radix-2 MMA. This result becomes more significant when it is noted that doubling the speed was achieved without any increase in the hardware requirement. In addition, it is shown that the parallel multiplier based on the new Radix-16 MMA achieves four times the speed of that of the Radix-2 MMA with the same hardware requirement.

When compared to the existing Radix-4 MMAs that are based on Carry Save format and Binary Signed Digit (BSD) representation, it is shown that the delay per step of the proposed Radix-4 multiplier is decreased by more than 40% when the intermediate steps are implemented using Carry Save Adders (CSAs).
HANDWRITTEN NUMERAL AND MACHINE PRINTED MULTIPLE FONT CHARACTER RECOGNITION USING NEURAL NETWORK CLASSIFIER
Authors: CAO J. , AHMADI M. , SHRIDHAR M.
Published: October 2004

In this paper a new neural network is proposed for recognition of handwritten digits and multi-font machine printed characters. In this system, overlapped regional chain code histograms of characters are used as features and a neural network has been used for classification.

A new neural network learning algorithm that combines unsupervised learning with supervised learning has been developed. This new algorithm overcomes the slow learning and difficult convergence problems that are typical of back-propagation learning algorithms. The algorithm was tested on a large set of handwritten digits collected from real world data and a set of multi-font machine printed English letters.
A SIMPLE LARGE-SIGNAL NONLINEAR MODEL FOR ZERO-CURRENT-SWITCH QUASI-RESONANT BUCK CONVERTERS
Authors: LEUNG FRANK HUNG-FAT , WONG LIK-KIN , TAM PETER KWONG-SHUN
Published: October 2004

A large-signal nonlinear model for zero-current-switch quasi-resonant buck converters is presented. The derivation is simple and the results are accurate even for large-signal operation. Such a model can be used for the analysis and simulation of the switching converter, no matter in open-loop or in closed-loop, with fast speed. The condition for zero-current switching can also be identified from this model.
DERIVATION OF SIMILAR MATRIX OF THE SCATTERING MATRIX FOR NUMERICAL COMPUTATION IN ELECTRONIC NETWORKS
Authors: TAN E.C.
Published: October 2004

The companion-form system matrix of an electronic network may be inconvenient or inappropriate for certain applications. In pole computations, it may produce values which are less accurate at certain points in the s-plane. In the state-space analysis, it is not a very suitable form for input/output computations especially in large system networks where iterative methods are used. The paper presents the derivation of a similar matrix that is in a more desirable form under the above-mentioned circumstances. Some examples are also given to illustrate the derivation process.
CALIBRATION OF SENSOR CHANNEL DELAY UNCERTAINTIES FOR LINEAR MICROPHONE ARRAYS IN FAR FIELD
Authors: ZHANG MING , ER M.H.
Published: October 2004

In this paper, we present three new methods to calibrate the microphone channel delay uncertainties, and to estimate the talker location for linear microphone arrays in the far field. The proposed methods are based on different a priori information and can be applied to different cases, respectively. The proposed methods are simple and practical. The estimate errors are analytically derived and analyzed. Computer simulations and theoretical computations support the proposed methods.
DESIGN AND MICROCONTROLLER IMPLEMENTATION OF A THREE PHASE SCR POWER CONVERTER
Authors: WALL RICHARD W. , HESS HERBERT L.
Published: October 2004

A single processor controls a three phase silicon controlled rectifier (SCR) power converter. An inexpensive, dual optoisolator interface to the power line provides noise rejection and an improved measure of the zero crossing. A dynamic digital phase-locked loop (PLL) algorithm implemented in an Intel 87C196KD-20 processor achieves frequency tracking, dynamically changing characteristics for improved performance. Dynamically modifying the PLL characteristics permits independent capture and locked dynamics. A feedforward method provides command tracking for improved response without loss of performance. This three-component design (processor, optoisolator, and SCR gate drivers) represents a minimal implementation with potential for closed loop voltage and current control. High speed input and output resources included on the 87C196KD processor make an efficient single-device implementation possible. The processor is less than 1% utilized allowing for additional functions to be added in the future. This system operates on both 50 Hz and 60 Hz power systems without modification or loss of performance.
PERFORMANCE MODELING OF DISCRETE COSINE TRANSFORM FOR STAR GRAPH CONNECTED MULTIPROCESSORS
Authors: DAS B.K. , MAHAPATRA R.N. , CHATTERJI B.N.
Published: October 2004

Discrete Cosine Transform algorithm has emphasized the research attention for its ability to analyze application-based problems in signal and image processing like speech coding, image coding, filtering, cepstral analysis, topographic classification, progressive image transmission, data compression etc. This has major applications in pattern recognition and image processing. In this paper, a Cooley-Tukey approach has been proposed for computation of Discrete Cosine Transform and the necessary mathematical formulations have been developed for Star Graph connected multiprocessors. The signal flow graph of the algorithm has been designed for mapping onto the Star Graph. The modeling results are derived in terms of computation time, speedup and efficiency.
STATE ENCODING OF FINITE STATE MACHINES FOR LOW POWER DESIGN
Authors: CHEN DE-SHENG , SARRAFZADEH MAJID , YEAP GARY K.H.
Published: October 2004

We address the problem of state encoding for synchronous finite state machines (FSMs), targeted for low power design. Most previous work in FSM state encoding has been focused on minimizing chip area and does not consider switching activity of the circuit. As a result, this does not always lead to a power efficient implementation. Especially in CMOS circuits, the switching activity is a very important factor to power dissipation.

In this work, we define a function λ for automatic tradeoff between switching activity and area that contribute to power dissipation. λ is used in determining the encoding affinity between states and is observed to be related to the number of states of an FSM in our experiments. A state encoding algorithm, based on hypercube embedding, is proposed to find encodings of states such that the sum of bit toggles between each pair of states times the encoding affinity between them is minimized. The proposed approach does not require any change in the functional specification of the state machine and can be easily incorporated in present design flow.

Results over a wide range of MCNC benchmark examples which show the efficacy of our technique are presented. A simple function for λ is provided, and it is shown to be robust in finding low-power state encodings.
A FAST ALGORITHM FOR FAULT ISOLATION IN DICTIONARY APPROACH OF ANALOG CIRCUIT DIAGNOSIS
Authors: PRASAD V.C. , PINJALA S.N. RAO
Published: October 2004

Dictionary generation, selection of test nodes and fault isolation are three important phases of dictionary approach of analog fault diagnosis. At present, fast algorithms exist in the literature for the first two phases whereas it is not so for the fault isolation phase. This gap is filled in this paper. First, complexity analysis of existing methods is carried out. The concept of hashing is then applied to achieve fault isolation in the fastest way. In terms of time complexity this is only O(1) as against O( log 2 f) in the best known method, where f is the number of faulty conditions. Thus the computational requirement in the new method is independent of dictionary size. A collision free hashing function useful for this application is also devised.
CONSTRAINT PROPAGATION AND PROGRESSIVE VERIFICATION FOR COMPONENT-BASED PROCESS MODEL
Authors: DENG YI , WANG JIACUN , HE XUDONG , TSAI JEFFREY J. P.
Published: October 2004

System assembly is one of the major issues in engineering complex component-based systems. This is especially true when heterogeneous, COTS and GOTS distributed systems, typical in industrial applications, are involved. The goal of system assembly is not only to make constituent components work together, but also to ensure that the components as a whole behave consistently and guarantee certain end-to-end properties. Despite recent advances, there is a lack of understanding about software composability, as well as theory and techniques for checking and verifying component-based systems. A theory of software system constraints about components, their environment and about system as a whole is the necessary foundation toward solid understanding of the composability of component-based systems. In this paper, we present a systematic approach for constraint specification and constraint propagation in concert with design refinement with a novel technique to ensure consistency between system-wide and component constraints in a design composition process of component-based systems. The consistent constraint propagation is used in our approach to drive progressive verification of the design. It allows us to verify overall design composition without interference of internal details of component designs. Verification is done separately at architectural and component levels without having to compose results of component analyses. A component can be safely replaced with alternative design without re-verifying the overall system composition so long as the replacement conforms to the corresponding interface and component constraint(s).
INTELLIGENT SEMANTIC CONCEPT MAPPING FOR SEMANTIC QUERY REWRITING/OPTIMIZATION IN ONTOLOGY-BASED INFORMATION INTEGRATION SYSTEM
Authors: KWON JUHUM , JEONG DONGWON , LEE LEE-SUB , BAIK DOO-KWON
Published: October 2004

Recently, ontology has been recognized as one of the most suitable global conceptual models for information integration architecture due to its easy taxonomical classification of data model and plentiful support of integrity constraint. However, the concept of mapping from global ontology to local information systems depends mostly on the simple metadata structures that allow for the mapping elements to be extracted with an If-Then-Else comparison statement. This kind of mapping is not suitable for ontology based data model in which the concepts are in the multiple subsumption relations. That is, there needs to be a semantic concept mapping in the case of a global concept that is to be mapped to the most specialized/generalized local concept in multiple Is-A structure, which cannot be mapped with simple direct one to one mapping. This kind of mapping needs inference mechanism to map one concept to substantially many target concepts in the concept inclusion hierarchy for an effective semantic query rewriting/optimization. In this paper, we provide an innovative method for semantic ontology concept mapping using Metadata-Based Logic (MBL) approach, which is equipped with knowledge inference mechanism so that the mapping elements can be reasoned automatically. We present semantic mapping patterns to accommodate subsumption problem and detect incoherence for a given global query. The experimental results gave viable results on the semantic query rewriting/optimization.
AN RPCL-BASED INDEXING APPROACH FOR SOFTWARE COMPONENT CLASSIFICATION
Authors: NAKKRASAE SATHIT , SOPHATSATHIT PERAPHON
Published: October 2004

Software Engineering is not only a technical discipline of its own, but also a problem domain where technologies coming from other disciplines are relevant and can play important roles. One important example is knowledge engineering, a term that is used in a broad sense to encompass artificial intelligence, computational intelligence, knowledge bases, data mining, and machine learning [13]. Many typical software development issues can benefit from these disciplines. For this reason, we will employ computational intelligence approach to classify software component repository into similar component cluster groups with the help of Rival Penalized Competitive Learning algorithm. The center of each cluster will be used to construct the coarse grain classification indexing structure. Subsequent retrieval requirements of software components are compared with all the indexed cluster centers. Any software components belonging to the cluster partition whose center is closest to the required software component will be retrieved and participated in selecting the most suitable software component at the fine grain level. This approach not only is suitable for multi-dimensional data, but also automatically decides the correct model classification.
EXPRESSING PRODUCT DIVERSIFICATION — CATEGORIZING AND CLASSIFYING VARIABILITY IN SOFTWARE PRODUCT FAMILY ENGINEERING
Authors: JARING MICHEL , BOSCH JAN
Published: October 2004

In a software product family context, software architects design architectures that support product diversification in both space (multiple contexts) and time (changing contexts). Product diversification is based on the concept of variability: a single architecture and a set of components support a family of products. Software product families have to support increasing amounts of variability, thereby making variability engineering a primary concern in software product family development. The first part of this paper (1) suggests a two-dimensional, orthogonal categorization of variability realization techniques and classifies these variability categories into system maturity levels. The second part (2) discusses a case study of an industrial software product family of mobile communication infrastructure for professional markets such as the military. The study categorizes and classifies the variability in this product family according to criteria common to virtually all software development projects.
THE RESIDUAL BOUND OF A FINITE ALGEBRA IS NOT COMPUTABLE
Authors: MCKENZIE RALPH
Published: October 2004

We exhibit a construction which produces for every Turing machine [Formula: see text], an algebra [Formula: see text] (finite and of finite type) such that the Turing machine halts iff the variety generated by [Formula: see text] is residually finite.
TARSKI’S FINITE BASIS PROBLEM IS UNDECIDABLE
Authors: MCKENZIE RALPH
Published: October 2004

We exhibit a construction which produces for every Turing machine [Formula: see text], an algebra [Formula: see text] (finite and of finite type) such that the Turing machine halts iff the algebra has a finite basis for its equations.
GROWTH AND EXISTENCE OF IDENTITIES IN A CLASS OF FINITELY PRESENTED INVERSE SEMIGROUPS WITH ZERO
Authors: SHNEERSON L.M. , EASDOWN D.
Published: October 2004

We prove that a finitely presented Rees quotient of a free inverse semigroup has polynomial or exponential growth, and that the type of growth is algorithmically recognizable. We prove that such a semigroup has polynomial growth if and only if it satisfies a certain semigroup identity. However we give an example of such a semigroup which has exponential growth and satisfies some nontrivial identity in signature with involution.
STRONG MORITA EQUIVALENCE AND THE SYNTHESIS THEOREM
Authors: TALWAR SUNIL
Published: October 2004

In recent work we associated a natural category to a semigroup and developed Morita theory for semigroups. In particular we gave a generalisation of Rees’ Theorem which led us to define what we call a Morita semigroup, this is our analogue of a structure matrix semigroup. In this article we formulate a method for extending Morita semigroups by groups. We say that a semigroup is an iterative Morita semigroup if it is obtained by successive applications of pasting families of Morita semigroups which have been extended by groups. By relying on Morita theory we show that every regular unambiguous semigroup is isomorphic to an iterative Morita semigroup of a special form. Our result can be viewed as a co-ordinate free version of the Synthesis Theorem.
COMPLETELY 0-SIMPLE SEMIGROUPS OF LEFT QUOTIENTS OF A SEMIGROUP
Authors: ÁNH PHAM NGOC , GOULD VICTORIA , MÁRKI LÁSZLÓ
Published: October 2004

In this paper we investigate the class of all completely 0-simple semigroups of left quotients of a given semigroup S. We show that (if the class is non-empty) it has a ‘greatest’ member ∈S which is in a sense the free completely 0-simple semigroup on S, and describe how the other members can be obtained as homomorphic images of [Formula: see text].
ON THE BURNSIDE SEMIGROUPS xn = xn+m
Authors: DO LAGO ALAIR PEREIRA
Published: October 2004

In this paper we prove that the congruence classes of A* associated to the Burnside semigroup with |A| generators defined by the equation xn=xn+m, for n≥4 and m≥1, are recognizable.

This problem was originally formulated by Brzozowski in 1969 for m=1 and n≥2. De Luca and Varricchio solved the problem for n≥5 in 90. A little later, McCammond extended the problem for m≥1 and solved it independently in the cases n≥6 and m≥1. Our work, which is based on the techniques developed by de Luca and Varricchio, extends both these results.

We effectively construct a minimal generator Σ of our congruence. We introduce an elementary concept, namely the stability of productions, which allows to eliminate all hypothesis related to the values of n and m. A substantial part of our proof consists of showing that all productions in Σ are stable, for n≥4 and m≥1.

We also show that Σ is a Church-Rosser rewriting system, thus solving the word problem, and show that the semigroup is finite [Formula: see text]-above. We prove that the frame of the ℛ-classes of the semigroup is a tree. We characterize and calculate the ℛ-classes, ℋ-classes and the [Formula: see text]-classes of the semigroup, regular or not, and prove that its maximal subgroups are cyclic of order m whenever all productions of Σ are stable.

Recently Guba extended the cases in which the conjecture holds to n≥3 and m≥1. Using his work we obtain the stability of the productions of Σ for n=3 and m≥1 too and, hence, all properties about the semigroup structure hold in this case.
THE BOUNDARY OF ITERATED MORPHISMS ON FREE SEMI-GROUPS
Authors: NARBEL PHILIPPE
Published: October 2004

This paper introduces a generalized way of defining languages of infinite words by topological means. It focuses on languages generated by iterating morphisms on free semi-groups (also called substitutions or D0L-systems). The main result is an effective construction of the boundary of such languages which leads to a bijective mapping of the boundary onto a regular language. Among the obtained properties are the uncountability of the boundary and the strict quasiperiodicity of its words. We also investigate the decidability of the boundary equality problem and the dynamical system induced by the inversed morphism.
A QUASI-OPTIMAL TIME FOR SYNCHRONIZING TWO INTERACTING FINITE AUTOMATA
Authors: VIVIEN H.
Published: October 2004

Mazoyer has constructed a family [Formula: see text] of systems of two interacting finite automata which synchronize in time about [2/ log (m)] Δ log (∆) where Δ is the delay of communication. Here we prove that solutions “à la Mazoyer” are optimal in the following senses: 1°) any synchronizing system operates in time at least [1/ log (N)]Δ log (∆/2), N being the number of states, so that the order Δ log (∆) is optimal 2°) Mazoyer-like systems have about a m3 states so that [2/ log (m)] is about 6 times the above lower bound, which is thus nearly optimal.
A DIRECTLY REPRESENTABLE VARIETY HAS A DISCRETE FIRST-ORDER LAW
Authors: BURRIS STANLEY , IDZIAK PAWEL
Published: October 2004

Using simple counting arguments, the Feferman-Vaught techniques and selected results from universal algebra, we show that for any directly representable variety V there is a positive integer k such that for any first-order sentence ϕ the proportion of members of V of size at most x which satisfy ϕ tends to a limit belonging to [Formula: see text] as x goes to infinity. Furthermore there is a first-order statement for which the limit is [Formula: see text]. V has a 0–1 law (i.e., k=1) iff the finite members factor uniquely into directly indecomposables.
E-SOLID E-VARIETIES OF REGULAR SEMIGROUPS WHICH ARE BIEQUATIONAL
Authors: BROEKSTEEG RAYMOND
Published: October 2004

We extend the notion of biidentity from bivarieties of orthodox semigroups to e-varieties of regular semigroups. We show that an E-solid e-variety ε may be described in terms of biidentities (within the e-variety of all regular semigroups) if and only if there is an integer n≥2 such that for each pair e, f of idempotents of each member of ε, we have that (ef)n=ef.
METANILPOTENT VARIETIES WITHOUT TORSION AND VARIETIES OF GROUPS OF PRIME POWER EXPONENT
Authors: GUPTA C.K. , KRASIL’NIKOV A.N.
Published: October 2004

The following results are established: (i) there exists a nonfinitely based variety of (nilpotent of class 2)-by-(nilpotent of class 2) groups, whose relatively free groups are torsion free; (ii) for every prime p, p≥3, there exists a nonfinitely based metanilpotent variety of groups of exponent p2.
TENSOR COMPLETION FOR A CERTAIN CLASS OF GROUPS
Authors: LIOUTIKOVA EKATERINA
Published: October 2004

In this paper we construct the tensor A-completion over an arbitrary torsion-free ring A for groups whose maximal abelian subgroups are either conjugate separated or A-modules. As a corollary, this result gives us an explicit description of the structure of tensor completion for groups of the form F/N′, in particular, for free solvable groups. We also prove that the class of all A-faithful groups is closed under free products.
THE BURNSIDE PROBLEM FOR GROUPS OF LOW QUADRATIC GROWTH
Authors: INCITTI ROBERTO
Published: October 2004

We show with a combinatorial argument that a finitely generated infinite group whose growth function relative to some finite generating system is less or equal to [Formula: see text], r<2, contains an element of infinite order. This result is aimed at investigating the combinatorial nature of M. Gromov’s theorem on groups of polynomial growth.
SERRE RELATIONS AND GRÖBNER-SHIRSHOV BASES FOR SIMPLE LIE ALGEBRAS I
Authors: BOKUT L.A. , KLEIN A.A.
Published: October 2004

A Gröbner-Shirshov basis for the Lie algebra An, abstractly defined by generators hi, xi, yi, i=1,..., n and the Serre relations for the Cartan matrix An, over a field k of characteristic ≠2 is constructed. It consists of the Serre relations for An together with the following relations: [Formula: see text] with j≥1, i≥2, i+j≤n and the same relations for y1,…, yn, where by [z1z2…zm] we mean [z1[z2… zm]]. As an application we get a direct proof that An, as defined, is isomorphic to sℓn+1(k).
SERRE RELATIONS AND GRÖBNER-SHIRSHOV BASES FOR SIMPLE LIE ALGEBRAS II
Authors: BOKUT L.A. , KLEIN A.A.
Published: October 2004

Gröbner-Shirshov bases for the Lie algebras Bn, Cn, Dn, abstractly defined by generators and the Serre relations for the corresponding Cartan matrices over a field of characteristic ≠2, 3, are constructed. As an application, we obtain that each of the previous algebras is isomorphic to a classical simple Lie algebra so2n+1(k), sp2n(k), so2nk respectively.
TWO AUTOMATIC SPANNING TREES IN SMALL CANCELLATION GROUP PRESENTATIONS
Authors: JOHNSGARD KARIN
Published: October 2004

Gersten and Short showed that group presentations satisfying certain minimal small cancellation conditions are automatic. The automatic structure they described does not have unique group element representatives. It is easy, however, to modify their language to produce an automatic spanning tree of geodesics: that is, an automatic structure of geodesics which is both prefix-closed and has unique representatives. When combined with a construction showing that all geodesic representatives of a group element are encoded in a tiling of a particular geometric form, this shows that in fact the language of lexicographically least geodesics is also automatic (it is clearly a spanning tree).
THE IDEMPOTENTS IN A PERIODIC SEMIGROUP
Authors: PASTIJN FRANCIS
Published: October 2004

Let [Formula: see text] be the semigroup variety determined by the identity xm=xm+k. For [Formula: see text] we define operations on the set E(S) of idempotents of S and thus obtain the idempotent algebra of S. For any subvariety [Formula: see text] of [Formula: see text] the idempotent algebras of the members of [Formula: see text] form a variety [Formula: see text] and [Formula: see text] yields a complete homomorphism of the lattice [Formula: see text] of subvarieties of [Formula: see text] onto the lattice [Formula: see text] of subvarieties of [Formula: see text]. The lattice [Formula: see text] contains a ∩-semilattice isomorphic to the ∩-semilattice [Formula: see text] of group varieties of exponent dividing k for every m≥1. In particular, for appropriate k, the lattice of subvarieties of the variety of all idempotent algebras of the completely regular semigroups over groups that belong to [Formula: see text] is of the power of the continuum. For any [Formula: see text], ρ→ρ|E(S) yields a complete homomorphism of the congruence lattice of S into the lattice of equivalence relations on E(S).
REPRESENTATIONS OF LOCALLY INVERSE *-SEMIGROUPS
Authors: IMAOKA TERUO , INATA ISAMU , YOKOYAMA HIROAKI
Published: October 2004

The first author obtained a generalization of Preston-Vagner Representation Theorem for generalized inverse *-semigroups. In this paper, we shall generalize their results for locally inverse *-semigroups.

Firstly, by introducing a concept of a π-set (which is slightly different from the one in [7]), we shall construct the π-symmetric locally inverse *-semigroup on a π-set, and show that any locally inverse *-semigroup can be embedded up to *-isomorphism in the π-symmetric locally inverse semigroup on a π-set. Moreover, we shall obtain that the wreath product of locally inverse *-semigroups is also a locally inverse *-semigroup.
APPLICATION OF COMPUTERS TO QUESTIONS LIKE THOSE OF BURNSIDE, II
Authors: NEWMAN M.F. , O’BRIEN E.A.
Published: October 2004

We show how automorphisms can be used to reduce significantly the resources needed to enforce laws in p-groups. This increases the extent to which Burnside groups with prime-power exponent can be studied in detail. For example, we describe how to construct power-conjugate presentations for the restricted Burnside groups R(5, 4) and R(3, 5) which have orders 22728 and 52282 respectively. We also describe how to determine the exponent of a p-group and report on relevant features of the current implementation of an algorithm to compute power-conjugate presentations.
CONJUGACY AND TRANSPOSITION FOR INVERSE MONOID PRESENTATIONS
Authors: SILVA PEDRO V.
Published: October 2004

The transposition problem is shown to be decidable for inverse monoid presentations of the form Inv , where e is a Dyck word on the alphabet X∪X−1. If e is a, restricted Dyck word, the left conjugacy problem is solved as well, and the (left) conjugacy relation is shown to be the union of the transitive closure of the transposition relation with the universal relation on the semilattice of idempotents, a result which does not hold for a general Dyck word e.
NONCOMMUTATIVE BELL POLYNOMIALS
Authors: SCHIMMING RAINER , RIDA SAAD ZAGLOUL
Published: October 2004

The recursive definition for the sequence of the Bell polynomials is generalized to noncommutative variables and then explicitly solved. As applications, we present formulas for the powers of a first-order matrix-valued differential operator, of the “substantial derivative” to a dynamical system, and for the Taylor coefficients of the time-ordered exponential integral.
REPRESENTATIONS OF SEMIGROUPS BY TRANSFORMATIONS AND THE CONGRUENCE LATTICE OF AN EVENTUALLY REGULAR SEMIGROUP
Authors: AUINGER K. , HALL T.E.
Published: October 2004

On any eventually regular semigroup S, congruences ν, μL, μR, μ, K, KL, KR, ζ are introduced which are the greatest congruences over: nil-extensions (n.e.) of completely simple semigroups, n.e. of left groups, n.e. of right groups, n.e. of groups, n.e. of rectangular bands, n.e. of left zero semigroups, n.e. of right zero semigroups, nil-semigroups, respectively. Each of these congruences is induced by a certain representation of S which is defined on an arbitrary semigroup. These congruences play an important role in the study of lattices of varieties, pseudovarieties and existence varieties. The investigation also leads to eight complete congruences U, Tt, Tr, T, K, Kl, Kr, Z on the congruence lattice Con (S) of S.
GRAPH EXPANSIONS OF RIGHT CANCELLATIVE MONOIDS
Authors: GOULD VICTORIA
Published: October 2004

The relations ℛ* and [Formula: see text] on a monoid M are natural generalizations of Green’s relations ℛ and [Formula: see text], which coincide with ℛ and [Formula: see text] if M is regular. A monoid M in which every ℛ*-class [Formula: see text] contains an idempotent is called left (right) abundant; if in addition the idempotents of M commute, that is, E(M) is a semilattice, then M is left (right) adequate. Regular monoids are obviously left (and right) abundant and inverse monoids are left (and right) adequate. Many of the well known results of regular and inverse semigroup theory have analogues for left abundant and left adequate monoids, or at least to special classes thereof.

The aim of this paper is to develop a construction of left adequate monoids from the Cayley graph of a presentation of a right cancellative monoid, inspired by the construction of inverse monoids from group presentations, given by Margolis and Meakin in [10]. This technique yields in particular the free left ample (formerly left type A) monoid on a given set X.
UPPER BOUNDS IN THE RESTRICTED BURNSIDE PROBLEM II
Authors: VAUGHAN-LEE MICHAEL , ZELMANOV E.I.
Published: October 2004

We show that if G is a finite m generator group of exponent n, with m>1, then [Formula: see text] This result extends bounds previously obtained for finite groups of prime power exponent. The proof is based on a reduction theorem for the restricted Burnside problem due to Hall and Higman.
ON THE COMBINATION THEOREM FOR NEGATIVELY CURVED GROUPS
Authors: GITIK RITA
Published: October 2004

We give a simple proof of a sufficient condition for an amalgamated free product of two negatively curved groups to be negatively curved, and we compute the curvature of such products.
Diagnosis, Treatment, and Long-Term Management of Kawasaki Disease
Authors: Newburger Jane W. , Takahashi Masato , Gerber Michael A. , Gewitz Michael H. , Tani Lloyd Y. , Burns Jane C. , Shulman Stanford T. , Bolger Ann F. , Ferrieri Patricia , Baltimore Robert S. , Wilson Walter R. , Baddour Larry M. , Levison Matthew E. , Pallasch Thomas J. , Falace Donald A. , Taubert Kathryn A.
Published: October 2004

Background—

Kawasaki disease is an acute self-limited vasculitis of childhood that is characterized by fever, bilateral nonexudative conjunctivitis, erythema of the lips and oral mucosa, changes in the extremities, rash, and cervical lymphadenopathy. Coronary artery aneurysms or ectasia develop in ∼15% to 25% of untreated children and may lead to ischemic heart disease or sudden death.

Methods and Results—

A multidisciplinary committee of experts was convened to revise the American Heart Association recommendations for diagnosis, treatment, and long-term management of Kawasaki disease. The writing group proposes a new algorithm to aid clinicians in deciding which children with fever for ≥5 days and ≤4 classic criteria should undergo echocardiography, receive intravenous gamma globulin (IVIG) treatment, or both for Kawasaki disease. The writing group reviews the available data regarding the initial treatment for children with acute Kawasaki disease, as well for those who have persistent or recrudescent fever despite initial therapy with IVIG, including IVIG retreatment and treatment with corticosteroids, tumor necrosis factor-α antagonists, and abciximab. Long-term management of patients with Kawasaki disease is tailored to the degree of coronary involvement; recommendations regarding antiplatelet and anticoagulant therapy, physical activity, follow-up assessment, and the appropriate diagnostic procedures to evaluate cardiac disease are classified according to risk strata.

Conclusions—

Recommendations for the initial evaluation, treatment in the acute phase, and long-term management of patients with Kawasaki disease are intended to assist physicians in understanding the range of acceptable approaches for caring for patients with Kawasaki disease. The ultimate decisions for case management must be made by physicians in light of the particular conditions presented by individual patients.
Practice Standards for Electrocardiographic Monitoring in Hospital Settings
Authors: Drew Barbara J. , Califf Robert M. , Funk Marjorie , Kaufman Elizabeth S. , Krucoff Mitchell W. , Laks Michael M. , Macfarlane Peter W. , Sommargren Claire , Swiryn Steven , Van Hare George F.
Published: October 2004

The goals of electrocardiographic (ECG) monitoring in hospital settings have expanded from simple heart rate and basic rhythm determination to the diagnosis of complex arrhythmias, myocardial ischemia, and prolonged QT interval. Whereas computerized arrhythmia analysis is automatic in cardiac monitoring systems, computerized ST-segment ischemia analysis is available only in newer-generation monitors, and computerized QT-interval monitoring is currently unavailable. Even in hospitals with ST-monitoring capability, ischemia monitoring is vastly underutilized by healthcare professionals. Moreover, because no computerized analysis is available for QT monitoring, healthcare professionals must determine when it is appropriate to manually measure QT intervals (eg, when a patient is started on a potentially proarrhythmic drug). The purpose of the present review is to provide ‘best practices’ for hospital ECG monitoring. Randomized clinical trials in this area are almost nonexistent; therefore, expert opinions are based upon clinical experience and related research in the field of electrocardiography. This consensus document encompasses all areas of hospital cardiac monitoring in both children and adults. The emphasis is on information clinicians need to know to monitor patients safely and effectively. Recommendations are made with regard to indications, timeframes, and strategies to improve the diagnostic accuracy of cardiac arrhythmia, ischemia, and QT-interval monitoring. Currently available ECG lead systems are described, and recommendations related to staffing, training, and methods to improve quality are provided.
Early Modernities and Contentious Politics in Mid-Qing China, c. 1740–1839
Authors: Hung Ho-fung
Published: October 2004

In the last three decades, a spate of research brought to light the dynamics of contentious politics in early modern Europe. These studies suggest that surges of commerce and centralized state power led to a transition of contentious politics from reactive to proactive claims, and from violent to non-violent repertoires. This literature assumes the uniqueness of the western experience, and pays little attention to the non-western world. This article is an attempt to examine the patterns of contentious politics in mid-Qing China, a period when China witnessed profound commercial growth and political centralization. Based on a catalogue of contentious events derived from archival sources, the article finds that contentious politics over mid-Qing China changed from predominantly proactive and peaceful actions to more reactive and violent forms. The direction of transition was opposite to that in Europe, and could be explained by the specific trajectories of state formation and commercialization in early modern China. The article also argues that the modern revolutionary movement in 20th-century China was a continuation of the reactive, violent contentions of the early 19th century. This study shows that ‘modernization’ of contentious politics in non-western civilizations is rarely a simple repetition of the western way, but is rather a complex interaction between western influences and indigenous tracks of development.