Approximate linear time ML decoding on tail-biting trellises in two rounds

A linear time approximate maximum likelihood decoding algorithm on tail-biting trellises is presented, that requires exactly two rounds on the trellis. This is an adaptation of an algorithm proposed earlier with the advantage that it reduces the time complexity from O(m log m) to O(m) where m is the number of nodes in the tail-biting trellis. A necessary condition for the output of the algorithm to differ from the output of the ideal ML decoder is deduced and simulation results on an AWGN channel using tail-biting trellises for two rate 1/2 convolutional codes with memory 4 and 6 respectively, are reported.

Text localization and extraction from complex gray images

We propose two texture-based approaches, one involving Gabor filters and the other employing log-polar wavelets, for separating text from non-text elements in a document image. Both the proposed algorithms compute local energy at some information-rich points, which are marked by Harris' corner detector. The advantage of this approach is that the algorithm calculates the local energy at selected points and not throughout the image, thus saving a lot of computational time. The algorithm has been tested on a large set of scanned text pages and the results have been seen to be better than the results from the existing algorithms. Among the proposed schemes, the Gabor filter based scheme marginally outperforms the wavelet based scheme.

Hardness of approximation results for the problem of finding the stopping distance in Tanner graphs

Tanner Graph representation of linear block codes is widely used by iterative decoding algorithms for recovering data transmitted across a noisy communication channel from errors and erasures introduced by the channel. The stopping distance of a Tanner graph T for a binary linear block code C determines the number of erasures correctable using iterative decoding on the Tanner graph T when data is transmitted across a binary erasure channel using the code C. We show that the problem of finding the stopping distance of a Tanner graph is hard to approximate within any positive constant approximation ratio in polynomial time unless P = NP. It is also shown as a consequence that there can be no approximation algorithm for the problem achieving an approximation ratio of 2(log n)(1-epsilon) for any epsilon > 0 unless NP subset of DTIME(n(poly(log n))).

Document page layout analysis using Harris corner points

Extraction of text areas from the document images with complex content and layout is one of the challenging tasks. Few texture based techniques have already been proposed for extraction of such text blocks. Most of such techniques are greedy for computation time and hence are far from being realizable for real time implementation. In this work, we propose a modification to two of the existing texture based techniques to reduce the computation. This is accomplished with Harris corner detectors. The efficiency of these two textures based algorithms, one based on Gabor filters and other on log-polar wavelet signature, are compared. A combination of Gabor feature based texture classification performed on a smaller set of Harris corner detected points is observed to deliver the accuracy and efficiency.

Memory-based reasoning approach for pattern recognition of binary images

Template matching is concerned with measuring the similarity between patterns of two objects. This paper proposes a memory-based reasoning approach for pattern recognition of binary images with a large template set. It seems that memory-based reasoning intrinsically requires a large database. Moreover, some binary image recognition problems inherently need large template sets, such as the recognition of Chinese characters which needs thousands of templates. The proposed algorithm is based on the Connection Machine, which is the most massively parallel machine to date, using a multiresolution method to search for the matching template. The approach uses the pyramid data structure for the multiresolution representation of templates and the input image pattern. For a given binary image it scans the template pyramid searching the match. A binary image of N × N pixels can be matched in O(log N) time complexity by our algorithm and is independent of the number of templates. Implementation of the proposed scheme is described in detail.

Max-Coloring Paths: Tight Bounds and Extensions

The max-coloring problem is to compute a legal coloring of the vertices of a graph G = (V, E) with a non-negative weight function w on V such that Sigma(k)(i=1) max(v epsilon Ci) w(v(i)) is minimized, where C-1, ... , C-k are the various color classes. Max-coloring general graphs is as hard as the classical vertex coloring problem, a special case where vertices have unit weight. In fact, in some cases it can even be harder: for example, no polynomial time algorithm is known for max-coloring trees. In this paper we consider the problem of max-coloring paths and its generalization, max-coloring abroad class of trees and show it can be solved in time O(vertical bar V vertical bar+time for sorting the vertex weights). When vertex weights belong to R, we show a matching lower bound of Omega(vertical bar V vertical bar log vertical bar V vertical bar) in the algebraic computation tree model.

Epidemiology of candidemia in Finland

