Toiminta ja tarkoite : Tutkimus suomen pronominista

The study describes the use and meaning of the Finnish demonstrative pronouns, focus being on the pronoun "tämä" (roughly 'this'). The Finnish demonstrative system is a three way one, the other two demonstratives are "tuo" ('that') and "se" ('it'). The data consisted of 12 half hours of video- and tape-recorded face-to-face and telephone conversations. The method for the study was ethnomethodological conversation analysis (CA); in addition to CA, the theoretical framework consisted of functional linguistics and linguistic anthropology. First, the study dealt with the syntactic distribution of the three demonstratives. The pronouns were analysed according to whether they are before or after the verb, and whether they compose an NP on their own or are determinants of a lexical NP. The study suggested that the form and the placement of the NP presents the referent as continuous/discontinuous or given/new. Givenness of a referent was defined as "identified adequately for the purposes of the on-going action". The so-called dislocated utterances were considered separately. It was found that left-dislocations are used for inserting referents in a particular relation to the on-going activity. Right-dislocations offer a solution for the sometimes competing motivations of newness and continuity: they are used for securing the identifiability of a referent that is implied to be continuous. Second, the study focussed on analysing the meaning of the pronouns according to three dimensions of reference: referential, indexical and relational. It was found that the demonstratives can organize interactional or spatial context. When organizing interactional context, the demonstrative pronouns express the role of identifying the referent in relation to the on-going activity. The pronoun "tämä" expresses that the referent is referentially open and the characterization of the referent is given in the on-going turn. Furthermore, it expresses asymmetry of the indexical ground: it expresses that the participants of a conversation do not share a mutual understanding of the activity at that particular time. In addition, the referent of the pronoun "tämä" is central for understanding the on-going action. Centrality could be understood as the relational feature of the pronoun. However, it is a consequence of the referential and indexical features of "tämä". The pronoun "tuo" also expresses referential openness, but it implies indexical symmetry. The pronoun "se" implies that the referent is known enough, and implies indexical symmetry. When used spatially, the pronouns may refer to a physical space or to a situation. They express or imply that the speaker is inside or outside the referent. The pronoun "tämä" implies inclusion, and the pronoun "tuo" expresses exclusion.

Luokan P loogisesta karakterisoinnista

Deskriptiivisessä vaativuusteoriassa tutkitaan laskennan vaativuuteen liittyviä kysymyksiä logiikan työkalujen avulla. Tällöin käsitellään tilannetta, jossa laskennan syötteenä toimivat äärelliset mallit. Tässä kehyksessä erinäisiä vaativuusluokkia voidaan karakterisoida etsimällä logiikoita, joilla on kyseistä vaativuusluokkaa vastaava ilmaisuvoima. Klassiset esimerkit tällaisista tuloksista ovat Faginin esittämä epädeterministisen polynomiaalisen ajan karakterisaatio logiikan Σ_1^1 avulla ja Immermanin, Livchakin ja Vardin esittämä deterministisen polynomiaalisen ajan karakterisaatio ensimmäisen kertaluvun inflatorisen kiintopistelogiikan avulla. Tässä opinnäytetyössä tarkastellaan Gurevichin esittämää kysymystä polynomiaalisessa ajassa ratkeavien kielten luokan P vahvasta loogisesta karakterisaatiosta. Kyseinen kysymys on yksi äärellisen malliteorian haastavimpia ongelmia. Kysymyksen esittelyyn tarvittavan peruskoneiston läpikäynnin lisäksi tässä käsi- tellään myös sen yhteyksiä laskennan vaativuusteoriassa keskeiseen P-NP-ongelmaan. Gurevichin kysymyksestä voidaan esittää myös rajoitetumpia versioita, mikäli käsitellään tilannetta, jossa laskennan syötteenä voi olla vain kiinnitetyn malliluokan K malleja. Tällöin luokan P karakterisointi helpottuu, ainakin jos luokka K on riittävän suppea. Tässä opinnäytetyössä käydään läpi Grohen esittämä tulos siitä, että mikäli luokaksi K valitaan 3-yhtenäisten tasoverkkojen luokka, niin ensimmäisen kertaluvun inflatorinen kiintopistelogiikka karakterisoi polynomiaalisessa ajassa laskettavat kielet.

