bluuebunny/crossref_metadata_2025 huggingface dataset:
Distinct Cohesin Complexes Organize Meiotic Chromosome Domains
Authors: Kitajima Tomoya S. , Yokobayashi Shihori , Yamamoto Masayuki , Watanabe Yoshinori
Published: May 2003

Meiotic cohesin complexes at centromeres behave differently from those along chromosome arms, but the basis for these differences has remained elusive. The fission yeast cohesin molecule Rec8 largely replaces its mitotic counterpart, Rad21/Scc1, along the entire chromosome during meiosis. Here we show that Rec8 complexes along chromosome arms contain Rec11, whereas those in the vicinity of centromeres have a different partner subunit, Psc3. The armassociated Rec8-Rec11 complexes are critical for meiotic recombination. The Rec8-Psc3 complexes comprise two different types of assemblies. First, pericentromeric Rec8-Psc3 complexes depend on histone methylation-directed heterochromatin for their localization and are required for cohesion during meiosis II. Second, central core Rec8-Psc3 complexes form independently of heterochromatin and are presumably required for establishing monopolar attachment at meiosis I. These findings define distinct modes of assembly and functions for cohesin complexes at different regions along chromosomes.
Regulation of Aging and Age-Related Disease by DAF-16 and Heat-Shock Factor
Authors: Hsu Ao-Lin , Murphy Coleen T. , Kenyon Cynthia
Published: May 2003

The
Caenorhabditis elegans
transcription factor HSF-1, which regulates the heat-shock response, also influences aging. Reducing
hsf-1
activity accelerates tissue aging and shortens life-span, and we show that
hsf-1
overexpression extends lifespan. We find that HSF-1, like the transcription factor DAF-16, is required for
daf-2
–insulin/IGF-1 receptor mutations to extend life-span. Our findings suggest this is because HSF-1 and DAF-16 together activate expression of specific genes, including genes encoding small heat-shock proteins, which in turn promote longevity. The small heat-shock proteins also delay the onset of polyglutamine-expansion protein aggregation, suggesting that these proteins couple the normal aging process to this type of age-related disease.
Rapid Turnover of Hyphae of Mycorrhizal Fungi Determined by AMS Microanalysis of
14
C
Authors: Staddon Philip L. , Ramsey Christopher Bronk , Ostle Nick , Ineson Philip , Fitter Alastair H.
Published: May 2003

Processes in the soil remain among the least well-characterized components of the carbon cycle. Arbuscular mycorrhizal (AM) fungi are ubiquitous root symbionts in many terrestrial ecosystems and account for a large fraction of photosynthate in a wide range of ecosystems; they therefore play a key role in the terrestrial carbon cycle. A large part of the fungal mycelium is outside the root (the extraradical mycelium, ERM) and, because of the dispersed growth pattern and the small diameter of the hyphae (<5 micrometers), exceptionally difficult to study quantitatively. Critically, the longevity of these fine hyphae has never been measured, although it is assumed to be short. To quantify carbon turnover in these hyphae, we exposed mycorrhizal plants to fossil (“carbon-14–dead”) carbon dioxide and collected samples of ERM hyphae (up to 116 micrograms) over the following 29 days. Analyses of their carbon-14 content by accelerator mass spectrometry (AMS) showed that most ERM hyphae of AM fungi live, on average, 5 to 6 days. This high turnover rate reveals a large and rapid mycorrhizal pathway of carbon in the soil carbon cycle.
Strain Gradient Influence on Diffusion Coefficients of Deuterium in Absorption and Desorption of Deuterium in Pd81Pt19 Membrane
Authors: Dudek Danuta
Published: May 2003

The diffusion of deuterium through a Pd81Pt19 membrane was investigated. At six temperatures in the range 278.2-328.2 K the diffusion coefficients were determined by breakthrough method for the membrane with no initial content of deuterium. The determined activation energy of diffusion of deuterium equals E = 26.4 kJ/mol. The solubility of deuterium in Pd81Pt19 alloy at 278.2 K was measured by volumetric method. The influence of self-stresses on diffusion of deuterium was investigated by determination of diffusion coefficients for the Pd81Pt19 membrane with different initial contents of deuterium at 278.2 K.
A New Method of Analysis of Polarographic Waves
Authors: Ruiz-Morales Juan Carlos , Rodríguez Placeres Jesús César , Barrera Niebla Manuel , Cuesta Sánchez Mariana
Published: May 2003

A method of analysis of polarographic waves of simple electrode processes is proposed. The quasi-reversible half-wave potential, Ec1/2, is involved in the determination of thermodynamic and kinetic parameters of electrode processes. This potential is determined very easily and with great precision. In order to facilitate the use of the method proposed, we have developed a computer program for Windows.
Study of the Reaction of Platinum(IV) with Dimethylglyoxime by UV Spectrophotometry
Authors: Georgieva Marija , Andonovski Blagoja
Published: May 2003

