Defining Contexts in Context-Free Grammars

This thesis introduces an extension of Chomsky’s context-free grammars equipped with operators for referring to left and right contexts of strings.The new model is called grammar with contexts. The semantics of these grammars are given in two equivalent ways — by language equations and by logical deduction, where a grammar is understood as a logic for the recursive definition of syntax. The motivation for grammars with contexts comes from an extensive example that completely defines the syntax and static semantics of a simple typed programming language. Grammars with contexts maintain most important practical properties of context-free grammars, including a variant of the Chomsky normal form. For grammars with one-sided contexts (that is, either left or right), there is a cubic-time tabular parsing algorithm, applicable to an arbitrary grammar. The time complexity of this algorithm can be improved to quadratic,provided that the grammar is unambiguous, that is, it only allows one parsefor every string it defines. A tabular parsing algorithm for grammars withtwo-sided contexts has fourth power time complexity. For these grammarsthere is a recognition algorithm that uses a linear amount of space. For certain subclasses of grammars with contexts there are low-degree polynomial parsing algorithms. One of them is an extension of the classical recursive descent for context-free grammars; the version for grammars with contexts still works in linear time like its prototype. Another algorithm, with time complexity varying from linear to cubic depending on the particular grammar, adapts deterministic LR parsing to the new model. If all context operators in a grammar define regular languages, then such a grammar can be transformed to an equivalent grammar without context operators at all. This allows one to represent the syntax of languages in a more succinct way by utilizing context specifications. Linear grammars with contexts turned out to be non-trivial already over a one-letter alphabet. This fact leads to some undecidability results for this family of grammars

Food webs in the era of molecular revolution – Like resolving the Gordian knot with a tricorder

Living nature consists of countless organisms, which are classified into millions of species. These species interact in many ways; for example predators when foraging on their prey, insect larvae consuming plants, and pathogenic bacteria drifting into humans. In addition, abiotic nature has a great initiative impact on life through many factors (including sunlight, ambient temperature, and water. In my thesis, I have studied interactions among different life forms in multifaceted ways. The webs of these interactions are commonly referred to as food webs, describing feeding relationships between species or energy transfer from one trophic level to another. These ecological interactions – whether they occur between species, between individuals, or between microorganisms within an individual – are among the greatest forces affecting natural communities. Relationships are tightly related to biological diversity, that is, species richness and abundances. A species is called a node in food web vocabulary, and its interactions to other species are called links. Generally, Artic food webs are considered to be loosely linked, simple structures. This conception roots into early modern food webs, where insects and other arthropods, for example, were clumped under one node. However, it has been shown that arthropods form the greatest part of diversity and biomass both in the tropics and in Arctic areas. Earlier challenges of revealing the role of insects and microorganisms in interactions webs have become possible with the help of recent advances in molecular techniques. In the first chapter, I studied the prey diversity of a common bat, Myotis daubentonii, in southwestern Finland. My results proved M. daubentonii being a versatile predator whose diet mainly consists of aquatic insects, such as chironomid midges. In the second chapter, I expanded the view to changes in seasonal and individual-based variation in the diet of M. daubentonii including the relationship between available and observed prey. I found out that chironomids remain the major prey group even though their abundance decreases in proportion to other insect groups. Diet varied a lot between individuals, although the differences were not statistically significant. The third chapter took the study to a large network in Greenland. I showed that Artic food webs are very complex when arthropods are taken into account. In the fourth chapter, I examined the bacterial flora of M. daubentonii and surveyed the zoonotic potential of these bacteria. I found Bartonella bacteria, of which one was described as a new species named after the locality of discovery. I have shown in my thesis that Myotis daubentonii as a predator links many insect species as well as terrestrial and aquatic environments. Moreover, I have exposed that Arctic food webs are complex structures comprising of many densely linked species. Finally, I demonstrated that the bacterial flora of bats includes several previously unknown species, some of which could possibly turn in to zoonosis. To summarize, molecular methods have untied several knots in biological research. I hope that this kind of increasing knowledge of the surrounding nature makes us further value all the life forms on earth.