Contributions to the Theory of Finite-State Based Grammars

This dissertation is a theoretical study of finite-state based grammars used in natural language processing. The study is concerned with certain varieties of finite-state intersection grammars (FSIG) whose parsers define regular relations between surface strings and annotated surface strings. The study focuses on the following three aspects of FSIGs: (i) Computational complexity of grammars under limiting parameters In the study, the computational complexity in practical natural language processing is approached through performance-motivated parameters on structural complexity. Each parameter splits some grammars in the Chomsky hierarchy into an infinite set of subset approximations. When the approximations are regular, they seem to fall into the logarithmic-time hierarchyand the dot-depth hierarchy of star-free regular languages. This theoretical result is important and possibly relevant to grammar induction. (ii) Linguistically applicable structural representations Related to the linguistically applicable representations of syntactic entities, the study contains new bracketing schemes that cope with dependency links, left- and right branching, crossing dependencies and spurious ambiguity. New grammar representations that resemble the Chomsky-Schützenberger representation of context-free languages are presented in the study, and they include, in particular, representations for mildly context-sensitive non-projective dependency grammars whose performance-motivated approximations are linear time parseable. (iii) Compilation and simplification of linguistic constraints Efficient compilation methods for certain regular operations such as generalized restriction are presented. These include an elegant algorithm that has already been adopted as the approach in a proprietary finite-state tool. In addition to the compilation methods, an approach to on-the-fly simplifications of finite-state representations for parse forests is sketched. These findings are tightly coupled with each other under the theme of locality. I argue that the findings help us to develop better, linguistically oriented formalisms for finite-state parsing and to develop more efficient parsers for natural language processing. Avainsanat: syntactic parsing, finite-state automata, dependency grammar, first-order logic, linguistic performance, star-free regular approximations, mildly context-sensitive grammars

Approximate solutions of Fredholm integral equations of the second kind

This note is concerned with the problem of determining approximate solutions of Fredholm integral equations of the second kind. Approximating the solution of a given integral equation by means of a polynomial, an over-determined system of linear algebraic equations is obtained involving the unknown coefficients, which is finally solved by using the least-squares method. Several examples are examined in detail. (c) 2009 Elsevier Inc. All rights reserved.

On the direct parallel solution of systems of linear equations: New algorithms and systolic structures

The paper presents two new algorithms for the direct parallel solution of systems of linear equations. The algorithms employ a novel recursive doubling technique to obtain solutions to an nth-order system in n steps with no more than 2n(n −1) processors. Comparing their performance with the Gaussian elimination algorithm (GE), we show that they are almost 100% faster than the latter. This speedup is achieved by dispensing with all the computation involved in the back-substitution phase of GE. It is also shown that the new algorithms exhibit error characteristics which are superior to GE. An n(n + 1) systolic array structure is proposed for the implementation of the new algorithms. We show that complete solutions can be obtained, through these single-phase solution methods, in 5n−log2n−4 computational steps, without the need for intermediate I/O operations.

A comment on the consistency of truncated nonlinear integral equation based theories of freezing

We report the results of two studies of aspects of the consistency of truncated nonlinear integral equation based theories of freezing: (i) We show that the self-consistent solutions to these nonlinear equations are unfortunately sensitive to the level of truncation. For the hard sphere system, if the Wertheim–Thiele representation of the pair direct correlation function is used, the inclusion of part but not all of the triplet direct correlation function contribution, as has been common, worsens the predictions considerably. We also show that the convergence of the solutions found, with respect to number of reciprocal lattice vectors kept in the Fourier expansion of the crystal singlet density, is slow. These conclusions imply great sensitivity to the quality of the pair direct correlation function employed in the theory. (ii) We show the direct correlation function based and the pair correlation function based theories of freezing can be cast into a form which requires solution of isomorphous nonlinear integral equations. However, in the pair correlation function theory the usual neglect of the influence of inhomogeneity of the density distribution on the pair correlation function is shown to be inconsistent to the lowest order in the change of density on freezing, and to lead to erroneous predictions. The Journal of Chemical Physics is copyrighted by The American Institute of Physics.

A generalized estimating equations approach for analysis of the impact of new technology on a trawl fishery

The article describes a generalized estimating equations approach that was used to investigate the impact of technology on vessel performance in a trawl fishery during 1988-96, while accounting for spatial and temporal correlations in the catch-effort data. Robust estimation of parameters in the presence of several levels of clustering depended more on the choice of cluster definition than on the choice of correlation structure within the cluster. Models with smaller cluster sizes produced stable results, while models with larger cluster sizes, that may have had complex within-cluster correlation structures and that had within-cluster covariates, produced estimates sensitive to the correlation structure. The preferred model arising from this dataset assumed that catches from a vessel were correlated in the same years and the same areas, but independent in different years and areas. The model that assumed catches from a vessel were correlated in all years and areas, equivalent to a random effects term for vessel, produced spurious results. This was an unexpected finding that highlighted the need to adopt a systematic strategy for modelling. The article proposes a modelling strategy of selecting the best cluster definition first, and the working correlation structure (within clusters) second. The article discusses the selection and interpretation of the model in the light of background knowledge of the data and utility of the model, and the potential for this modelling approach to apply in similar statistical situations.

Estimating equations with nonignorably missing response data