Candida species are an important cause of nosocomial bloodstream infections in hospitalized patients worldwide, with associated high mortality, excess length of stay and costs. Main contributors to candidemias is profound immunosuppression due to serious underlying condition or intensive treatments leading to an increasing number of susceptible patients. The rank order of causative Candida species varies over time and in different geographic locations. The aim of this study was to obtain information on epidemiology of candidemia in Finland, to identify trends in incidence, causative species, and patient populations at risk. In order to reveal possible outbreaks and assess the value of one molecular typing method, restriction enzyme analysis (REA), in epidemiological study, we analyzed C. albicans bloodstream isolates in Uusimaa region in Southern Finland during eight years. The data from the National Infectious Disease Register were used to assess the incidence and epidemiological features of candidemia cases. In Helsinki University Central Hospital (HUCH) all patients with blood culture yielding any Candida spp. were identified from laboratory log-books and from Finnish Hospital Infection Program. All the patients with a stored blood culture isolate of C. albicans were identified through microbiology laboratory logbooks, and stored isolates were genotyped with REA in the National Institute for Health and Welfare (former KTL). The incidence of candidemia in Finland is globally relatively low, but increased between between 1990s and 2000s. The incidence was highest in males >65 years of age, but incidence rates for patients <1-15 years were lower during 2000s than during 1990s. In HUCH the incidence of candidemia remained low and constant during our 18 years of observation, but a significant shift in patient-populations at risk was observed, associated with patients treated in intensive care units, such as premature neonates and surgical patients. The predominating causative species in Finland and in HUCH is C. albicans, but the proportion of C. glabrata increased considerably. The crude one-month case fatality was constantly high between 28-33%. REA differentiated efficiently between C. albicans blood culture isolates and no clusters were observed in the hospitals involved, despite of abundant transfer of patients among them. Candida spp. are an important cause of nosocomial blood stream infections in Finland, and continued surveillance is necessary to determine the overall trends and patient groups at risk, and reduce the impact of these infections in the future. Molecular methods provide an efficient tool for investigation of suspected outbreak and should be available in the future in Finland, also.

Maissin tuotantoon ja markkinoihin vaikuttavat tekijät Yhdysvalloissa 2000-luvulla

Tutkimus käsittelee maissin tuotantoon ja markkinoihin vaikuttavia tekijöitä Yhdysvalloissa 2000-luvulla. Yhdysvallat on maailman merkittävin maissin tuottaja. Aikaisemmin maissia on tuotettu suoraan tai välillisesti eläinten rehuna ihmisten ruuantuotannon tarpeisiin. 2000-luvulla maissin käyttö liikenteen polttoaineena käytettävän etanolin raaka-aineena on merkittävästi lisääntynyt. Samaan aikaan maissin hinta on noussut ennätyskorkeaksi. Tässä tutkimuksessa maissimarkkinoihin vaikuttavia tekijöitä tutkittiin ajankohtaisen viranomaistiedon, aiheeseen liittyvän aikaisemman tutkimuksen ja empiirisen ekonometrisen estimoinnin perusteella. Tutkimuksen teoreettinen viitekehys perustuu kysyntä- ja tarjontateoriaan. Lisäksi tässä tutkimuksessa on kerrottu Yhdysvaltojen maatalouspolitiikan lähihistoriasta ja tarkemmin tällä hetkellä rehuviljan tuotantoon vaikuttavasta maatalouspolitiikasta. Tutkimuksessa estimoitiin maissin tuottajien viljelypäätöksiin vaikuttavia tekijöitä käyttäen pienimmän neliösumman menetelmää. Viljelypäätöstä kuvaavaksi selitettäväksi muuttujaksi valittiin maissin viljelypinta-ala. Aineiston saatavuus rajasi tutkimuksen vuosiin 1987 – 2010. Viljelypinta-alaa selittäviä muuttujia valittiin 12. Muuttujien valinta perustui maissin tuotantoon liittyviin tekijöihin, joita on käytetty muissa alan tutkimuksissa ja joiden käyttöä voidaan perustella talousteorialla. Vähitellen kokeilemalla mallista karsittiin turhat muuttujat pois ja viljelypinta-alaa selittämään jäi maissin ja soijan viivästetty hintasuhde, viivästetty typpilannoitteen hinta, maissifutuurien ostomäärät sekä viivästetty etanolin tuotanto ja maissin muu teollinen käyttö. Paras ja luotettavin lineaarisella mallilla saatu tulos sai selitysasteeksi 0,85. Tässä mallissa molemmat kysyntää kuvaavat muuttujat olivat alle 1 % virhetasolla tilastollisesti merkitseviä. Alle 10 % virhetasolla tilastollisesti merkitseviä olivat myös maissin ja soijan hintasuhde samoin kuin futuuriostot. Samoilla muuttujilla testattu log-lineaarinen malli antoi tutkimuksen korkeimman selitysasteen 0,87. Selittävistä muuttujista etanolin tuotanto oli edelleen alle 1 % virhetasolla tilastollisesti merkitsevä. Sen sijaan maissin muun teollisen käytön merkitsevyys heikkeni, ollen kuitenkin alle 10 % virhetasolla tilastollisesti merkitsevä. Lannoitteen hinnan p-arvo laski, joten lannoitteen hinta oli nyt alle 5 % virhetasolla tilastollisesti merkitsevä samoin kuin futuuriostot. Log-lineaarinen malli paransi myös maissin ja soijan hintasuhteen merkitsevyyttä. Tutkimustulokset ovat loogisia ja vastaavat teoriaa ja muita tutkimuksia siltä osin, että maissin korkeampi hinta, maissin lisääntynyt kysyntä ja futuuriostot lisäävät maissin viljelypinta-alaa. Tulosten perusteella voi todeta maissin tuotantokustannusten nousun ja soijan hinnan nousun laskevan maissin viljelypinta-alaa. Tutkimuksen tuloksena saadut joustokertoimet ovat pieniä, mikä kertoo maissin viljelypinta-alan vaihtelujen olevan melko joustamattomia markkinoilla tapahtuviin muutoksiin nähden. Tästä voisi päätellä viljelijöiden tuotantopäätösten olevan melko riippumattomia markkinoiden muutoksista. Tämä voi selittyä maatalouspolitiikan luomalla vahvalla turvaverkolla, rajoitteilla ja kannustimilla.