The complex formation of dimethylglyoxime and platinum(IV) in alkaline medium has been investigated by ultraviolet spectroscopy. This study has shown that more than one complex species exists in solution. The effects of pH variation of ammonia buffer solution from 6.0 to 13.0 were investigated with respect to the absorption spectra. The molar ratios method, the Job's method and the method of relative recovery of complex species were used. It was found that the stoichiometric ratio Pt(IV)/dimethylglyoxime was 1:1, 1:2 and 2:1. The molar absorptivity (log ε = 4.1 at 260 nm) and the formation constant of the complex (log K2,1 = 15.0) were obtained. The stability constants of the [Pt(Hdmg)2(NH3)2] complex determined by the molar ratios and Job's method were log β2 = 9.2 ± 0.2 and log β2 = 9.3 ± 0.2, respectively.
First Examples of Homogeneous Catalytic Cyclotrimerization and Polymerization of Phenylacetylene and Copolymerization of Phenylacetylene and Norbonene with Dinuclear Complexes Containing Unbridged Metal-Metal Quadruple Bond
Authors: Mertis Konstantinos , Arbilias Stavros , Argyris Demos , Psaroudakis Nikos , Vohlídal Jiří , Lavastre Olivier , Dixneuf Pierre H.
Published: May 2003

First examples of application of dinuclear complexes containing unbrigded metal-metal quadruple bond as catalysts in cyclotrimerization, oligomerization and polymerization of substituted acetylene are reported. The d4-d4 dinuclear complexes (Bu4N)2[Re2X8] (1) (1a, X = Cl; 1b, X = Br and 1c, X = I) show low activity and the complex [Mo2Cl4(MeOH)2(PPh3)2] (2) medium activity in cyclotrimerization and oligomerization of phenylacetylene (PA). In contrast, the tungsten-based d4-d4, complex Na4[W2Cl8] (3) exhibits high polymerization activity (polymer yield above 90%) and ca 75% cis-selectivity in tetrahydrofuran. The activity and cis-stereoselectivity of these single-component catalysts decrease in the order 3 >> 2 >> 1, which is proportional to the metal-metal quadruple bond propensity towards ligand addition reactions. Complex 3 induces metathesis polymerization of norbornene (NBE) to poly(cyclopentene-1,3-diylvinylene) with 82% cis-selectivity and copolymerization of PA and NBE to almost all-cis high-molecular-weight copolymer containing cyclopentene-1,3-diylvinylene units, which is free of longer sequences of both PA and NBE units. This suggests that also homopolymerization of PA with 3 proceeds by the metathesis mechanism and that the PA/NBE copolymer structure is close to the alternating one.
Polymerization of Propene with Modified Constrained Geometry Complexes. Double-Bond Isomerization in Pendant Alkenyl Groups Attached to Cyclopentadienyl Ligands
Authors: Staal Oetze K. B. , Beetstra Dirk J. , Jekel Andries P. , Hessen Bart , Teuben Jan H. , Štěpnička Petr , Gyepes Róbert , Horáček Michal , Pinkas Jiří , Mach Karel
Published: May 2003

Polymerization of propene with dimethylsilylene-bridged (amidocyclopentadienyl)dichlorotitanium(IV) complexes [TiCl2{η5-1-(t-BuSiMe2N-κN)-2,3,4-Me3-5-R-C5}], where R = Me (1), H (2), Ph (3), 4-fluorophenyl (4), but-2-en-2-yl (5), and butyl (6), combined with excess methylaluminoxane revealed a moderate effect of the substituent R on the catalyst activity and the molecular weight of polypropene. The asymmetric substitution in the position adjacent to the bridging carbon atom resulted in polymer yields decreasing in the order 1 > 6 > 3 ≈ 5 > 4 > 2 while polymers with the molecular weights (Mw) close to 2.5 × 105 for 1, 3, and 4, 1.5 × 105 for 5 and 6, and 7.5 × 104 for 2 were obtained. The 13C NMR analysis of the polymers has shown that atactic polypropene is slightly enriched with syndiotactic triads for all the catalysts. Investigation of the crystal structure of 5 by X-ray crystallography revealed that the double bond in but-3-en-2-yl had shifted to an internal position to give the isomeric, but-2-en-2-yl-substituted complex. Likewise, the spectroscopic data for complex 7 prepared from the ligand containing but-3-en-1-yl substituent, indicate the absence of terminal double bond.
THE PERMUTATIONAL GRAPH: A NEW NETWORK TOPOLOGY
Authors: OKAWA SATOSHI
Published: May 2003

This paper introduces the penmutational graph, a new network topology, which preserves the same desirable properties as those of a star graph topology. A permutational graph can be decomposed into subgraphs induced by node sets defined by equivalence classes. Using this decomposition, its structual properties as well as the relationship among graph families, permutational graphs, star graphs, and complete graphs are studied. Moreover, the diameters of permutational graphs are investigated and good estimates are obtained which are better than those of some network topologies of similar orders.
THE DIAMETER AND HAMILTONIAN CYCLE OF THE GENERALIZED DE BRUIJN GRAPHS UGB(n, n(n+1))
Authors: NOCHEFRANCA LUZ R. , SY POLLY W.
Published: May 2003

In this paper, we will show that the diameter of the generalized De Bruijn graph UGB (n, n(n+1)) is 3 using an automorphism of the graph, and we will also give an algorithm to find a hamiltonian cycle of UGB (n, n(n+1)) for all integers n≥2.
THE CUBE-OF-RINGS INTERCONNECTION NETWORK
Authors: CORTINA THOMAS J. , XU ZHIWEI
Published: May 2003

We present a family of interconnection networks named the Cube-Of-Rings (COR) networks along with their basic graph-theoretic properties. Aspects of group graph theory are used to show the COR networks are symmetric and optimally fault tolerant. We present a closed-form expression of the diameter and optimal one-to-one routing algorithm for any member of the COR family. We also discuss the suitability of the COR networks as the interconnection network of scalable parallel computers.
A DYNAMIC SCHEDULING COMMUNICATION PROTOCOL AND ITS ANALYSIS FOR HYPERCUBE NETWORKS
Authors: BANERJEE AYAN , VARVARIGOS EMMANOUEL (MANOS)
Published: May 2003

