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

Ecological dynamics of emerging bat virus spillover

Viruses that originate in bats may be the most notorious emerging zoonoses that spill over from wildlife into domestic animals and humans. Understanding how these infections filter through ecological systems to cause disease in humans is of profound importance to public health. Transmission of viruses from bats to humans requires a hierarchy of enabling conditions that connect the distribution of reservoir hosts, viral infection within these hosts, and exposure and susceptibility of recipient hosts. For many emerging bat viruses, spillover also requires viral shedding from bats, and survival of the virus in the environment. Focusing on Hendra virus, but also addressing Nipah virus, Ebola virus, Marburg virus and coronaviruses, we delineate this cross-species spillover dynamic from the within-host processes that drive virus excretion to land-use changes that increase interaction among species. We describe how land-use changes may affect co-occurrence and contact between bats and recipient hosts. Two hypotheses may explain temporal and spatial pulses of virus shedding in bat populations: episodic shedding from persistently infected bats or transient epidemics that occur as virus is transmitted among bat populations. Management of livestock also may affect the probability of exposure and disease. Interventions to decrease the probability of virus spillover can be implemented at multiple levels from targeting the reservoir host to managing recipient host exposure and susceptibility.

Variation in the Understanding of Lutheranism and Its Implications for Religious Education : Meaning Discernment of Students and Teachers in Finnish Upper Secondary Schools

The study investigated variation in the ways in which a group of students and teachers of Evangelical Lutheran religious education in Finnish upper secondary schools understand Lutheranism and searched for educational implications for learning in religious education. The aim of understanding the qualitative variation in understanding Lutheranism was explored through the relationship between the following questions, which correspond to the results reported in the following original refereed publications: 1) How do Finnish students understand Lutheranism? 2) How do Finnish teachers of religious education constitute the meaning of Lutheranism? 3) How could phenomenography and the Variation Theory of Learning contribute to learning about and from religion in the context of Finnish Lutheran Religious Education as compared to religious education in the UK? Two empirical studies (Hella, 2007; Hella, 2008) were undertaken from a phenomenographic research perspective (e.g., Marton, 1981) and the Variation Theory of Learning (e.g., Marton & Tsui et al. 2004) that developed from it. Data was collected from 63 upper secondary students and 40 teachers of religious education through written tasks with open questions and complementary interviews with 11 students and 20 teachers for clarification of meanings. The two studies focused on the content and structure of meaning discernment in students and teachers expressed understandings of Lutheranism. Differences in understandings are due to differences in the meanings that are discerned and focused on. The key differences between the ways students understand varied from understanding Lutheranism as a religion to personal faith with its core in mercy. The logical relationships between the categories that describe variation in understanding express a hierarchy of ascending complexity, according to which more developed understandings are inclusive of less developed ones. The ways the teachers understand relate to student s understandings in a sequential manner. Phenomenography and Variation Theory were discussed in the context of religious education in Finland and the UK in relation to the theoretical notion of learning about and from religion (Hella & Wright, 2008). The thesis suggests that variation theory enables religious educators to recognise the unity of learning about and from religion, as learning is always learning about something and involves simultaneous engagement with the object of learning and development as a person. The study also suggests that phenomenography and variation theory offer a means by which it is possible for academics, policy makers, curriculum designers, teachers and students to learn to discern different ways of understanding the contested nature of religions. Keywords: Lutheranism, understanding, variation, teaching, learning, phenomenography, religious education

Food intake, growth and social interactions of signal crayfish, Pacifastacus leniusculus (Dana)

The knowledge about the optimal rearing conditions, such as water temperature and quality, photoperiod and density, with the understanding of animal nutritional requirements forms the basis of economically stable aquaculture for freshwater crayfish. However, the shift from a natural environment to effective culture conditions induces several changes, not only at the population level, but also at the individual level. The social contacts between conspecifics increase with increasing animal density. The competition for limited resources (e.g. food, shelter, mates) is more severe with the presence of agonistic behaviour and may lead to unequal distribution of these. The objectives of this study were to: 1) study the distribution of a common food resource between communally reared signal crayfish (Pacifastacus leniusculus) and to assign potential feeding hierarchy on the basis of individual food intake measurements, 2) explore the possibilities of size distribution manipulations to affect population dynamics and food intake to improve growth and survival in culture and 3) study the effect of food ration and spatial distribution on food intake and to explore the effect of temperature and food ration on growth and body composition of freshwater crayfish. The feeding ranks between animals were assigned with a new method for individual food intake measurement of communally reared crayfish. This technique has a high feasibility and a great potential to be applied in crayfish aquaculture studies. In this study, signal crayfish showed high size-related variability in food consumption both among individuals within a group (inter-individual) and within individual day-to-day variation (intra-individual). Increased competition for food led to an unequal distribution of this resource and this may be a reason for large growth differences between animals. The consumption was significantly higher when reared individually in comparison with communal housing. These results suggest that communally housed crayfish form a feeding hierarchy and that the animal size is the major factor controlling the position in this hierarchy. The optimisation of the social environment ( social conditions ) was evaluated in this study as a new approach to crayfish aquaculture. The results showed that the absence of conspecifics (individual rearing vs. communal housing) affects growth rate, food intake and the proportion of injured animals, whereas size variation between animals influences the number and duration of agonistic encounters. In addition, animal size had a strong influence on the fighting success of signal crayfish reared in a social milieu with a wide size variation of conspecifics. Larger individuals initiated and won most of the competitions, which suggests size-based social hierarchy of P. leniusculus. This is further supported by the fact that the length and weight gain of smaller animals increased after size grading, maybe because of a better access to the food resource due to diminished social pressure. However, the high dominance index was not based on size under conditions of limited size variation, e.g. those characteristic of restocked natural populations and aquaculture, indicating the important role of behaviour on social hierarchy.