Exact bounds for distributed graph colouring

A distributed system is a collection of networked autonomous processing units which must work in a cooperative manner. Currently, large-scale distributed systems, such as various telecommunication and computer networks, are abundant and used in a multitude of tasks. The field of distributed computing studies what can be computed efficiently in such systems. Distributed systems are usually modelled as graphs where nodes represent the processors and edges denote communication links between processors. This thesis concentrates on the computational complexity of the distributed graph colouring problem. The objective of the graph colouring problem is to assign a colour to each node in such a way that no two nodes connected by an edge share the same colour. In particular, it is often desirable to use only a small number of colours. This task is a fundamental symmetry-breaking primitive in various distributed algorithms. A graph that has been coloured in this manner using at most k different colours is said to be k-coloured. This work examines the synchronous message-passing model of distributed computation: every node runs the same algorithm, and the system operates in discrete synchronous communication rounds. During each round, a node can communicate with its neighbours and perform local computation. In this model, the time complexity of a problem is the number of synchronous communication rounds required to solve the problem. It is known that 3-colouring any k-coloured directed cycle requires at least ½(log* k - 3) communication rounds and is possible in ½(log* k + 7) communication rounds for all k ≥ 3. This work shows that for any k ≥ 3, colouring a k-coloured directed cycle with at most three colours is possible in ½(log* k + 3) rounds. In contrast, it is also shown that for some values of k, colouring a directed cycle with at most three colours requires at least ½(log* k + 1) communication rounds. Furthermore, in the case of directed rooted trees, reducing a k-colouring into a 3-colouring requires at least log* k + 1 rounds for some k and possible in log* k + 3 rounds for all k ≥ 3. The new positive and negative results are derived using computational methods, as the existence of distributed colouring algorithms corresponds to the colourability of so-called neighbourhood graphs. The colourability of these graphs is analysed using Boolean satisfiability (SAT) solvers. Finally, this thesis shows that similar methods are applicable in capturing the existence of distributed algorithms for other graph problems, such as the maximal matching problem.

Development of foreign direct investment in Finland

During 1990 to 2009, Foreign Direct Investment (FDI henceforth) in Finland has fluctuated greatly. This paper focused on analyzing the overall development and basic characteristics of Foreign Direct Investment in Finland, covering the period from 1990 to present. By comparing FDI in Finland with FDI in other countries, the picture of Finland’s FDI position in the world market is clearer. A lot of statistical data, tables and figures are used to describe the trend of Foreign Direct Investment in Finland. All the data used in this study were obtained from Statistics Finland, UNCTAD, OECD, World Bank and International Labor Office, Investment map website and etc. It is also found that there is a big, long-lasting and increasing imbalance of the inward FDI and outward FDI in Finland, the performance of outward FDI is stronger than the inward FDI in Finland. Finland’s position of FDI in the world is rather modest. And based on existing theories, I tried to analyze the factors that might determine the size of the inflows of FDI in Finland. The econometric model of my thesis is based on time series data ranging from 1990 to 2007. A Log linear regression model is adopted to analyze the impact of each variable. The regression results showed that Labor Cost and Investment in Education have a negative influence on the FDI inflows into Finland. Too high labor cost is the main impediment of FDI in Finland, explaining the relative small size of FDI inflows into Finland. GDP and Economy openness have a significant positive impact on the inflows of FDI into Finland; other variables do not emerge as significant factor in affecting the size of FDI inflows in Finland as expected. Meanwhile, the impacts of the most recent financial and economic crisis on FDI in the world and in Finland are discussed as well. FDI inflows worldwide and in Finland have suffered from a big setback from the 2008 global crisis. The economic crisis has undoubtedly significant negative influence on the FDI flows in the world and in Finland. Nevertheless, apart from the negative impact, the crisis itself also brings in chances for policymakers to implement more efficient policies in order to create a pro-business and pro-investment climate for the recovery of FDI inflows. . The correspondent policies and measures aiming to accelerate the recovery of the falling FDI were discussed correspondently.