Problems and Algorithms for Sequence Segmentations

The analysis of sequential data is required in many diverse areas such as telecommunications, stock market analysis, and bioinformatics. A basic problem related to the analysis of sequential data is the sequence segmentation problem. A sequence segmentation is a partition of the sequence into a number of non-overlapping segments that cover all data points, such that each segment is as homogeneous as possible. This problem can be solved optimally using a standard dynamic programming algorithm. In the first part of the thesis, we present a new approximation algorithm for the sequence segmentation problem. This algorithm has smaller running time than the optimal dynamic programming algorithm, while it has bounded approximation ratio. The basic idea is to divide the input sequence into subsequences, solve the problem optimally in each subsequence, and then appropriately combine the solutions to the subproblems into one final solution. In the second part of the thesis, we study alternative segmentation models that are devised to better fit the data. More specifically, we focus on clustered segmentations and segmentations with rearrangements. While in the standard segmentation of a multidimensional sequence all dimensions share the same segment boundaries, in a clustered segmentation the multidimensional sequence is segmented in such a way that dimensions are allowed to form clusters. Each cluster of dimensions is then segmented separately. We formally define the problem of clustered segmentations and we experimentally show that segmenting sequences using this segmentation model, leads to solutions with smaller error for the same model cost. Segmentation with rearrangements is a novel variation to the segmentation problem: in addition to partitioning the sequence we also seek to apply a limited amount of reordering, so that the overall representation error is minimized. We formulate the problem of segmentation with rearrangements and we show that it is an NP-hard problem to solve or even to approximate. We devise effective algorithms for the proposed problem, combining ideas from dynamic programming and outlier detection algorithms in sequences. In the final part of the thesis, we discuss the problem of aggregating results of segmentation algorithms on the same set of data points. In this case, we are interested in producing a partitioning of the data that agrees as much as possible with the input partitions. We show that this problem can be solved optimally in polynomial time using dynamic programming. Furthermore, we show that not all data points are candidates for segment boundaries in the optimal solution.

Kuoleman kielissä

Ihmisen virallinen olemassaolo ei pääty fysiologiseen kuolemaan. Se päättyy institutionaaliseen kielenkäyttöön: kuolintodistuksen kirjoittamiseen tai kuolleeksi julistamiseen. Valtaosa saa elämänsä viralliseksi päätökseksi lääkärin kirjoittaman kuolintodistuksen. Se on oikeuslääkinnällinen asiakirja, jolla saadaan aikaan uusi institutionaalinen asiaintila päättynyt elämä. Tarkastelen tutkielmassani 40 kuolintodistuksen kielenkäyttöä. Kartoitan, millaisia ovat niiden keskeiset kielenpiirteet. Osoitan myös, kuinka lääkäri esittää kuolintodistuksessa kertomuksen, jossa kieliopillisesti menneeseen aikaan kiinnittymätön kerronta toimii tekona, joka tekee tekstistä antinarratiivista ja avaa tien metatason merkityksenantoon. Tutkielmani keskeinen viitekehys on performatiivisuuden teoria. Esitän, ettei kuolintodistuksessa esitettyä lääketieteellistä kuolemankulkua sellaisenaan ole olemassa lääkärin kielenkäytön ja sen puitteet sanelevan institutionaalisen toiminnan ulkopuolella. Potilas muodostuu lääketieteelliseksi tapaukseksi kielenkäytössä, jolla tapaus esitetään. Siksi kuolintodistuksen kielenaineksetkin ovat monikasvoisesti performatiivisia, esittämänsä asiaintilan synnyttävää kielenkäyttöä. Kuolintodistuksille on tyypillistä itsenäisiin partisiippeihin ja verbittömään konstruointiin perustuva kerronta. Finiittiverbeistä käytetään preteritiä ja dramaattista preesensiä. Aktiivimuotoisella NUT-partisiipilla raportoidaan potilaan tilasta, passiivimuotoisella TU-partisiipilla sairaanhoitoinstituution toiminnasta. Koska liittotempukset eivät kuulu aineistoni keskeisiin kielenpiirteisiin, partisiippikerrontaa ei ole perusteltua tarkastella apuverbin ellipsioletuksesta käsin. Verbittömät rakenteet muistuttavat syntaktisia lausetyyppejä tai ovat vapaita NP:itä. Jos verbittömässä rakenteessa käytetään teonnimeä tai lääketieteen termiä, jolla on teonnimen merkitys, rakenne on funktioltaan lähellä dramaattista preesensiä: kertoo toiminnasta tai tapahtumasta eikä kiinnity kieliopillisesti menneeseen aikaan. Analyyseissa tulee esiin, että dramaattinen preesens ja verbitön konstruointi toimivat osana samaa kielellistä strategiaa. Molempia myös käytetään dramaattisen preesensin tyypillisessä esiintymisyhteydessä, kertomuksen käänteissä ja huipentumassa. Tutkielma tarjoaa tarkan kuvan etenkin dramaattisen preesensin funktioista kuolintodistuksessa. Esiintymisympäristönsä kokonaiskuvan mukaan se asettaa lääkärin toimijan tai tarkkailijan asemaan. Yksipersoonaisten passiivien ja eksplisiittisten performatiivien yhteydessä se kertoo yhteistyöhön perustuvasta institutionaalisesta toiminnasta. Preesensmuotoiset muuttumisjohdokset puolestaan siirtävät lääkärin toimijan roolista tarkkailijan asemaan ja esittävät potilaan tilanteen epäagentiivisena patienttina. Jos muuttumisjohdoksen yhteydessä on käytetty odotuksenvastaisen suhteen merkitsintä, lääkäri osoittaa yllättyneisyyttä tavasta, jolla kuolema etenee. Näin hän nostaa esiin kuoleman vallan ja yhden toimenkuvansa realiteeteista: hoitoinstituutio on sitoutunut potilaan auttamiseen, mutta vääjäämättömissä tilanteissa voi lääkärikin olla vain silminnäkijänä.

