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

Non-Fermi liquid theory of quantum hall effects

Within the Grassmannian U(2N)/U(N) x U(N) nonlinear sigma-model representation of localization, one can study the low-energy dynamics of both a free and interacting electron gas. We study the crossover between these two fundamentally different physical problems. We show how the topological arguments for the exact quantization of the Hall conductance are extended to include the Coulomb interaction problem. We discuss dynamical scaling and make contact with the theory of variable range hopping. (C) 2005 Pleiades Publishing, Inc.

Studies of the representation of interatomic distances in molecules and crystal as sum of atomic radii

The electron diffraction investigation of the following compounds has been carried out: sulfur, sulfur nitride, realgar, arsenic trisulfide, spiropentane, dimethyltrisulfide, cis and trans lewisite, methylal, and ethylene glycol.

The crystal structures of the following salts have been determined by x-ray diffraction: silver molybdateand hydrazinium dichloride.

Suggested revisions of the covalent radii for B, Si, P, Ge, As, Sn, Sb, and Pb have been made, and values for the covalent radii of Al, Ga, In, Ti, and Bi have been proposed.

The Schomaker-Stevenson revision of the additivity rule for single covalent bond distances has been used in conjunction with the revised radii. Agreement with experiment is in general better with the revised radii than with the former radii and additivity.

The principle of ionic bond character in addition to that present in a normal covalent bond has been applied to the observed structures of numerous molecules. It leads to a method of interpretation which is at least as consistent as the theory of multiple bond formation.

The revision of the additivity rule has been extended to double bonds. An encouraging beginning along these lines has been made, but additional experimental data are needed for clarification.

The complex angular momentum theory of the production of three particles in collisions of two strongly interacting particles at high energy

The problem of the continuation to complex values of the angular momentum of the partial wave amplitude is examined for the simplest production process, that of two particles → three particles. The presence of so-called "anomalous singularities" complicates the procedure followed relative to that used for quasi two-body scattering amplitudes. The anomalous singularities are shown to lead to exchange degenerate amplitudes with possible poles in much the same way as "normal" singularities lead to the usual signatured amplitudes. The resulting exchange-degenerate trajectories would also be expected to occur in two-body amplitudes.

The representation of the production amplitude in terms of the singularities of the partial wave amplitude is then developed and applied to the high energy region, with attention being paid to the emergence of "double Regge" terms. Certain new results are obtained for the behavior of the amplitude at zero momentum transfer, and some predictions of polarization and minima in momentum transfer distributions are made. A calculation of the polarization of the ρ^o meson in the reaction π ^- p → π ^- ρ^op at high energy with small momentum transfer to the proton is compared with data taken at 25 Gev by W. D. Walker and collaborators. The result is favorable, although limited by the statistics of the available data.

Theory of high-power mode-locked lasers with a slow absorber

We develop an analytical theory of high-power passively mode-locked lasers with a slow absorber; the theory is valid at pulse energies well exceeding the saturation energy. We analyze the Haus modelocking master equation in the pulse-energy-domain representation, approximating the intensity profile function by a series in the vicinity of its peak value. We consider the high-power operation regime of subpicosecond blue-violet GaN mode-locked diode lasers, using the approach developed. © 2010 Springer Science+Business Media, Inc.

A Theory of Networks for Appxoimation and Learning

Learning an input-output mapping from a set of examples, of the type that many neural networks have been constructed to perform, can be regarded as synthesizing an approximation of a multi-dimensional function, that is solving the problem of hypersurface reconstruction. From this point of view, this form of learning is closely related to classical approximation techniques, such as generalized splines and regularization theory. This paper considers the problems of an exact representation and, in more detail, of the approximation of linear and nolinear mappings in terms of simpler functions of fewer variables. Kolmogorov's theorem concerning the representation of functions of several variables in terms of functions of one variable turns out to be almost irrelevant in the context of networks for learning. We develop a theoretical framework for approximation based on regularization techniques that leads to a class of three-layer networks that we call Generalized Radial Basis Functions (GRBF), since they are mathematically related to the well-known Radial Basis Functions, mainly used for strict interpolation tasks. GRBF networks are not only equivalent to generalized splines, but are also closely related to pattern recognition methods such as Parzen windows and potential functions and to several neural network algorithms, such as Kanerva's associative memory, backpropagation and Kohonen's topology preserving map. They also have an interesting interpretation in terms of prototypes that are synthesized and optimally combined during the learning stage. The paper introduces several extensions and applications of the technique and discusses intriguing analogies with neurobiological data.

Tense, Aspect and the Cognitive Representation of Time

This paper explores the relationships between a computation theory of temporal representation (as developed by James Allen) and a formal linguistic theory of tense (as developed by Norbert Hornstein) and aspect. It aims to provide explicit answers to four fundamental questions: (1) what is the computational justification for the primitive of a linguistic theory; (2) what is the computational explanation of the formal grammatical constraints; (3) what are the processing constraints imposed on the learnability and markedness of these theoretical constructs; and (4) what are the constraints that a linguistic theory imposes on representations. We show that one can effectively exploit the interface between the language faculty and the cognitive faculties by using linguistic constraints to determine restrictions on the cognitive representation and vice versa. Three main results are obtained: (1) We derive an explanation of an observed grammatical constraint on tense?? Linear Order Constraint??m the information monotonicity property of the constraint propagation algorithm of Allen's temporal system: (2) We formulate a principle of markedness for the basic tense structures based on the computational efficiency of the temporal representations; and (3) We show Allen's interval-based temporal system is not arbitrary, but it can be used to explain independently motivated linguistic constraints on tense and aspect interpretations. We also claim that the methodology of research developed in this study??oss-level" investigation of independently motivated formal grammatical theory and computational models??a powerful paradigm with which to attack representational problems in basic cognitive domains, e.g., space, time, causality, etc.