We propose a new protocol for one-to-one communication in multiprocessor networks, which we call the Dynamic Scheduling Communication (or DSC) protocol. In the DSC protocol, the capacity of a link is partitioned into two channels: a data channel, used to transmit packets, and a control channel used to make reservations. We initially describe the DSC protocol and the data structures needed to implement it for a general network topology. We then analyze the steady-state throughput of the DSC protocol for random node-to-node communication in a hypercube topology. The analytical results obtained are in very close agreement with corresponding simulation results. For the hypercube topology, and under the same set of assumptions on the node architecture and the routing algorithm used, the DSC protocol is found to achieve higher throughput than packet switching, provided that the size of the network is sufficiently large. We also investigate the relationship between the achievable throughput and the fraction of network capacity dedicated to the control channel, and present a method to select this fraction so as to optimize throughput.
NETWORK PROPERTIES OF DOUBLE AND TRIPLE FIXED STEP GRAPHS
Authors: LIESTMAN A. L. , OPATRNY J. , ZARAGOZÁ M.
Published: May 2003

The network properties of double and triple fixed step graphs are considered. We determine that the broadcast times of double and triple fixed step graphs of diameter D are equal to D+2 and D+3, respectively. Some results on the embeddings of grids into these graphs with dilation 1 and 2 are given. For a triple fixed step graph we give a method to calculate the routing between any two vertices of the graph. Furthermore, we show that the diameter of the surviving route graph remains two for any set F of faults for |F|=5, which is optimum.
SHUFFLE-RING: A NEW CONSTANT-DEGREE NETWORK
Authors: CHEN GUIHAI , LAU FRANCIS C. M.
Published: May 2003

The hypercube as a parallel interconnection network has been of academic and engineering concern for tens of year due to its many merits. However, its increasing node degree is an obvious weakness. Some networks such as the cube-connected cycles (CCC) and the de Bruijn network have been proposed to overcome the increasing degree of the hypercube. In this paper, we present a new cost-effective network which outperforms the cube network. It can overcome the increasing degree of cube networks while keeping the advantages of the cube network such as logarithmic diameter, easy routing, optimal fault tolerance, and suitability for the ASCEND/DESCEND class of parallel problems. Furthermore, the proposed network achieves the logarithmic diameter with a very small constant node degree, 3 or 4.
INTEGER SORTING AND ROUTING IN ARRAYS WITH RECONFIGURABLE OPTICAL BUSES
Authors: PAVEL SANDY , AKL SELIM G.
Published: May 2003

In this paper we present deterministic algorithms for integer sorting and on-line packet routing on arrays with reconfigurable optical buses. The main objective is to identify the mechanisms specific to this type of architectures that allow us to build efficient integer sorting, partial permutation routing and h-relations algorithms. The consequences of these results on the PRAM simulation complexity are also investigated.
CONTINUOUS ROUTING IN PACKET SWITCHES
Authors: GRAMMATIKAKIS MILTOS D. , FLEURY ERIC , KRAETZL MIRO
Published: May 2003

Considering continuous routing, we analyze the transient behavior of n×n routers with input buffering, split input buffering, output buffering, and central buffering with dedicated virtual circuits, one for each source-destination pair in a network. Assuming similar buffer space requirements, output buffering has the highest throughput. Split input buffering and central buffering have comparable performance; split input buffering slightly outperforms central buffering for large switches. Input buffering is known to saturate at packet generating rates above 0.586. By extending these models, two 1024-node, unique-path multistage networks configured with (approximately-modeled) input buffered STC104 32×32 switches, or central buffered Telegraphos 4×4 switches (Telegraphos I version) are compared. Surprisingly, the network configured with smaller switches performs better. This is due to the higher peak bandwidth of the Telegraphos switch and saturation of the input buffered STC104 switch.
SUBOPTIMAL-OPTIMAL ROUTING FOR LAN INTERNETWORKING USING TRANSPARENT BRIDGES
Authors: GARCIA ROMAN , DUATO JOSE
Published: May 2003

The current standard transparent bridge protocol IEEE-802.1D is based on the Spanning Tree (ST) algorithm. It has a very important restriction: it cannot work when the topology has active loops. Therefore, a tree is the only possible interconnection topology that can be used. The ST algorithm guarantees that the active topology is a tree discarding lines that form loops. However, because of this, network bandwidth cannot be fully utilized. Moreover, trees have a very serious bottleneck near the root. This paper proposes a new transparent bridge protocol for LAN interconnection that allows active loops. Therefore, strongly connected regular topologies like tori, hypercubes, meshes, etc., as well as irregular topologies can be used without wasting bandwidth. As loops provide alternative paths, the new protocol (named OSR for Optimal-Suboptimal Routing) uses optimal routing or, in the worst case, suboptimal routing.
PERFORMANCE ANALYSIS OF WORMHOLE ROUTED K-Ary N-TREES
Authors: PETRINI FABRIZIO , VANNESCHI MARCO
Published: May 2003

