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

Efficient search for statistically significant dependency rules in binary data

Analyzing statistical dependencies is a fundamental problem in all empirical science. Dependencies help us understand causes and effects, create new scientific theories, and invent cures to problems. Nowadays, large amounts of data is available, but efficient computational tools for analyzing the data are missing. In this research, we develop efficient algorithms for a commonly occurring search problem - searching for the statistically most significant dependency rules in binary data. We consider dependency rules of the form X->A or X->not A, where X is a set of positive-valued attributes and A is a single attribute. Such rules describe which factors either increase or decrease the probability of the consequent A. A classical example are genetic and environmental factors, which can either cause or prevent a disease. The emphasis in this research is that the discovered dependencies should be genuine - i.e. they should also hold in future data. This is an important distinction from the traditional association rules, which - in spite of their name and a similar appearance to dependency rules - do not necessarily represent statistical dependencies at all or represent only spurious connections, which occur by chance. Therefore, the principal objective is to search for the rules with statistical significance measures. Another important objective is to search for only non-redundant rules, which express the real causes of dependence, without any occasional extra factors. The extra factors do not add any new information on the dependence, but can only blur it and make it less accurate in future data. The problem is computationally very demanding, because the number of all possible rules increases exponentially with the number of attributes. In addition, neither the statistical dependency nor the statistical significance are monotonic properties, which means that the traditional pruning techniques do not work. As a solution, we first derive the mathematical basis for pruning the search space with any well-behaving statistical significance measures. The mathematical theory is complemented by a new algorithmic invention, which enables an efficient search without any heuristic restrictions. The resulting algorithm can be used to search for both positive and negative dependencies with any commonly used statistical measures, like Fisher's exact test, the chi-squared measure, mutual information, and z scores. According to our experiments, the algorithm is well-scalable, especially with Fisher's exact test. It can easily handle even the densest data sets with 10000-20000 attributes. Still, the results are globally optimal, which is a remarkable improvement over the existing solutions. In practice, this means that the user does not have to worry whether the dependencies hold in future data or if the data still contains better, but undiscovered dependencies.

A General Theory of Semi-Unification

Various restrictions on the terms allowed for substitution give rise to different cases of semi-unification. Semi-unification on finite and regular terms has already been considered in the literature. We introduce a general case of semi-unification where substitutions are allowed on non-regular terms, and we prove the equivalence of this general case to a well-known undecidable data base dependency problem, thus establishing the undecidability of general semi-unification. We present a unified way of looking at the various problems of semi-unification. We give some properties that are common to all the cases of semi-unification. We also the principality property and the solution set for those problems. We prove that semi-unification on general terms has the principality property. Finally, we present a recursive inseparability result between semi-unification on regular terms and semi-unification on general terms.

The transformation of Ireland 1958 - 93: the role of ideas in punctuating institutional path dependency at critical junctures

Ireland experienced two critical junctures when its economic survival was threatened: 1958/9 and 1986/7. Common to both crises was the supplanting of long established practices, that had become an integral part of the political culture of the state, by new ideas that ensured eventual economic recovery. In their adoption and implementation these ideas also fundamentally changed the institutions of state – how politics was done, how it was organised and regulated. The end result was the transformation of the Irish state. The main hypothesis of this thesis is that at those critical junctures the political and administrative elites who enabled economic recovery were not just making pragmatic decisions, their actions were influenced by ideas. Systematic content analysis of the published works of the main ideational actors, together with primary interviews with those actors still alive, reveals how their ideas were formed, what influenced them, and how they set about implementing their ideas. As the hypothesis assumes institutional change over time historical institutionalism serves as the theoretical framework. Central to this theory is the idea that choices made when a policy is being initiated or an institution formed will have a continuing influence long into the future. Institutions of state become ‘path dependent’ and impervious to change – the forces of inertia take over. That path dependency is broken at critical junctures. At those moments ideas play a major role as they offer a set of ready-made solutions. Historical institutionalism serves as a robust framework for proving that in the transformation of Ireland the role of ideas in punctuating institutional path dependency at critical junctures was central.

A theory of hypoellipticity and unique ergodicity for semilinear stochastic PDEs