Sarveiskalvon permeabiliteetin ennustaminen QSPR-mallin avulla

QSPR-malli kuvaa kvantitatiivista riippuvuutta muuttujien ja biologisen ominaisuuden välillä. Näin ollen QSPR mallit ovat käyttökelpoisia lääkekehityksen apuvälineitä. Kirjallisessa osassa kerrotaan sarveiskalvon, suoliston ja veriaivoesteen permeabiliteetin malleista. Useimmin käytettyjä muuttujia ovat yhdisteen rasvaliukoisuus, polaarinen pinta-ala, vetysidosten muodostuminen ja varaus. Myös yhdisteen koko vaikuttaa läpäisevyyteen, vaikka tutkimuksissa onkin erilaista tietoa tämän merkittävyydestä. Malliin vaikuttaa myös muiden kuin mallissa mukana olevien muuttujien suuruusluokka esimerkkinä Lipinskin ‖rule of 5‖ luokittelu. Tässä luokittelussa yhdisteen ominaisuus ei saa ylittää tiettyjä raja-arvoja. Muussa tapauksessa sen imeytyminen suun kautta otettuna todennäköisesti vaarantuu. Lisäksi kirjallisessa osassa tutustuttiin kuljetinproteiineihin ja niiden toimintaan silmän sarveiskalvossa, suolistossa ja veriaivoesteessä. Nykyisin on kehitetty erilaisia QSAR-malleja kuljetinproteiineille ennustamaan mahdollisten substraatittien tai inhibiittorien vuorovaikutuksia kuljetinproteiinin kanssa. Kokeellisen osan tarkoitus oli rakentaa in silico -malli sarveiskalvon passiiviselle permeabiliteetille. Työssä tehtiin QSPR-malli 54 yhdisteen ACDLabs-ohjelmalla laskettujen muuttujien arvojen avulla. Permeabiliteettikertoimien arvot saatiin kirjallisuudesta kanin sarveiskalvon läpäisevyystutkimuksista. Lopullisen mallin muuttujina käytettiin oktanoli-vesijakaantumiskerrointa (logD) pH:ssa 7,4 ja vetysidosatomien kokonaismäärää. Yhtälö oli muotoa log10(permeabiliteettikerroin) = -3,96791 - 0,177842Htotal + 0,311963logD(pH7,4). R2-korrelaatiokerroin oli 0,77 ja Q2-korrelaatiokerroin oli 0,75. Lopullisen mallin hyvyyttä arvioitiin 15 yhdisteen ulkoisella testijoukolla, jolloin ennustettua permeabiliteettia verrattiin kokeelliseen permeabiliteettiin. QSPR-malli arvioitiin myös farmakokineettisen simulaation avulla. Simulaatiossa laskettiin seitsemän yhdisteen kammionestepitoisuudet in vivo vakaassa tilassa käyttäen simulaatioissa QSPR mallilla ennustettuja permeabiliteettikertoimia. Lisäksi laskettiin sarveiskalvon imeytymisen nopeusvakio (Kc) 13 yhdisteelle farmakokineettisen simulaation avulla ja verrattiin tätä lopullisella mallilla ennustettuun permeabiliteettiin. Tulosten perusteella saatiin tilastollisesti hyvä QSPR-malli kuvaamaan sarveiskalvon passiivista permeabiliteettia, jolloin tätä mallia voidaan käyttää lääkekehityksen alkuvaiheessa. QSPR-malli ennusti permeabiliteettikertoimet hyvin, mikä nähtiin vertaamalla mallilla ennustettuja arvoja kokeellisiin tuloksiin. Lisäksi yhdisteiden kammionestepitoisuudet voitiin simuloida käyttäen apuna QSPR-mallilla ennustettuja permeabiliteettikertoimien arvoja.

Estimation of cutting volume with three inventory methods for harvest planning in Canadian boreal forests.