The past few years have seen a rise in popularity of massively parallel architectures that use fat-trees as their interconnection networks. In this paper we formalize a parametric family of fat-trees, the k-ary n-trees, built with constant arity switches interconnected in a regular topology. A simple adaptive routing algorithm for k-ary n-trees sends each message to one of the nearest common ancestors of both source and destination, choosing the less loaded physical channels, and then reaches the destination following the unique available path. Through simulation on a 4-ary 4-tree with 256 nodes, we analyze some variants of the adaptive algorithm that utilize wormhole routing with 1, 2 and 4 virtual channels. The experimental results show that the uniform, bit reversal and transpose traffic patterns are very sensitive to the flow control strategy. In all these cases, the saturation points are between 35–40% of the network capacity with 1 virtual channel, 55–60% with 2 virtual channels and around 75% with 4 virtual channels. The complement traffic, a representative of the class of the congestion-free communication patterns, reaches an optimal performance, with a saturation point at 97% of the capacity for all flow control strategies. In this case virtual channels are of little help and the average network latency experiences an increase proportional to the number of virtual channels, due to the multiplexing of several packets onto the same physical links.
TOPOLOGICAL CONSTRAINTS FOR SENSE OF DIRECTION
Authors: FLOCCHINI PAOLA , SANTORO NICOLA
Published: May 2003

In a distributed system, each entity has a label (port number) associated to each of its neighbors. It is well known that if the labeling satisfies a global consistency property called Sense of Direction, the communication complexity of many distributed problem can be greatly reduced. This property is assumed to be present and it is implicitly used in most interconnection networks.

In this paper we investigate the nature of the relationship between Sense of Direction and network topology. We first consider the class of labelings which only satisfy the requirement of local orientation; that is, at each node, the outgoing edges have distinct labels. We then consider the class of labelings which also satisfy edge symmetry; that is, there exists a correlation between the labels neighbors give to their connecting edge. This class includes most of used labelings. We completely characterize the interplay between topological constraints and consistency constraints for these two classes of labelings. In fact, for each class, we identify both the set of forbidden subgraphs and the set of feasible graphs, and we show that the characterization is complete.
PERMUTATION ROUTING AND SORTING ON THE RECONFIGURABLE MESH
Authors: RAJASEKARAN SANGUTHEVAR , MCKENDALL THEODORE
Published: May 2003

In this paper we demonstrate the power of reconfiguration by presenting efficient randomized algorithms for both packet routing and sorting on a reconfigurable mesh connected computer. The run times of these algorithms are better than the best achievable time bounds on a conventional mesh. Many variations of the reconfigurable mesh can be found in the literature. We define yet another variation which we call as Mr. We also make use of the standard PARBUS model.

We show that permutation routing problem can be solved on a linear array Mr of size n in [Formula: see text] steps, whereas n-1 is the best possible run time without reconfiguration. A trivial lower bound for routing on Mr will be [Formula: see text]. On the PARBUS linear array, n is a lower bound and hence any standard n-step routing algorithm will be optimal.

We also show that permutation routing on an n×n reconfigurable mesh Mr can be done in time n+o(n) using a randomized algorithm or in time 1.25n+o(n) deterministically. In contrast, 2n-2 is the diameter of a conventional mesh and hence routing and sorting will need at least 2n-2 steps on a conventional mesh. A lower bound of [Formula: see text] is in effect for routing on the 2D mesh Mr as well. On the other hand, n is a lower bound for routing on the PARBUS and our algorithms have the same time bounds on the PARBUS as well. Thus our randomized routing algorithm is optimal upto a lower order term.

In addition we show that the problem of sorting can be solved in randomized time n+o(n) on Mr as well as on PARBUS. Clearly, this sorting algorithm will be optimal on the PARBUS model. The time bounds of our randomized algorithms hold with high probability.
AN EXTENDED DIMENSION ORDER TOKEN DISTRIBUTION ALGORITHM ON k-Ary d-CUBES AND ITS COMPLEXITY
Authors: DIDERICH CLAUDE G. , GENGLER MARC
Published: May 2003

Parallel programs that dynamically generate data generally need good load balancing algorithms. The token distribution problem is a generalization of the static load balancing problem. We solve this problem by an algorithm, called dimension order token distribution algorithm, designed for k-ary d-cube topologies. The algorithm is formally stated and proved correct. We analyze its message-passing and computational complexities and show that it is optimal. We also discuss generalizations of this algorithm, showing how the algorithm can be adapted so as to handle tokens of different kinds or so as to let the sender of a token know the destination of the migrating token.
TOPOLOGICAL PROPERTIES OF THE (n,k)-STAR GRAPH
Authors: CHIANG WEI-KUO , CHEN RONG-JAYE
Published: May 2003

The star graph, though an attractive alternative to the hypercube, has a major drawback in that the number of nodes for an n-star graph must be n!, and thus considerably limits the choice of the number of nodes in the graph. In order to alleviate this drawback, the arrangement graph was recently proposed as a generalization of the star graph topology. The arrangement graph provides more flexibility than the star graph in choosing the number of nodes, but the degree of the resulting network may be very high. To overcome that disadvantage, this paper presents another generalization of the star graph, called the (n,k)-star graph. We examine some topological properties of the (n,k)-star graph from the graph-theory point of view. It is shown that two different types of edges in the (n,k)-star prevent it from being edge-symmetric, but edges in each class are essentially symmetric with respect to each other. Also, the diameter and the exact average distance of the (n,k)-star graph are derived. In addition, the fault-diameter for the (n,k)-star graph is shown to be at most the fault-free diameter plus three.
NEW RESULTS ON COMPUTABILITY OF RECURRENCE EQUATIONS
Authors: VERGE HERVE LE , SAOUTER YANNICK
Published: May 2003