Context-dependency of a complex fruit-frugivore mutualism: temporal variation in crop size and neighborhood effects

The quantity of fruit consumed by dispersers is highly variable among individuals within plant populations. The outcome Of Such selection operated by firugivores has been examined mostly with respect to changing spatial contexts. The influence of varying temporal contexts on frugivore choice, and their possible demographic and evolutionary consequences is poorly understood. We examined if temporal variation in fruit availability across a hierarchy of nested temporal levels (interannual, intraseasonal, 120 h, 24 h) altered frugivore choice for a complex seed dispersal system in dry tropical forests of southern India. The interactions between Phyllanthus emblica and its primary disperser (ruminants) was mediated by another frugivore (a primate),which made large quantities of fruit available on the ground to ruminants. The direction and strength of crop size and neighborhood effects on this interaction varied with changing temporal contexts.Fruit availability was higher in the first of the two study years, and at the start of the season in both years. Fruit persistence on trees,determined by primate foraging, was influenced by crop size andconspecific neighborhood densities only in the high fruit availability year. Fruit removal by ruminants was influenced by crop size in both years and neighborhood densities only in the high availability year. In both years, these effects were stronger at the start of the season.Intraseasonal reduction in fruit availability diminished inequalities in fruit removal by ruminants and the influence of crop size and fruiting neighborhoods. All trees were not equally attractive to frugivores in a P. emblica population at all points of time. Temporal asymmetry in frugivore-mediated selection could reduce potential for co-evolution between firugivores and plants by diluting selective pressures. Inter-dependencies; formed between disparate animal consumers can add additional levels of complexity to plant-frugivore mutualistic networks and have potential reproductive consequences for specific individuals within populations.

Application of D transforms in the analysis of nonlinear distributed parameter systems

The scope of application of Laplace transforms presently limited to the study of linear partial differential equations, is extended to the nonlinear domain by this study. This has been achieved by modifying the definition of D transforms, put forth recently for the study of classes of nonlinear lumped parameter systems. The appropriate properties of the new D transforms are presented to bring out their applicability in the analysis of nonlinear distributed parameter systems.

Philosophy as a Path to Happiness : Attainment of Happiness in Arabic Peripatetic and Ismaili Philosophy

The aim of the dissertation is to explore the idea of philosophy as a path to happiness in classical Arabic philosophy. The starting point is in comparison of two distinct currents between the 10th and early 11th centuries, Peripatetic philosophy, represented by al-Fārābī and Ibn Sīnā, and Ismaili philosophy represented by al-Kirmānī and the Brethren of Purity. They initially offer two contrasting views about philosophy in that the attitude of the Peripatetics is rationalistic and secular in spirit, whereas for the Ismailis philosophy represents the esoteric truth behind revelation. Still, they converge in their view that the ultimate purpose of philosophy lies in its ability to lead man towards happiness. Moreover, they share a common concept of happiness as a contemplative ideal of human perfection, which refers primarily to an otherworldly state of the soul s ascent to the spiritual world. For both the way to happiness consists of two parts: theory and practice. The practical part manifests itself in the idea of the purification of the rational soul from its bodily attachments in order for it to direct its attention fully to the contemplative life. Hence, there appears an ideal of philosophical life with the goal of relative detachment from the worldly life. The regulations of the religious law in this context appear as the primary means for the soul s purification, but for all but al-Kirmānī they are complemented by auxiliary philosophical practices. The ascent to happiness, however, takes place primarily through the acquisition of theoretical knowledge. The saving knowledge consists primarily of the conception of the hierarchy of physical and metaphysical reality, but all of philosophy forms a curriculum through which the soul gradually ascends towards a spiritual state of being along an order that is inverse to the Neoplatonic emanationist hierarchy of creation. For Ismaili philosophy the ascent takes place from the exoteric religious sciences towards the esoteric philosophical knowledge. For Peripatetic philosophers logic performs the function of an instrument enabling the ascent, mathematics is treated either as propaedeutic to philosophy or as a mediator between physical and metaphysical knowledge, whereas physics and metaphysics provide the core of knowledge necessary for the attainment of happiness.