Two methods of pre-harvest inventory were designed and tested on three cutting sites containing a total of 197 500 m3 of wood. These sites were located on flat-ground boreal forests located in northwestern Quebec. Both methods studied involved scaling of trees harvested to clear the road path one year (or more) prior to harvest of adjacent cut-blocks. The first method (ROAD) considers the total road right-of-way volume divided by the total road area cleared. The resulting volume per hectare is then multiplied by the total cut-block area scheduled for harvest during the following year to obtain the total estimated cutting volume. The second method (STRATIFIED) also involves scaling of trees cleared from the road. However, in STRATIFIED, log scaling data are stratified by forest stand location. A volume per hectare is calculated for each stretch of road that crosses a single forest stand. This volume per hectare is then multiplied by the remaining area of the same forest stand scheduled for harvest one year later. The sum of all resulting estimated volumes per stand gives the total estimated cutting-volume for all cut-blocks adjacent to the studied road. A third method (MNR) was also used to estimate cut-volumes of the sites studied. This method represents the actual existing technique for estimating cutting volume in the province of Quebec. It involves summing the cut volume for all forest stands. The cut volume is estimated by multiplying the area of each stand by its estimated volume per hectare obtained from standard stock tables provided by the governement. The resulting total estimated volume per cut-block for all three methods was then compared with the actual measured cut-block volume (MEASURED). This analysis revealed a significant difference between MEASURED and MNR methods with the MNR volume estimate being 30 % higher than MEASURED. However, no significant difference from MEASURED was observed for volume estimates for the ROAD and STRATIFIED methods which respectively had estimated cutting volumes 19 % and 5 % lower than MEASURED. Thus the ROAD and STRATIFIED methods are good ways to estimate cut-block volumes after road right-of-way harvest for conditions similar to those examined in this study.

Criticality of the exponential rate of decay for the largest nearest-neighbor link in random geometric graphs

Let n points be placed independently in d-dimensional space according to the density f(x) = A(d)e(-lambda parallel to x parallel to alpha), lambda, alpha > 0, x is an element of R-d, d >= 2. Let d(n) be the longest edge length of the nearest-neighbor graph on these points. We show that (lambda(-1) log n)(1-1/alpha) d(n) - b(n) converges weakly to the Gumbel distribution, where b(n) similar to ((d - 1)/lambda alpha) log log n. We also prove the following strong law for the normalized nearest-neighbor distance (d) over tilde (n) = (lambda(-1) log n)(1-1/alpha) d(n)/log log n: (d - 1)/alpha lambda <= lim inf(n ->infinity) (d) over tilde (n) <= lim sup(n ->infinity) (d) over tilde (n) <= d/alpha lambda almost surely. Thus, the exponential rate of decay alpha = 1 is critical, in the sense that, for alpha > 1, d(n) -> 0, whereas, for alpha <= 1, d(n) -> infinity almost surely as n -> infinity.

Disorder-driven electronic localization and phase separation in superconducting Fe1+yTe0.5Se0.5 single crystals

We have investigated the influence of Fe excess on the electrical transport and magnetism of Fe1+yTe0.5Se0.5 (y=0.04 and 0.09) single crystals. Both compositions exhibit resistively determined superconducting transitions (T-c) with an onset temperature of about 15 K. From the width of the superconducting transition and the magnitude of the lower critical field H-c1, it is inferred that excess of Fe suppresses superconductivity. The linear and nonlinear responses of the ac susceptibility show that the superconducting state for these compositions is inhomogeneous. A possible origin of this phase separation is a magnetic coupling between Fe excess occupying interstitial sites in the chalcogen planes and those in the Fe-square lattice. The temperature derivative of the resistivity d(rho)/d(T) in the temperature range T-c < T < T-a with T-a being the temperature of a magnetic anomaly, changes from positive to negative with increasing Fe. A log 1/T divergence of the resistivity above T-c in the sample with higher amount of Fe suggests a disorder-driven electronic localization.

Bayesian Analysis of a Superimposed Renewal Process

Stochastic behavior of an aero-engine failure/repair process has been analyzed from a Bayesian perspective. Number of failures/repairs in the component-sockets of this multi-component system are assumed to follow independent renewal processes with Weibull inter-arrival times. Based on the field failure/repair data of a large number of such engines and independent Gamma priors on the scale parameters and log-concave priors on the shape parameters, an exact method of sampling from the resulting posterior distributions of the parameters has been proposed. These generated parameter values are next utilised in obtaining the posteriors of the expected number of system repairs, system failure rate, and the conditional intensity function, which are computed using a recursive formula.