Systems of uniform recurrence equations were proposed by Karp et al.13 as a mean of automatically deriving programs for parallel architectures. Extensions of this formalism are used by many authors in systolic array synthesis. The computability of a system of recurrence equations is therefore of primary importance, and is considered as the first point to be examined when trying to implement an algorithm. This paper investigates the computability of recurrence equations and especially new results obtained in this area. We first recall the definitions of computability proposed by Karp et al.,13 Rao,31 Joinnault12 and Saouter et al.32 Then we correct and generalize those results. Finally, we give a new original proof for the undecidability of computability of non-uniform, non-conditional systems of recurrence equations.
RECOGNIZABLE AND LOGICALLY DEFINABLE LANGUAGES OF INFINITE COMPUTATIONS IN CONCURRENT AUTOMATA
Authors: DROSTE MANFRED , KUSKE DIETRICH
Published: May 2003

Automata with concurrency relations [Formula: see text], which occurred in formal verification methods of concurrent programs, are labeled transition systems with a collection of binary relations describing when two actions in a given state of the automaton can happen independently of each other. The concurrency monoid M($\mathcal{A}$) comprises all finite computation sequences of [Formula: see text], modulo a canonical congruence induced by the concurrency relations, with composition as monoid operation. Then M∞($\mathcal{A}$) denotes the set of all infinite products in M($\mathcal{A}$); its elements can be represented by labeled partially ordered sets. Under suitable assumptions on [Formula: see text], we show that a language L in M∞($\mathcal{A}$) is recognizable iff it is definable by a formula of monadic second order logic, and that it is recognizable iff it can be constructed from recognizable languages in M($\mathcal{A}$) using co-rational expressions. This generalizes various recent results in trace theory.
MINIMAL CONCEPT IDENTIFICATION AND RELIABILITY
Authors: JAIN SANJAY
Published: May 2003

Identification, by algorithmic devices, of grammars for languages from positive data is a well studied problem. In this paper we are mainly concerned about the learnability of indexed families of uniformly recursive languages. Mukouchi introduced the notion of minimal and reliable minimal concept inference from positive data. He left open a question about whether every indexed family of uniformly recursive languages that is minimally inferable is also reliably minimally inferable. We show that this is not the case.
THE SOUNDNESS OF EXPLICIT SUBSTITUTION WITH NAMELESS VARIABLES
Authors: KAMAREDDINE FAIROUZ
Published: May 2003

We show the soundness of a λ-calculus ℬ where de Bruijn indices are used, substitution is explicit, and reduction is step-wise. This is done by interpreting ℬ in the classical calculus where the explicit substitution becomes implicit and de Bruijn indices become named variables. This is the first flat semantics of explicit substitution and step-wise reduction and the first clear account of exactly when α-reduction is needed.
PROCESSOR LOWER BOUND FORMULAS FOR ARRAY COMPUTATIONS AND PARAMETRIC DIOPHANTINE SYSTEMS
Authors: CAPPELLO PETER , EĞECIOĞLU ÖMER
Published: May 2003

Using a directed acyclic graph (dag) model of algorithms, we solve a problem related to precedence-constrained multiprocessor schedules for array computations: Given a sequence of dags and linear schedules parametrized by n, compute a lower bound on the number of processors required by the schedule as a function of n. In our formulation, the number of tasks that are scheduled for execution during any fixed time step is the number of non-negative integer solutions dn to a set of parametric linear Diophantine equations. We present an algorithm based on generating functions for constructing a formula for these numbers dn. The algorithm has been implemented as a Mathematica program. Example runs and the symbolic formulas for processor lower bounds automatically produced by the algorithm for Matrix-Vector Product, Triangular Matrix Product, and Gaussian Elimination problems are presented. Our approach actually solves the following more general problem: Given an arbitrary r× s integral matrix A and r-dimensional integral vectors b and c, let dn(n=0,1,…) be the number of solutions in non-negative integers to the system Az=nb+c. Calculate the (rational) generating function ∑n≥ 0dntn and construct a formula for dn.
VERTEX SPLITTING IN DAGS AND APPLICATIONS TO PARTIAL SCAN DESIGNS AND LOSSY CIRCUITS
Authors: PAIK DOOWON , REDDY SUDHAKAR , SAHNI SARTAJ
Published: May 2003

Directed acyclic graphs (dags) are often used to model circuits. Path lengths in such dags represent circuit delays. In the vertex splitting problem, the objective is to determine a minimum number of vertices to split so that the resulting dag has no path of length > δ. This problem has application to the placement of flip-flops in partial scan designs, placement of latches in pipelined circuits, placement of signal boosters in lossy circuits and networks, etc. Several simplified versions of this problem are shown to be NP-hard. A linear time algorithm is obtained for the case when the dag is a tree. A backtracking algorithm and heuristics are developed for general dags and experimental results using dags obtained from ISCAS benchmark circuits are obtained.
SORT ORDER PROBLEMS IN RELATIONAL DATABASES
Authors: LARSEN KIM S.
Published: May 2003

A relation of degree k can be sorted lexicographically in k! different ways, i.e., according to any one of the possible permutations of the schema of the relation. Such permutations are referred to as sort orders. When evaluating unary and binary relational algebra operators using sort-merge algorithms, sort orders fulfilling the constraints enforced by the operators are chosen for the operand relations. The relations are then sorted according to their assigned sort orders, and the result is obtained by merging. Should the operands already be sorted according to one of the permissible sort orders, then only a merging is required. The sort order of the result will depend on the sort orders of the operands.

