Learning Automata from Ordered Examples

Connectionist learning models have had considerable empirical success, but it is hard to characterize exactly what they learn. The learning of finite-state languages (FSL) from example strings is a domain which has been extensively studied and might provide an opportunity to help understand connectionist learning. A major problem is that traditional FSL learning assumes the storage of all examples and thus violates connectionist principles. This paper presents a provably correct algorithm for inferring any minimum-state deterministic finite-state automata (FSA) from a complete ordered sample using limited total storage and without storing example strings. The algorithm is an iterative strategy that uses at each stage a current encoding of the data considered so far, and one single sample string. One of the crucial advantages of our algorithm is that the total amount of space used in the course of learning for encoding any finite prefix of the sample is polynomial in the size of the inferred minimum state deterministic FSA. The algorithm is also relatively efficient in time and has been implemented. More importantly, there is a connectionist version of the algorithm that preserves these properties. The connectionist version requires much more structure than the usual models and has been implemented using the Rochester Connectionist Simulator. We also show that no machine with finite working storage can iteratively identify the FSL from arbitrary presentations.     

Performance analysis of a class of transient detection algorithms-aunified framework

The detection of short-duration nonstationary signals, which are commonly referred to as transients, is often performed in the time-frequency-transform domain. An analytical framework within which the performance of different detectors based on linear transforms can be easily compared, for different classes of signals, is developed. A given class of transients is modeled as a signal existing in a linear subspace, plus a mismatch signal. Closed-form expressions are derived for the best and the worst detection performance for all possible transients in a given class. Using this framework, the performance of detectors based on the Gabor transform and on the short-time Fourier transform is evaluated and compared     

Estimation of frequency in the presence of nonrandom interference

This paper develops a method of error analysis for Fourier transform-based sinusoidal frequency estimation in the presence of nonrandom interferences. A general error formula is derived and then specialized to the cases of additive and multiplicative interferences. Approximate error formulas are derived for the case of additive polynomial-phase interference. Finally, an application to error analysis in estimating the parameters of multiple polynomial-phase signals is discussed in detail     

Efficient pebbling for list traversal synopses with application to program rollback

We show how to support efficient back traversal in a unidirectional list, using small memory and with essentially no slowdown in forward steps. Using O(lgn)$O(lgn)$ memory for a list of size n$n$, the i$i$’th back-step from the farthest point reached so far takes O(lgi)$O(lgi)$ time in the worst case, while the overhead per forward step is at most ?$?$ for arbitrary small constant ?>0$?>0$. An arbitrary sequence of forward and back steps is allowed. A full trade-off between memory usage and time per back-step is presented: k$k$ vs. kn^1/k$k{n}^{1/k}$ and vice versa. Our algorithms are based on a novel pebbling technique which moves pebbles on a virtual binary, or n^1/k$n^{1/k}$-ary, tree that can only be traversed in a pre-order fashion.     

The interaction between molten gallium and the hydrocarbon medium induced by ultrasonic energy—can gallium carbide be formed?

Ultrasonic irradiation of molten gallium in organic liquids (decane, dodecane, etc.) results in dispersion of the gallium into nanometric spheres. These were examined by several analytical methods XRD, DSC, Raman and IR spectroscopy) as well as electron microscopy (SEM, TEM) and found to be composed of Ga and C. The DSC analysis indicates that the Ga has possibly reacted with carbon, while the Raman spectrum of the product demonstrates a strong additional peak that could not be identified. This work explores the possibility that the product is gallium carbide or another gallium‐carbon complex. To investigate the nature of the product, we performed detailed extended X‐ray absorption fine structure (EXAFS) and X‐ray absorption near‐edge structure (XANES) analyses. On the basis of DSC, IR, and Raman it appear to be formation of GaC, whereas the analysis by EXAFS and XANES demonstrated that the gallium is found to be in a higher reduced state (almost metallic), supported by carbon. The question that remains open in addition to the one related to the formation of galium carbide is whether a complex structure, including oxygen contamination is involved in the layers surrounding the Ga as indicated by the EXAFS results.