Towards a Computational Theory of Definite Anaphora Comprehension in English Discourse

This report investigates the process of focussing as a description and explanation of the comprehension of certain anaphoric expressions in English discourse. The investigation centers on the interpretation of definite anaphora, that is, on the personal pronouns, and noun phrases used with a definite article the, this or that. Focussing is formalized as a process in which a speaker centers attention on a particular aspect of the discourse. An algorithmic description specifies what the speaker can focus on and how the speaker may change the focus of the discourse as the discourse unfolds. The algorithm allows for a simple focussing mechanism to be constructed: and element in focus, an ordered collection of alternate foci, and a stack of old foci. The data structure for the element in focus is a representation which encodes a limted set of associations between it and other elements from teh discourse as well as from general knowledge.

Analysis of Sequence Periodicity in E. coli Proteins: Empirical Investigation of the ?Duplication and Divergence? Theory of Protein Evolution

Gatherer, D., and McEwan, N.R. (2003). Analysis of sequence periodicity in E. coli proteins: empirical investigation of the 'duplication and divergence' theory of protein evolution. Journal of Molecular Evolution 57, 149-158. RAE2008

A Neural Theory of Attentive Visual Search: Interactions of Boundary, Surface, Spatial, and Object Representations

Visual search data are given a unified quantitative explanation by a model of how spatial maps in the parietal cortex and object recognition categories in the inferotemporal cortex deploy attentional resources as they reciprocally interact with visual representations in the prestriate cortex. The model visual representations arc organized into multiple boundary and surface representations. Visual search in the model is initiated by organizing multiple items that lie within a given boundary or surface representation into a candidate search grouping. These items arc compared with object recognition categories to test for matches or mismatches. Mismatches can trigger deeper searches and recursive selection of new groupings until a target object io identified. This search model is algorithmically specified to quantitatively simulate search data using a single set of parameters, as well as to qualitatively explain a still larger data base, including data of Aks and Enns (1992), Bravo and Blake (1990), Chellazzi, Miller, Duncan, and Desimone (1993), Egeth, Viri, and Garbart (1984), Cohen and Ivry (1991), Enno and Rensink (1990), He and Nakayarna (1992), Humphreys, Quinlan, and Riddoch (1989), Mordkoff, Yantis, and Egeth (1990), Nakayama and Silverman (1986), Treisman and Gelade (1980), Treisman and Sato (1990), Wolfe, Cave, and Franzel (1989), and Wolfe and Friedman-Hill (1992). The model hereby provides an alternative to recent variations on the Feature Integration and Guided Search models, and grounds the analysis of visual search in neural models of preattentive vision, attentive object learning and categorization, and attentive spatial localization and orientation.

What is the value of technology? Toward a labour theory of technology change

Economic analysis of technology treats it as given exogenously, while determined endogenously. This paper examines the conceptual conflict. The paper outlines an alternative conceptual framework. This uses a 'General Vertical Division of Labour' into conceptual and executive parts to facilitate a coherent political economic explanation of technological change. The paper suggests that we may acquire rather than impose an understanding of technological change. It also suggests that we may re-define and reassess the efficiency of technological change, through the values inculcated into it.

'A Job in Politics is not for Woman': Analysing Barriers to Women's Political Representation in CEE

This article discusses women’s political representation in Central and Eastern Europe in the fifteen years after the fall of the Berlin Wall and the adoption of liberal democratic political systems in the region. It highlights the deepseated gender stereotypes that define women primarily as wives and mothers, with electoral politics seen as an appropriate activity for men, but less so for women. The article explores the ways in which conservative attitudes on gender roles hinders the supply of, and demand for, women in the politics of Central and Eastern Europe. It also discusses the manner in which the internalisation of traditional gender norms affects women’s parliamentary behaviour, as few champion women’s rights in the legislatures of the region. The article also finds that links between women MPs and women’s organisations are weak and fragmented, making coalition-building around agendas for women’s rights problematic.

Self-consistent non-Markovian theory of a quantum-state evolution for quantum-information processing

We study non-Markovian decoherence phenomena by employing projection-operator formalism when a quantum system (a quantum bit or a register of quantum bits) is coupled to a reservoir. By projecting out the degree of freedom of the reservoir, we derive a non-Markovian master equation for the system, which is reduced to a Lindblad master equation in Markovian limit, and obtain the operator sum representation for the time evolution. It is found that the system is decohered slower in the non- Markovian reservoir than the Markovian because the quantum information of the system is memorized in the non-Markovian reservoir. We discuss the potential importance of non-Markovian reservoirs for quantum-information processing.

Horowitz’s Theory of Ethnic Party Competition and the Case of the SDLP, 1970-79

Donald Horowitz's theory of ethnic conflict suggests that a political party operating in a deeply divided society can be effected by a centrifugal pull even when it is not subject to formal electoral competition. This idea can be applied to Northern Ireland's SDLP in the 1970s, when the party faced no credible electoral rival within its primary political constituency. Doing so helps to explain why the SDLP failed in its original objective of mobilizing a cross-community constituency, and instead became what Horowitz terms an “ethnically based party,” representing the interests of only one side of the political divide in Northern Ireland.