When evaluating whole relational algebra expressions, the result of one operation will be used as an operand to the next. It is desirable to choose sort orders in such a way that the result of one operation will automatically fulfill the requirements of the next. In general, one would like to find a minimal number of operators in the expression for which this cannot be obtained, bearing in mind the overall goal of minimizing the total work.

We show that this problem is NP-hard, and that the corresponding decision problem is NP-complete. However, most simplifications of the original problem give rise to efficient algorithms. In fact, most frequently occurring queries can be analyzed in linear time in the size of the query. This is due to the fact that only a very limited number of subsets of all permutations of schemas can be encountered in the algorithms, which means that compact representations for these subsets can be found.
ON THE CONSERVATIVITY OF LEIBNIZ EQUALITY
Authors: SELLINK M. P. A.
Published: May 2003

We embed a first order theory with equality in the Pure Type System λMON2 that is a subsystem of the well-known type system λPRED2. The embedding is based on the Curry-Howard isomorphism, i.e. → and ∀ coincide with → and Π. Formulas of the form [Formula: see text] are treated as Leibniz equalities. That is, [Formula: see text] is identified with the second order formula ∀ P. P(t1)→ P(t2), which contains only →'s and ∀'s and can hence be embedded straightforwardly. We give a syntactic proof — based on enriching typed λ-calculus with extra reduction steps — for the equivalence between derivability in the logic and inhabitance in λMNO2. Familiarity with Pure Type Systems is assumed.
FEEDFORWARD NEURAL NETWORK WITH ADAPTIVE REFERENCE PATTERN LAYER
Authors: LEHTOKANGAS MIKKO
Published: May 2003

A hybrid neural network architecture is investigated for modeling purposes. The proposed hybrid is based on the multilayer perceptron (MLP) network. In addition to the usual hidden layers, the first hidden layer is selected to be an adaptive reference pattern layer. Each unit in this new layer incorporates a reference pattern that is located somewhere in the space spanned by the input variables. The outputs of these units are the component wise-squared differences between the elements of a reference pattern and the inputs. The reference pattern layer has some resemblance to the hidden layer of the radial basis function (RBF) networks. Therefore the proposed design can be regarded as a sort of hybrid of MLP and RBF networks. The presented benchmark experiments show that the proposed hybrid can provide significant advantages over standard MLPs and RBFs in terms of fast and efficient learning, and compact network structure.
NEURAL NETWORKS AND LINEAR PROGRAMMING FOR THE SATISFIABILITY PROBLEM
Authors: MONFROGLIO ANGELO
Published: May 2003

First a Linear Programming formulation is considered for the satisfiability problem, in particular for the satisfaction of a Conjunctive Normal Form in the Propositional Calculus and the Simplex algorithm for solving the optimization problem. The use of Recurrent Neural Networks is then described for choosing the best pivot positions and greatly improving the algorithm performance. The result of hard cases testing is reported and shows that the technique can be useful even if it requires a huge amount of size for the constraint array and Neural Network Data Input.
SOLVING LINEAR INTEGER PROGRAMMING PROBLEMS BY A NOVEL NEURAL MODEL
Authors: CAVALIERI S.
Published: May 2003

The paper deals with integer linear programming problems. As is well known, these are extremely complex problems, even when the number of integer variables is quite low. Literature provides examples of various methods to solve such problems, some of which are of a heuristic nature. This paper proposes an alternative strategy based on the Hopfield neural network. The advantage of the strategy essentially lies in the fact that hardware implementation of the neural model allows for the time required to obtain a solution so as not depend on the size of the problem to be solved. The paper presents a particular class of integer linear programming problems, including well-known problems such as the Travelling Salesman Problem and the Set Covering Problem. After a brief description of this class of problems, it is demonstrated that the original Hopfield model is incapable of supplying valid solutions. This is attributed to the presence of constant bias currents in the dynamic of the neural model. A demonstration of this is given and then a novel neural model is presented which continues to be based on the same architecture as the Hopfield model, but introduces modifications thanks to which the integer linear programming problems presented can be solved. Some numerical examples and concluding remarks highlight the solving capacity of the novel neural model.
A MEMORY-BASED SELF-GENERATED BASIS FUNCTION NEURAL NETWORK
Authors: LIN CHUN-SHIN , LI CHIEN-KUO
Published: May 2003

The paper presents a novel memory-based Self-Generated Basis Function Neural Network (SGBFN) that is composed of small CMACs. The SGBFN requires much smaller memory space than the conventional CMAC and has an excellent learning convergence property compared to multilayer neural networks. Each CMAC in the new structure takes a subset of problem inputs as its inputs. Several CMACs that have different subsets of inputs form a submodule and a group of submodules form a neural network. The output of a submodule is the product of its CMACs' outputs. Each submodule implements a self-generated basis function, which is developed during the learning. The output of the neural network is the sum of the outputs from the submodules. Using only a subset of inputs in each CMAC significantly reduces the required memory space in high-dimensional modeling. With the same size of memory, the new structure is able to achieve a much smaller learning error compared to the conventional CMAC.
SYNCHRONOUS AND ASYNCHRONOUS BRAIN-STATE-IN-A-BOX INFORMATION SYSTEM NEURAL MODELS
Authors: CHAN HUBERT Y. , HUI STEFEN , ŻAK STANISLAW H.
Published: May 2003

