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

Word Sense Discovery and Disambiguation

The work is based on the assumption that words with similar syntactic usage have similar meaning, which was proposed by Zellig S. Harris (1954,1968). We study his assumption from two aspects: Firstly, different meanings (word senses) of a word should manifest themselves in different usages (contexts), and secondly, similar usages (contexts) should lead to similar meanings (word senses). If we start with the different meanings of a word, we should be able to find distinct contexts for the meanings in text corpora. We separate the meanings by grouping and labeling contexts in an unsupervised or weakly supervised manner (Publication 1, 2 and 3). We are confronted with the question of how best to represent contexts in order to induce effective classifiers of contexts, because differences in context are the only means we have to separate word senses. If we start with words in similar contexts, we should be able to discover similarities in meaning. We can do this monolingually or multilingually. In the monolingual material, we find synonyms and other related words in an unsupervised way (Publication 4). In the multilingual material, we ?nd translations by supervised learning of transliterations (Publication 5). In both the monolingual and multilingual case, we first discover words with similar contexts, i.e., synonym or translation lists. In the monolingual case we also aim at finding structure in the lists by discovering groups of similar words, e.g., synonym sets. In this introduction to the publications of the thesis, we consider the larger background issues of how meaning arises, how it is quantized into word senses, and how it is modeled. We also consider how to define, collect and represent contexts. We discuss how to evaluate the trained context classi?ers and discovered word sense classifications, and ?nally we present the word sense discovery and disambiguation methods of the publications. This work supports Harris' hypothesis by implementing three new methods modeled on his hypothesis. The methods have practical consequences for creating thesauruses and translation dictionaries, e.g., for information retrieval and machine translation purposes. Keywords: Word senses, Context, Evaluation, Word sense disambiguation, Word sense discovery.

How to Succeed in Knowledge Transfer : Case Study of Scandinavian Alliance in Ukraine

The current study of Scandinavian multinational corporate subsidiaries in the rapidly growing Eastern European market, due to their particular organizational structure, attempts to gain some new insights into processes and potential benefits of knowledge and technology transfer. This study explores how to succeed in knowledge transfer and to become more competitive, driven by the need to improve transfer of systematic knowledge for the manufacture of product and service provisions in newly entered market. The scope of current research is exactly limited to multinational corporations, which are defined as enterprises comprising entities in two or more countries, regardless of legal forms and field of activity of those entities, and which operate under a system of decision-making permitting coherent policies and a common strategy through one or more decision-making centers. The entities are linked, by ownership, and able to exercise influence over the activities of the others; and, in particular, to share the knowledge, resources, and responsibilities with others. The research question is "How and to which extent can knowledge-transfer influence a company's technological competence and economic competitiveness?" and try to find out what particular forces and factors affect the development of subsidiary competencies; what factors influence the corporate integration and use of the subsidiary's competencies; and what may increase competitiveness of MNC pursuing leading position in entered market. The empirical part of the research was based on qualitative analyses of twenty interviews conducted among employees in Scandinavian MNC subsidiary units situated in Ukraine, using structured sequence of questions with open-ended answers. The data was investigated by comparison case analyses to literature framework. Findings indicate that a technological competence developed in one subsidiary will lead to an integration of that competence with other corporate units within the MNC. Success increasingly depends upon people's learning. The local economic area is crucial for understanding competition and industrial performance, as there seems to be a clear link between the performance of subsidiaries and the conditions prevailing in their environment. The linkage between competitive advantage and company's success is mutually dependent. Observation suggests that companies can be characterized as clusters of complementary activities such as R&D, administration, marketing, manufacturing and distribution. Study identifies barriers and obstacles in technology and knowledge transfer that is relevant for the subsidiaries' competence development. The accumulated experience can be implemented in new entered market with simple procedures, and at a low cost under specific circumstances, by cloning. The main goal is focused to support company prosperity, making more profits and sustaining an increased market share by improved product quality and/or reduced production cost of the subsidiaries through cloning approach. Keywords: multinational corporation; technology transfer; knowledge transfer; subsidiary competence; barriers and obstacles; competitive advantage; Eastern European market