Computational Methods for Studies of Quantum Dots and Boson Condensates

This thesis presents ab initio studies of two kinds of physical systems, quantum dots and bosons, using two program packages of which the bosonic one has mainly been developed by the author. The implemented models, \emph{i.e.}, configuration interaction (CI) and coupled cluster (CC) take the correlated motion of the particles into account, and provide a hierarchy of computational schemes, on top of which the exact solution, within the limit of the single-particle basis set, is obtained. The theory underlying the models is presented in some detail, in order to provide insight into the approximations made and the circumstances under which they hold. Some of the computational methods are also highlighted. In the final sections the results are summarized. The CI and CC calculations on multiexciton complexes in self-assembled semiconductor quantum dots are presented and compared, along with radiative and non-radiative transition rates. Full CI calculations on quantum rings and double quantum rings are also presented. In the latter case, experimental and theoretical results from the literature are re-examined and an alternative explanation for the reported photoluminescence spectra is found. The boson program is first applied on a fictitious model system consisting of bosonic electrons in a central Coulomb field for which CI at the singles and doubles level is found to account for almost all of the correlation energy. Finally, the boson program is employed to study Bose-Einstein condensates confined in different anisotropic trap potentials. The effects of the anisotropy on the relative correlation energy is examined, as well as the effect of varying the interaction potential.}

Locally checkable proofs

This work studies decision problems from the perspective of nondeterministic distributed algorithms. For a yes-instance there must exist a proof that can be verified with a distributed algorithm: all nodes must accept a valid proof, and at least one node must reject an invalid proof. We focus on locally checkable proofs that can be verified with a constant-time distributed algorithm. For example, it is easy to prove that a graph is bipartite: the locally checkable proof gives a 2-colouring of the graph, which only takes 1 bit per node. However, it is more difficult to prove that a graph is not bipartite—it turns out that any locally checkable proof requires Ω(log n) bits per node. In this work we classify graph problems according to their local proof complexity, i.e., how many bits per node are needed in a locally checkable proof. We establish tight or near-tight results for classical graph properties such as the chromatic number. We show that the proof complexities form a natural hierarchy of complexity classes: for many classical graph problems, the proof complexity is either 0, Θ(1), Θ(log n), or poly(n) bits per node. Among the most difficult graph properties are symmetric graphs, which require Ω(n2) bits per node, and non-3-colourable graphs, which require Ω(n2/log n) bits per node—any pure graph property admits a trivial proof of size O(n2).

Perturbative growth of cosmological clustering. I: Formalism

Here we rederive the hierarchy of equations for the evolution of distribution functions of various orders using a convenient parameterization. We use this to obtain equations for two- and three-point correlation functions in powers of a small parameter, viz., the initial density contrast. The correspondence of the lowest order solutions of these equations to the results from the linear theory of density perturbations is shown for an OMEGA = 1 universe. These equations are then used to calculate, to the lowest order, the induced three-point correlation function that arises from Gaussian initial conditions in an OMEGA = 1 universe. We obtain an expression which explicitly exhibits the spatial structure of the induced three-point correlation function. It is seen that the spatial structure of this quantity is independent of the value of OMEGA. We also calculate the triplet momentum. We find that the induced three-point correlation function does not have the ''hierarchical'' form often assumed. We discuss possibilities of using the induced three-point correlation to interpret observational data. The formalism developed here can also be used to test a validity of different schemes to close the

Automatic decomposition of unstructured meshes employing genetic algorithms for parallel FEM computations

Parallel execution of computational mechanics codes requires efficient mesh-partitioning techniques. These mesh-partitioning techniques divide the mesh into specified number of submeshes of approximately the same size and at the same time, minimise the interface nodes of the submeshes. This paper describes a new mesh partitioning technique, employing Genetic Algorithms. The proposed algorithm operates on the deduced graph (dual or nodal graph) of the given finite element mesh rather than directly on the mesh itself. The algorithm works by first constructing a coarse graph approximation using an automatic graph coarsening method. The coarse graph is partitioned and the results are interpolated onto the original graph to initialise an optimisation of the graph partition problem. In practice, hierarchy of (usually more than two) graphs are used to obtain the final graph partition. The proposed partitioning algorithm is applied to graphs derived from unstructured finite element meshes describing practical engineering problems and also several example graphs related to finite element meshes given in the literature. The test results indicate that the proposed GA based graph partitioning algorithm generates high quality partitions and are superior to spectral and multilevel graph partitioning algorithms.