Synchronous and asynchronous information system neural models are proposed that are hybrids of Pawlak's information system and Brain-State-in-a-Box (BSB) neural models. The stability of the proposed models is studied using LaSalle's Invariance Principle. Applications to an analysis of the United Nations activities are presented as examples.
PARTIAL RETRAINING: A NEW APPROACH TO INPUT RELEVANCE DETERMINATION
Authors: LAAR PIËRRE VAN DE , HESKES TOM , GIELEN STAN
Published: May 2003

In this article we introduce partial retraining, an algorithm to determine the relevance of the input variables of a trained neural network. We place this algorithm in the context of other approaches to relevance determination. Numerical experiments on both artificial and real-world problems show that partial retraining outperforms its competitors, which include methods based on constant substitution, analysis of weight magnitudes, and "optimal brain surgeon".
A NEURAL NETWORK METHODOLOGY OF QUADRATIC OPTIMIZATION
Authors: WU AI , TAM P. K. S.
Published: May 2003

According to the basic optimization principle of artificial neural networks, a novel kind of neural network model for solving the quadratic programming problem is presented. The methodology is based on the Lagrange multiplier theory in optimization and seeks to provide solutions satisfying the necessary conditions of optimality. The equilibrium point of the network satisfies the Kuhn-Tucker condition for the problem. The stability and convergency of the neural network is investigated and the strategy of the neural optimization is discussed. The feasibility of the neural network method is verified with the computation examples. Results of the simulation of the neural network to solve optimum problems are presented to illustrate the computational power of the neural network method.
ASYMPTOTIC HYPERSTABILITY OF A CLASS OF NEURAL NETWORKS
Authors: MEYER-BÄSE ANKE
Published: May 2003

This paper is concerned with the asymptotic hyperstability of recurrent neural networks. We derive based on the stability results necessary and sufficient conditions for the network parameters. The results we achieve are more general than those based on Lyapunov methods, since they provide milder constraints on the connection weights than the conventional results and do not suppose symmetry of the weights.
AN EXPERIMENTAL COMPARISON OF NEURAL ALGORITHMS FOR INDEPENDENT COMPONENT ANALYSIS AND BLIND SEPARATION
Authors: GIANNAKOPOULOS XAVIER , KARHUNEN JUHA , OJA ERKKI
Published: May 2003

In this paper, we compare the performance of five prominent neural or adaptive algorithms designed for Independent Component Analysis (ICA) and blind source separation (BSS). In the first part of the study, we use artificial data for comparing the accuracy, convergence speed, computational load, and other relevant properties of the algorithms. In the second part, the algorithms are applied to three different real-world data sets. The task is either blind source separation or finding interesting directions in the data for visualisation purposes. We develop criteria for selecting the most meaningful basis vectors of ICA and measuring the quality of the results. The comparison reveals characteristic differences between the studied ICA algorithms. The most important conclusions of our comparison are robustness of the ICA algorithms with respect to modest modeling imperfections, and the superiority of fixed-point algorithms with respect to the computational load.
COLOR IMAGE CORRECTION FOR SCANNER AND PRINTER USING B-SPLINE CMAC NEURAL NETWORKS
Authors: CHANG PO-RONG
Published: May 2003

The process of eliminating the color errors from the gamut mismatch, resolution conversion, and nonlinearity between scanner and printer is usually recognized as an essential issue of color reproduction. This paper presents a new formulation based on the generalized inverse plant control for the color error reduction process. In our formulation, the printer input and scanner output correspond to the input and output of a system plant, respectively. Obviously, if the printer input equals the scanner output, then there are no color errors involved in the entire system. In other words, the plant becomes an identity system. To achieve this goal, a plant generalized inverse should be identified and added to the original system. Since the system of a combination of both scanner and printer is highly nonlinear, CMAC-based neural networks, which have the capability to learn arbitrary nonlinearity, are applied to identify the plant generalized inverse. CMAC network is a perceptron-like feedforward structure with associative memory properties. Its memory requirements can be greatly reduced by the use of hash coding techniques. In order for CMAC networks to construct high-order, smooth, nonlinear plant inverse, more general CMAC addressing schemes have been proposed in conjunction with use of B-spline receptive functions. It is shown that B-spline CMAC networks learn orders of magnitude more rapidly than typical implementations of back propagation in the multilayered neural networks, due to the local nature of its weighting updating and the finite support of B-spline receptive field functions. Finally, a number of test samples are conducted to verify the effectiveness of the proposed method.
MODULAR NEURAL NETWORKS: A SURVEY
Authors: AUDA GASSER , KAMEL MOHAMED
Published: May 2003

Modular Neural Networks (MNNs) is a rapidly growing field in artificial Neural Networks (NNs) research. This paper surveys the different motivations for creating MNNs: biological, psychological, hardware, and computational. Then, the general stages of MNN design are outlined and surveyed as well, viz., task decomposition techniques, learning schemes and multi-module decision-making strategies. Advantages and disadvantages of the surveyed methods are pointed out, and an assessment with respect to practical potential is provided. Finally, some general recommendations for future designs are presented.
RECOGNITION OF SEED VARIETIES USING A TEMPORAL ORGANISATION MAP ANALYSIS OF ELECTROPHORETIC IMAGES
Authors: JEDRA M. , KHATTABI N. EL , LIMOURI M. , ESSAID A.
Published: May 2003