We present a theory of hypoellipticity and unique ergodicity for semilinear parabolic stochastic PDEs with "polynomial" nonlinearities and additive noise, considered as abstract evolution equations in some Hilbert space. It is shown that if Hörmander's bracket condition holds at every point of this Hilbert space, then a lower bound on the Malliavin covariance operatorμt can be obtained. Informally, this bound can be read as "Fix any finite-dimensional projection on a subspace of sufficiently regular functions. Then the eigenfunctions of μt with small eigenvalues have only a very small component in the image of Π." We also show how to use a priori bounds on the solutions to the equation to obtain good control on the dependency of the bounds on the Malliavin matrix on the initial condition. These bounds are sufficient in many cases to obtain the asymptotic strong Feller property introduced in [HM06]. One of the main novel technical tools is an almost sure bound from below on the size of "Wiener polynomials," where the coefficients are possibly non-adapted stochastic processes satisfying a Lips chitz condition. By exploiting the polynomial structure of the equations, this result can be used to replace Norris' lemma, which is unavailable in the present context. We conclude by showing that the two-dimensional stochastic Navier-Stokes equations and a large class of reaction-diffusion equations fit the framework of our theory.

Modelling bi-directional research: a fresh approach to stakeholder theory

Purpose – While Freeman's stakeholder management approach has attracted much attention from both scholars and practitioners, little empirical work has considered the interconnectedness of organisational perspectives and stakeholder perspectives. The purpose of this paper is to respond to this gap by developing and empirically testing a bi-directional model of organisation/stakeholder relationships. Design/methodology/approach – A conceptual framework is developed that integrates how stakeholders are affected by organisations with how they affect organisations. Quantitative data relating to both sides of the relationship are obtained from 700 customers of a European service organisation and analysed using partial least squares structural equation modelling technique. Findings – The findings provide empirical support for the notion of mutual dependency between organisations and stakeholders as advocated by stakeholder theorists. The results suggest that the way stakeholders relate to organisations is dependent on how organisations relate to stakeholders. Originality/value – The study is original on two fronts: first, it provides a framework and process that can be used by researchers to model bi-directional research with other stakeholder groups and in different contexts. Second, the study presents an example application of bi-directional research by empirically linking organisational and stakeholder expectations in the case of customers of a UK service organisation.

Artefact-oriented business process modelling: an ontological dependency approach

Business process modelling can help an organisation better understand and improve its business processes. Most business process modelling methods adopt a task- or activity-based approach to identifying business processes. Within our work, we use activity theory to categorise elements within organisations as being either human beings, activities or artefacts. Due to the direct relationship between these three elements, an artefact-oriented approach to organisation analysis emerges. Organisational semiotics highlights the ontological dependency between affordances within an organisation. We analyse the ontological dependency between organisational elements, and therefore produce the ontology chart for artefact-oriented business process modelling in order to clarify the relationship between the elements of an organisation. Furthermore, we adopt the techniques from semantic analysis and norm analysis, of organisational semiotics, to develop the artefact-oriented method for business process modelling. The proposed method provides a novel perspective for identifying and analysing business processes, as well as agents and artefacts, as the artefact-oriented perspective demonstrates the fundamental flow of an organisation. The modelling results enable an organisation to understand and model its processes from an artefact perspective, viewing an organisation as a network of artefacts. The information and practice captured and stored in artefact can also be shared and reused between organisations that produce similar artefacts.

Theory and generalization of Monte Carlo models of the BOLD signal source

The dependency of the blood oxygenation level dependent (BOLD) signal on underlying hemodynamics is not well understood. Building a forward biophysical model of this relationship is important for the quantitative estimation of the hemodynamic changes and neural activity underlying functional magnetic resonance imaging (fMRI) signals. We have developed a general model of the BOLD signal which can model both intra- and extravascular signals for an arbitrary tissue model across a wide range of imaging parameters. The model of the BOLD signal was instantiated as a look-up-table (LuT), and was verified against concurrent fMRI and optical imaging measurements of activation induced hemodynamics. Magn Reson Med, 2008. © 2008 Wiley-Liss, Inc.

Transport of simple fluids in nanopores: Theory and simulation

