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).

An improved iterative finite element solution for pin joints

Accurate, reliable and economical methods of determining stress distributions are important for fastener joints. In the past the contact stress problems in these mechanically fastened joints using interference or push or clearance fit pins were solved using both inverse and iterative techniques. Inverse techniques were found to be most efficient, but at times inadequate in the presence of asymmetries. Iterative techniques based on the finite element method of analysis have wider applications, but they have the major drawbacks of being expensive and time-consuming. In this paper an improved finite element technique for iteration is presented to overcome these drawbacks. The improved iterative technique employs a frontal solver for elimination of variables not requiring iteration, by creation of a dummy element. This automatically results in a large reduction in computer time and in the size of the problem to be handled during iteration. Numerical results are compared with those available in the literature. The method is used to study an eccentrically located pin in a quasi-isotropic laminated plate under uniform tension.

Cohésion modale et subordination : Le conditionnel et le jussif finnois au miroir de la valeur sémantique et discursive du subjonctif français

Modal cohesion and subordination. The Finnish conditional and jussive moods in comparison to the French subjunctive This study examines verb moods in subordinate clauses in French and Finnish. The first part of the analysis deals with the syntax and semantics of the French subjunctive, mood occurring mostly in subordinate positions. The second part investigates Finnish verb moods. Although subordinate positions in Finnish grammar have no special finite verb form, certain uses of Finnish verb moods have been compared to those of subjunctives and conjunctives in other languages. The present study focuses on the subordinate uses of the Finnish conditional and jussive (i.e. the third person singular and plural of the imperative mood). The third part of the analysis discusses the functions of subordinate moods in contexts beyond complex sentences. The data used for the analysis include 1834 complex sentences gathered from newspapers, online discussion groups and blog texts, as well as audio-recorded interviews and conversations. The data thus consist of both written and oral texts as well as standard and non-standard variants. The analysis shows that the French subjunctive codes theoretical modality. The subjunctive does not determine the temporal and modal meaning of the event, but displays the event as virtual. In a complex sentence, the main clause determines the temporal and modal space within which the event coded by the subjunctive clause is interpreted. The subjunctive explicitly indicates that the space constructed in the main clause extends its scope over the subordinate clause. The subjunctive can therefore serve as a means for creating modal cohesion in the discourse. The Finnish conditional shares the function of making explicit the modal link between the components of a complex construction with the French subjunctive, but the two moods differ in their semantics. The conditional codes future time and can therefore occur only in non-factual or counterfactual contexts, whereas the event expressed by French subjunctive clauses can also be interpreted as realized. Such is the case when, for instance, generic and habitual meaning is involved. The Finnish jussive mood is used in a relatively limited number of subordinate clause types, but in these contexts its modal meaning is strikingly close to that of the French subjunctive. The permissive meaning, typical of the jussive in main clause positions, is modified in complex sentences so that it entails inter-clausal relation, namely concession. Like the French subjunctive, the jussive codes theoretical modal meaning with no implication of the truth value of the proposition. Finally, the analysis shows that verb moods mark modal cohesion, not only on the syntagmatic level (namely in complexe sentences), but also on the paradigmatic axis of discourse in order to create semantic links over entire segments of talk. In this study, the subjunctive thus appears, not as an empty category without function, as it is sometimes described, but as an open form that conveys the temporal and modal meanings emerging from the context.

Analysis of reflection characteristics of a normal incidence plane wave on resonant sound absorbers: A finite element approach

Resonant sound absorbers are used widely as anechoic coatings in underwater applications. In this paper a finite element scheme based on the Galerkin technique is used to analyze the reflection characteristics of the resonant absorber when insonified by a normal incidence plane wave. A waveguide theory coupled with an impedance matching condition in the fluid is used to model the problem. It is shown in this paper that the fluid medium encompassing the absorber can be modeled as an elastic medium with equivalent Lamé constants. Quarter symmetry conditions within the periodic unit cell are exploited. The finite element results are compared with analytical results, and with results published elsewhere in the literature. It is shown in the process that meshing of the fluid domain can be obviated if the transmission coefficients or reflection coefficients only are desired as is often the case. Finally, some design curves for thin resonant absorbers with water closure are presented in this paper.

Analysis of the evanescent field coupling between a fiber and a planar waveguide using the explicit finite difference method with a nonuniform mesh (Journal Paper)

We investigate an optical waveguide system consisting of an unclad fiber core suspended at a constant distance parallel to the surface of a planar waveguide. The coupling and propagation of light in the combined system is studied using the three-dimensional explicit finite difference beam propagation method with a nonuniform mesh configuration. The power loss in the fiber and the field distribution in the waveguide are studied as a function of various parameters, such as index changes, index profile, and propagation distance, for the combined system.

Dynamic response of a beam on elastic foundation of finite depth under a moving force

In this paper, dynamic response of an infinitely long beam resting on a foundation of finite depth, under a moving force is studied. The effect of foundation inertia is included in the analysis by modelling the foundation as a series of closely spaced axially vibrating rods of finite depth, fixed at the bottom and connected to the beam at the top. Viscous damping in the beam and foundation is included in the analysis. Steady state response of the beam-foundation system is obtained. Detailed numerical results are presented to study the effect of various parameters such as foundation mass, velocity of the moving load, damping and axial force on the beam. It is shown that foundation inertia can considerably reduce the critical velocity and can also amplify the beam response.