Patterns in permuted binary matrices

Reorganizing a dataset so that its hidden structure can be observed is useful in any data analysis task. For example, detecting a regularity in a dataset helps us to interpret the data, compress the data, and explain the processes behind the data. We study datasets that come in the form of binary matrices (tables with 0s and 1s). Our goal is to develop automatic methods that bring out certain patterns by permuting the rows and columns. We concentrate on the following patterns in binary matrices: consecutive-ones (C1P), simultaneous consecutive-ones (SC1P), nestedness, k-nestedness, and bandedness. These patterns reflect specific types of interplay and variation between the rows and columns, such as continuity and hierarchies. Furthermore, their combinatorial properties are interlinked, which helps us to develop the theory of binary matrices and efficient algorithms. Indeed, we can detect all these patterns in a binary matrix efficiently, that is, in polynomial time in the size of the matrix. Since real-world datasets often contain noise and errors, we rarely witness perfect patterns. Therefore we also need to assess how far an input matrix is from a pattern: we count the number of flips (from 0s to 1s or vice versa) needed to bring out the perfect pattern in the matrix. Unfortunately, for most patterns it is an NP-complete problem to find the minimum distance to a matrix that has the perfect pattern, which means that the existence of a polynomial-time algorithm is unlikely. To find patterns in datasets with noise, we need methods that are noise-tolerant and work in practical time with large datasets. The theory of binary matrices gives rise to robust heuristics that have good performance with synthetic data and discover easily interpretable structures in real-world datasets: dialectical variation in the spoken Finnish language, division of European locations by the hierarchies found in mammal occurrences, and co-occuring groups in network data. In addition to determining the distance from a dataset to a pattern, we need to determine whether the pattern is significant or a mere occurrence of a random chance. To this end, we use significance testing: we deem a dataset significant if it appears exceptional when compared to datasets generated from a certain null hypothesis. After detecting a significant pattern in a dataset, it is up to domain experts to interpret the results in the terms of the application.

Planar subgraphs without low-degree nodes

We study the following problem: given a geometric graph G and an integer k, determine if G has a planar spanning subgraph (with the original embedding and straight-line edges) such that all nodes have degree at least k. If G is a unit disk graph, the problem is trivial to solve for k = 1. We show that even the slightest deviation from the trivial case (e.g., quasi unit disk graphs or k = 1) leads to NP-hard problems.