A theory is discussed of single-component transport in nanopores, recently developed by Bhatia and coworkers. The theory considers the oscillatory motion of molecules between diffuse wall collisions, arising from the fluid-wall interaction, along with superimposed viscous flow due to fluid-fluid interaction. The theory is tested against molecular dynamics simulations for hydrogen, methane, and carbon tetrafluoride flow in cylindrical nanopores in silica. Although exact at low densities, the theory performs well even at high densities, with the density dependency of the transport coefficient arising from viscous effects. Such viscous effects are reduced at high densities because of the large increase in viscosity, which explains the maximum in the transport coefficient with increase in density. Further, it is seen that in narrow pore sizes of less than two molecular diameters, where a complete monolayer cannot form on the surface, the mutual interference of molecules on opposite sides of the cross section can reduce the transport coefficient, and lead to a maximum in the transport coefficient with increasing density. The theory is also tested for the case of partially diffuse reflection and shows the viscous contribution to be negligible when the reflection is nearly specular. (c) 2005 American Institute of Chemical Engineers AIChE J, 52: 29-38, 2006.

Actor-network theory as a theoretical lens and research strategy for investigating firm internationalisation

Totally generalisable theories of firm internationalisation in the post-industrial era of international business, where national barriers are becoming less significant and technology becoming more influential, appear to be illusory. Stepwise or evolutionary models that predict gradual internationalisation are under challenge from empirical evidence of rapid internationalisation such as the phenomenon of the “born global” firm. Similarly, equilibrium models such as the eclectic paradigm have been criticised for being static and unable to account for process and path dependency. In this paper, the information and knowledge assumptions implied in theories of firm internationalisation are outlined and discussed. From this discussion, we suggest that actor-network theory, with its balance between description and explanation, may be a useful theoretical and empirical tool for investigating the complex and heterogeneous process of firm internationalisation whilst creating opportunities for further theory building.

Intensive care survivors’ experiences of ward-based care: Meleis’ theory of nursing transitions and role development among critical care outreach services.

Aims and objectives. To explore the psychosocial needs of patients discharged from intensive care, the extent to which they are captured using existing theory on transitions in care and the potential role development of critical care outreach, follow-up and liaison services. Background. Intensive care patients are at an increased risk of adverse events, deterioration or death following ward transfer. Nurse-led critical care outreach, follow-up or liaison services have been adopted internationally to prevent these potentially avoidable sequelae. The need to provide patients with psychosocial support during the transition to ward-based care has also been identified, but the evidence base for role development is currently limited. Design and methods. Twenty participants were invited to discuss their experiences of ward-based care as part of a broader study on recovery following prolonged critical illness. Psychosocial distress was a prominent feature of their accounts, prompting secondary data analysis using Meleis et al.’s mid-range theory on experiencing transitions. Results. Participants described a sense of disconnection in relation to profound debilitation and dependency and were often distressed by a perceived lack of understanding, indifference or insensitivity among ward staff to their basic care needs. Negotiating the transition between dependence and independence was identified as a significant source of distress following ward transfer. Participants varied in the extent to which they were able to express their needs and negotiate recovery within professionally mediated boundaries. Conclusion. These data provide new insights into the putative origins of the psychosocial distress that patients experience following ward transfer. Relevance to clinical practice. Meleis et al.’s work has resonance in terms of explicating intensive care patients’ experiences of psychosocial distress throughout the transition to general ward–based care, such that the future role development of critical care outreach, follow-up and liaison services may be more theoretically informed.

Feminist Disability Theory: Domestic Violence Against Women with a Disability

Women with a disability continue to experience social oppression and domestic violence as a consequence of gender and disability dimensions. Current explanations of domestic violence and disability inadequately explain several features that lead women who have a disability to experience violent situations. This article incorporates both disability and material feminist theory as an alternative explanation to the dominant approaches (psychological and sociological traditions) of conceptualising domestic violence. This paper is informed by a study which was concerned with examining the nature and perceptions of violence against women with a physical impairment. The emerging analytical framework integrating material feminist interpretations and disability theory provided a basis for exploring gender and disability dimensions. Insight was also provided by the women who identified as having a disability in the study and who explained domestic violence in terms of a gendered and disabling experience. The article argues that material feminist interpretations and disability theory, with their emphasis on gender relations, disablism and poverty, should be used as an alternative tool for exploring the nature and consequences of violence against women with a disability.