Finite element estimation of elastic interlaminar stresses in laminates

Low interlaminar strength and the consequent possibility of interlaminar failures in composite laminates demand an examination of interlaminar stresses and/or strains to ensure their satisfactory performance. As a first approximation, these stresses can be obtained from thickness-wise integration of ply equilibrium equations using in-plane stresses from the classical laminated plate theory. Implementation of this approach in the finite element form requires evaluation of third and fourth order derivatives of the displacement functions in an element. Hence, a high precision element developed by Jayachandrabose and Kirkhope (1985) is used here and the required derivatives are obtained in two ways. (i) from direct differentiation of element shape functions; and (ii) by adapting a finite difference technique applied to the nodal strains and curvatures obtained from the finite element analysis. Numerical results obtained for a three-layered symmetric and a two-layered asymmetric laminate show that the second scheme is quite effective compared to the first scheme particularly for the case of asymmetric laminates.

Water Management in Cambodia Resources and Relations

In Cambodia, water has a special purpose as a source of life and livelihoods. Along with agriculture, fishing and forest use, industry, hydropower, navigation and tourism compete for the water resources. When rights and responsibilities related to essential and movable water are unclear, conflicts emerge easily. Therefore, water management is needed in order to plan and control the use of water resources. The international context is characterized by the Mekong River that flows through six countries. All of the countries by the river have very different roles and interests already depending on their geographical location. At the same time, water is also a tool for cooperation and peace. Locally, the water resources and related livelihoods create base for well-being, for economical and human resources in particular. They in turn are essential for the local people to participate and defend their rights to water use. They also help to construct the resource base of the state administration. Cambodia is highly dependent on the Mekong River. However, Cambodia has a volatile history whose effects can be seen for example in population structure, once suspended public institutions and weakened trust in the society. Relatively stable conditions came to the country as late as in the 1990s, therefore Cambodia for example has a weak status within the Mekong countries. This Master s thesis forms international, national and local interest groups of water use and analyzes their power relations and resources to affect water management. The state is seen as the salient actor as it has the formal responsibility of the water resources and of the coordination between the actions of different levels. In terms of water use this study focuses on production, in management on planning and in power relations on the resources. Water resources of Cambodia are seen consisting of the Mekong River and Tonle Sap Lake and the time span of the study is between the years 1991 and 2006. The material consists of semi-structured interviews collected during summer 2006 in Finland and in Cambodia as well as of literature and earlier studies. The results of the study show that the central state has difficulties to coordinate the actions of different actors because of its resource deficit and internal conflicts. The lessons of history and the vested interests of the actors of the state make it difficult to plan and to strengthen legislation. It seems that the most needed resources at the central state level are intangible as at the village level instead, the tangible resources (fulfilling the basic needs) are primarily important. The local decision-making bodies, NGOs and private sector mainly require legislation and legitimacy to support their role. However, the civil society and the international supporters are active and there are possibilities for new cooperation networks. Keywords: Water management, resources, participation, Cambodia, Mekong

Nonlinear finite element analysis of reinforced concrete corbel

Reinforced concrete corbels have been analysed using the nonlinear finite element method. An elasto-plastic-cracking constitutive formulation using Huber-Hencky-Mises yield surface augmented with a tension cut-off is employed. Smeared-fixed cracking with mesh-dependent strain softening is employed to obtain objective results. Multiple non-orthogonal cracking and opening and closing of cracks are permitted. The model and the formulation are verified with respect to available numerical solution for an RC corbel. Results of analyses of nine reinforced concrete corbels are presented and compared with experimental results. Nonlinear finite element analysis of reinforced concrete structures is shown to be a complement and also a feasible alternative to laboratory testing.

Part-of-Speech Tagging using Parallel Weighted Finite-State Transducers

We use parallel weighted finite-state transducers to implement a part-of-speech tagger, which obtains state-of-the-art accuracy when used to tag the Europarl corpora for Finnish, Swedish and English. Our system consists of a weighted lexicon and a guesser combined with a bigram model factored into two weighted transducers. We use both lemmas and tag sequences in the bigram model, which guarantees reliable bigram estimates.

Finite-State Spell-Checking with Weighted Language and Error Models

In this paper we present simple methods for construction and evaluation of finite-state spell-checking tools using an existing finite-state lexical automaton, freely available finite-state tools and Internet corpora acquired from projects such as Wikipedia. As an example, we use a freely available open-source implementation of Finnish morphology, made with traditional finite-state morphology tools, and demonstrate rapid building of Northern Sámi and English spell checkers from tools and resources available from the Internet.

Building and Using Existing Hunspell Dictionaries and TEX Hyphenators as Finite-State Automata

There are numerous formats for writing spellcheckers for open-source systems and there are many descriptions for languages written in these formats. Similarly, for word hyphenation by computer there are TEX rules for many languages. In this paper we demonstrate a method for converting these spell-checking lexicons and hyphenation rule sets into finite-state automata, and present a new finite-state based system for writer’s tools used in current open-source software such as Firefox, OpenOffice.org and enchant via the spell-checking library voikko.