Troxel, Lipsitz, and Brennan (1997, Biometrics 53, 857-869) considered parameter estimation from survey data with nonignorable nonresponse and proposed weighted estimating equations to remove the biases in the complete-case analysis that ignores missing observations. This paper suggests two alternative modifications for unbiased estimation of regression parameters when a binary outcome is potentially observed at successive time points. The weighting approach of Robins, Rotnitzky, and Zhao (1995, Journal of the American Statistical Association 90, 106-121) is also modified to obtain unbiased estimating functions. The suggested estimating functions are unbiased only when the missingness probability is correctly specified, and misspecification of the missingness model will result in biases in the estimates. Simulation studies are carried out to assess the performance of different methods when the covariate is binary or normal. For the simulation models used, the relative efficiency of the two new methods to the weighting methods is about 3.0 for the slope parameter and about 2.0 for the intercept parameter when the covariate is continuous and the missingness probability is correctly specified. All methods produce substantial biases in the estimates when the missingness model is misspecified or underspecified. Analysis of data from a medical survey illustrates the use and possible differences of these estimating functions.

Estimating equations for parameters in stochastic growth models from tag-recapture data

James (1991, Biometrics 47, 1519-1530) constructed unbiased estimating functions for estimating the two parameters in the von Bertalanffy growth curve from tag-recapture data. This paper provides unbiased estimating functions for a class of growth models that incorporate stochastic components and explanatory variables. a simulation study using seasonal growth models indicates that the proposed method works well while the least-squares methods that are commonly used in the literature may produce substantially biased estimates. The proposed model and method are also applied to real data from tagged rack lobsters to assess the possible seasonal effect on growth.

Estimating equations for removal data analysis

We consider the problem of estimating a population size from successive catches taken during a removal experiment and propose two estimating functions approaches, the traditional quasi-likelihood (TQL) approach for dependent observations and the conditional quasi-likelihood (CQL) approach using the conditional mean and conditional variance of the catch given previous catches. Asymptotic covariance of the estimates and the relationship between the two methods are derived. Simulation results and application to the catch data from smallmouth bass show that the proposed estimating functions perform better than other existing methods, especially in the presence of overdispersion.

Transient state work fluctuation theorem for a classical harmonic oscillator linearly coupled to a harmonic bath

Based on a Hamiltonian description we present a rigorous derivation of the transient state work fluctuation theorem and the Jarzynski equality for a classical harmonic oscillator linearly coupled to a harmonic heat bath, which is dragged by an external agent. Coupling with the bath makes the dynamics dissipative. Since we do not assume anything about the spectral nature of the harmonic bath the derivation is not restricted only to the Ohmic bath, rather it is more general, for a non-Ohmic bath. We also derive expressions of the average work done and the variance of the work done in terms of the two-time correlation function of the fluctuations of the position of the harmonic oscillator. In the case of an Ohmic bath, we use these relations to evaluate the average work done and the variance of the work done analytically and verify the transient state work fluctuation theorem quantitatively. Actually these relations have far-reaching consequences. They can be used to numerically evaluate the average work done and the variance of the work done in the case of a non-Ohmic bath when analytical evaluation is not possible.

Structure of the noncubic phase in the ferroelectric state of Pr-substituted SrTiO3

Sr1−xPrxTiO3 has recently been shown to exhibit ferroelectricity at room temperature. In this paper powder x-ray and neutron-diffraction patterns of this system at room temperature have been analyzed to show that the system exhibits cubic (Pm-3m) structure for x<=0.05 and tetragonal (I4/mcm) for x>0.05. The redundancy of the noncentrosymmetric structural model (I4cm) in the ferroelectric state suggests the absence of long-range ordered ferroelectric domains and supports the relaxor ferroelectric model for this system.

Nanopatterning by solid-state dewetting on reconstructed ceramic surfaces

We demonstrate ordered array formation of Au nanoparticles by controlled solid-state dewetting of a metal film on stepped alumina substrates. In situ transmission electron microscopy studies reveal that the dewetting process starts with nucleation of ordered dry regions on the substrate. The chemical potential difference between concave and convex surface regions induces anisotropic metal diffusion leading to the formation of nanowires in the valleys. The nanowires fragment due to Rayleigh instability forming arrays of metal nanoparticles on the substrate. The length scale of reconstruction relative to the starting film thickness is an important parameter in controlling the spatial order of the nanoparticles.

Reversible photodimerization of phenylbutadienes in the solid state

Based on x-ray crystallographic studies, it is shown that crystal chemical factors govern the reversible photodimerization of phenylbutadienes in the solid state.

Solid-state Thermal Polymerization of Sodium Acrylate

Initiation and propagation processes in thermally initiated solid-state polymerization of sodiumvacrylate have been studied. The kinetics of initiation, followed with the electron spin resonancev technique, leads to an activation energy E of 28.8 kcal/mol, which is attributed to the formation of dimeric radicals. The activation energy of 16 f 1 kcaVmol obtained for the solid-state polymerization of sodium acrylate by chemical analysis and differential scanning calorimetry has been attributed to the propagation process.

Calorimetric, infrared and ESR studies of the plastically crystalline state of organic compounds

Enthalpy changes of the crystal-plastic and plastic-liquid transitions are related to the temperature range of stability of the plastic phase. Thermodynamics of the plastic state of binary mixtures have been examined. Infrared correlation times, τc, and activation energies have been measured for a few molecules in the plastic state. Molecular tumbling times, τt, have also been measured employing ESR spectra of a spin-probe. Plots of log τc(τt) 1/T are continuous through the plastic-liquid transition. Activation energies for molecular motion seem to vary in the same direction as the ΔH of the plastic-crystal transition. Infrared correlation times of solute molecules in binary solutions in the plastic and the liquid states show interesting variations with solute concentration.