This paper presents a method for seed varieties recognition using one-dimensional electrophoresis gels. It employs a neural network basically constituted of temporal organisation maps (TOM). The TOM model is a neural net which was initially developed for speech recognition. It can be trained to recognise words in speech by reference to the sound pattern over a sequence of time steps. Electrophoresis creates a set of bands in the gel, caused by migration of protein from the seed. Each seed variety generates a characteristic pattern. The bands are made visible by staining. They can then be imaged and digitised to create an input to a TOM, which treats the variation with distance along the lane in the same way as the time sequence for which it was originally employed. In this way the characteristic signature of a seed variety can be recognised.

A set of 50 images — each containing 10 to 15 lanes — was used to train and test the performance of a neural network in recognising 75 cereal varieties. The network could achieve a recognition rate of 98%, provided that the gel was not distorted or cracked during heating or drying.

Details of the design and training of the network are given.
Improving the Discriminatory Capabilities of a Neural Classifier by Using a Biased-Wavelet Layer
Authors: GALVÃO ROBERTO KAWAKAMI HARROP , YONEYAMA TAKASHI
Published: May 2003

In the context of wavelet neural networks (WNN's), two modifications to the basic training algorithms are proposed, namely the introduction of a bias component in the wavelets and the adoption of a weight decay policy. A problem of ECG segment classification is used for illustration purposes. Results suggest that bias improves the discriminatory capabilities of the WNN, which is also compared favourably to a conventional perceptron classifier. The use of weight decay during training, followed by pruning, resulted in a more parsimonious network, which also turned out to be a more conservative classifier. The knowledge embedded in the wavelet layer is interpreted with basis on the concept of super-wavelets.
Thermodynamics Energy for Both Supervised and Unsupervised Learning Neural Nets at a Constant Temperature
Authors: SZU HAROLD
Published: May 2003

Unified Lyaponov function is given for the first time to prove the learning methodologies convergence of artificial neural network (ANN), both supervised and unsupervised, from the viewpoint of the minimization of the Helmholtz free energy at the constant temperature. Early in 1982, Hopfield has proven the supervised learning by the energy minimization principle. Recently in 1996, Bell & Sejnowski has algorithmically demonstrated. Independent Component Analyses (ICA) generalizing the Principal Component Analyses (PCA) that the continuing reduction of early vision redundancy happens towards the "sparse edge maps" by maximization of the ANN output entropy. We explore the combination of both as Lyaponov function of which the proven convergence gives both learning methodologies. The unification is possible because of the thermodynamics Helmholtz free energy at a constant temperature. The blind de-mixing condition for more than two objects using two sensor measurement. We design two smart cameras with short term working memory to do better image de-mixing of more than two objects. We consider channel communication application that we can efficiently mix four images using matrices [AO] and [Al] to send through two channels.
Neural Networks Learning With Sliding Mode Control: The Sliding Mode Backpropagation Algorithm
Authors: PARMA GUSTAVO G. , MENEZES BENJAMIN R. DE , BRAGA ANTÔNIO P.
Published: May 2003

Based on the classical backpropagation weight update equations, sliding mode control theory is introduced as a technique to adapt weights of a multi-layer perceptron. As will be demonstrated, the introduction of sliding mode has resulted in a much faster version of the standard backpropagation. The results show also that the proposed algorithm presents some important features of sliding mode control, which are robustness and high speed of learning. In addition to that, this paper shows also how control theory can be applied to train neural networks
Estimating the Number of Clusters in Multivariate Data by Self-Organizing Maps
Authors: COSTA JOSÉ ALFREDO FERREIRA , NETTO MÁRCIO LUIZ DE ANDRADE
Published: May 2003

Determining the structure of data without prior knowledge of the number of clusters or any information about their composition is a problem of interest in many fields, such as image analysis, astrophysics, biology, etc. Partitioning a set of n patterns in a p-dimensional feature space must be done such that those in a given cluster are more similar to each other than the rest. As there are approximately [Formula: see text] possible ways of partitioning the patterns among K clusters, finding the best solution is very hard when n is large. The search space is increased when we have no a priori number of partitions. Although the self-organizing feature map (SOM) can be used to visualize clusters, the automation of knowledge discovery by SOM is a difficult task. This paper proposes region-based image processing methods to post-processing the U-matrix obtained after the unsupervised learning performed by SOM. Mathematical morphology is applied to identify regions of neurons that are similar. The number of regions and their labels are automatically found and they are related to the number of clusters in a multivariate data set. New data can be classified by labeling it according to the best match neuron. Simulations using data sets drawn from finite mixtures of p-variate normal densities are presented as well as related advantages and drawbacks of the method.
Sequential RAM-based Neural Networks: Learnability, Generalisation, Knowledge Extraction, And Grammatical Inference
Authors: SOUTO MARCÍLIO C.P.DE , ADEODATO PAULO J. L. , LUDERMIR TERESA B.
Published: May 2003

A fundamental question in the field of artificial neural networks is what set of problems a given class of networks can perform (computability). Such a problem can be made less general, but no less important, by asking what these networks could learn by using a given training procedure (learnability). The basic purpose of this paper is to address the learnability problem. Specifically, it analyses the learnability of sequential RAM-based neural networks. The analytical tools used are those of Automata Theory. In this context, this paper establishes which class of problems and under what conditions such networks, together with their existing learning rules, can learn and generalise. This analysis also yields techniques for both extracting knowledge from and inserting knowledge into the networks. The results presented here, besides helping in a better understanding of the temporal behaviour of sequential RAM-based networks, could also provide useful insights for the integration of the symbolic/connectionist paradigms.