Comparison of HMM and SDTW for Tamil handwritten character recognition

In this paper, we compare the experimental results for Tamil online handwritten character recognition using HMM and Statistical Dynamic Time Warping (SDTW) as classifiers. HMM was used for a 156-class problem. Different feature sets and values for the HMM states & mixtures were tried and the best combination was found to be 16 states & 14 mixtures, giving an accuracy of 85%. The features used in this combination were retained and a SDTW model with 20 states and single Gaussian was used as classifier. Also, the symbol set was increased to include numerals, punctuation marks and special symbols like $, & and #, taking the number of classes to 188. It was found that, with a small addition to the feature set, this simple SDTW classifier performed on par with the more complicated HMM model, giving an accuracy of 84%. Mixture density estimation computations was reduced by 11 times. The recognition is writer independent, as the dataset used is quite large, with a variety of handwriting styles.

Thermo-physical and structural studies of sodium zinc borovanadate glasses in the region of high concentration of modifier oxides

This paper reports investigation of Na2O and ZnO modified borovanadate glasses in the highly modified regime of compositions. These glasses have been prepared by microwave route. Ultraviolet (UV) and visible, infrared (IR), Magic Angle Spinning Nuclear Magnetic Resonance (MAS NMR) and Electron Paramagnetic Resonance (EPR) spectroscopies have been used to characterize the speciation in the glasses. Together with the variation of properties such as molar volume and glass transition temperatures, spectroscopic data indicate that at high levels of modification, ZnO tends to behave like network former. It is proposed that the observed variation of all the properties can be reasonably well understood with a structural model. The model considers that the modification and speciation in glasses are strongly determined by the hierarchy of group electronegativities. Further, it is proposed that the width of the transitions of glasses obtained under same condition reflects the fragility of the glasses. An empirical expression has been suggested to quantify fragility on the basis of width of the transition regions. (C) 2012 Elsevier Ltd. All rights reserved.

The evolution of complexity in social organization-A model using dominance-subordinate behavior in two social wasp species

Dominance and subordinate behaviors are important ingredients in the social organizations of group living animals. Behavioral observations on the two eusocial species Ropalidia marginata and Ropalidia cyathiformis suggest varying complexities in their social systems. The queen of R. cyathiformis is an aggressive individual who usually holds the top position in the dominance hierarchy although she does not necessarily show the maximum number of acts of dominance, while the R. marginata queen rarely shows aggression and usually does not hold the top position in the dominance hierarchy of her colony. In R. marginata, more workers are involved in dominance-subordinate interactions as compared to R. cyathiformis. These differences are reflected in the distribution of dominance-subordinate interactions among the hierarchically ranked individuals in both the species. The percentage of dominance interactions decreases gradually with hierarchical ranks in R. marginata while in R. cyathiformis it first increases and then decreases. We use an agent-based model to investigate the underlying mechanism that could give rise to the observed patterns for both the species. The model assumes, besides some non-interacting individuals, the interaction probabilities of the agents depend on their pre-differentiated winning abilities. Our simulations show that if the queen takes up a strategy of being involved in a moderate number of dominance interactions, one could get the pattern similar to R. cyathiformis, while taking up the strategy of very low interactions by the queen could lead to the pattern of R. marginata. We infer that both the species follow a common interaction pattern, while the differences in their social organization are due to the slight changes in queen as well as worker strategies. These changes in strategies are expected to accompany the evolution of more complex societies from simpler ones.

The role of tusks, musth and body size in male-male competition among Asian elephants, Elephas maximus

The evolution of sexually dimorphic, elaborate male traits that are seemingly maladaptive may be driven by sexual selection (male-male competition and or female mate choice). Tusk possession in the Asian elephant is sexually dimorphic and exaggerated but its role in male-male competition has not yet been determined. We examined the role of the tusks in establishing dominance along with two other known male-male signals, namely, body size and musth (a temporary physiologically heightened sexual state) in an Asian elephant population in northeastern India with equal proportions of tusked and tuskless males. We observed 116 agonistic interactions with clear dominance outcomes between adult (>15 years) males during 458 field days in the dry season months of 2008-2011. A generalized linear mixed-effects model was used to predict the probability of winning as a function of body size, tusk possession and musth status relative to the opponent. A hierarchy of the three male-male signals emerged from this analysis, with musth overriding body size and body size overriding tusk possession. In this elephant population tusk possession thus plays a relatively minor role in male-male competition. An important implication of musth and body size being stronger determinants of dominance than tusk possession is that it could facilitate rapid evolution of tuskless males in the population under artificial selection against tusked individuals, which are poached for ivory. (C) 2013 The Association for the Study of Animal Behaviour. Published by Elsevier Ltd. All rights reserved.