The work covered in this thesis concerns automatic analysis of correctness of parallel programs running under relaxed memory models. When a parallel program is compiled and executed on a modern architecture, various optimizations may cause it to behave in unexpected ways. In particular, accesses to the shared memory may appear in the execution in the opposite order to how they appear in the control flow of the original program source code. The memory model determines which memory accesses can be reordered in a program on a given system. Any memory model that allows some observable memory access reordering is called a relaxed memory model. The reorderings may cause bugs and make the production of parallel programs more difficult. In this work, we consider three main approaches to analysis of correctness of programs running under relaxed memory models. An exact analysis for finite state programs running under the TSO memory model (Paper I). This technique is based on the well quasi ordering framework. An over-approximate analysis for integer programs running under TSO (Paper II), based on predicate abstraction combined with a buffer abstraction. Two under-approximate analysis techniques for programs running under the TSO, PSO or POWER memory models (Papers III and IV). The latter two techniques are based on stateless model checking and dynamic partial order reduction. In addition to determining whether a program is correct under a given memory model, the problem of automatic fence synthesis is also considered. A memory fence is an instruction that can be inserted into a program in order to locally disable some memory access reorderings. The fence synthesis problem is the problem of automatically inferring a minimal set of memory fences which restores sufficient order in a given program to ensure its correctness. / UPMARC

A polarization-independent electro-optically tunable add/drop filter utilizing non-polarizing novel relaxed beam splitters has been developed in LiNbO3 at the 1.55μm wavelength regime. The operation of this filter is based on passive directional coupler type beam splitters and strain-induced phase-matched TE↔TM polarization mode converters on an asymmetric Mach-Zehnder interferometer waveguide configuration. Fabrication parameters for channel waveguides, relaxed beam splitters and polarization mode converters were optimized individually then integrated to produce the final device. Single mode channel waveguides for both TE and TM polarizations were realized by the diffusion of 7μm wide Ti strips into LiNbO3 substrate. Relaxed beam splitters were produced using Ti diffused waveguides in a directional coupler configuration with 3.5mm long coupling region, 0.6º bending angle, and separation gap of 11μm and 13μm between waveguides. Tunable TE↔TM polarization mode converters with 99.8%

A polarization-independent electro-optically tunable add/drop filter utilizing non-polarizing novel relaxed beam splitters has been developed in LiNbO3 at the 1.55μm wavelength regime. The operation of this filter is based on passive directional coupler type beam splitters and strain-induced phase-matched TE↔TM polarization mode converters on an asymmetric Mach-Zehnder interferometer waveguide configuration. Fabrication parameters for channel waveguides, relaxed beam splitters and polarization mode converters were optimized individually then integrated to produce the final device. Single mode channel waveguides for both TE and TM polarizations were realized by the diffusion of 7μm wide Ti strips into LiNbO3 substrate. Relaxed beam splitters were produced using Ti diffused waveguides in a directional coupler configuration with 3.5mm long coupling region, 0.6º bending angle, and separation gap of 11μm and 13μm between waveguides. Tunable TE↔TM polarization mode converters with 99.8%

Many hardware and compiler optimisations introduced to speed up single-threaded programs also introduce additional, sometimes surprising, behaviours for concurrent programs with shared mutable state. How many of these extra behaviours occur in practice depends on the combination of the hardware, compiler, runtime, etc. that make up the platform. A memory model, which prescribes what values each read of a concurrent program can read, allows programmers to determine whether a program behaves as expected without having to worry about the details of the platform. However, capturing these behaviours in a memory model without also including undesirable "out-of-thin-air" behaviours that do not occur in practice has proved elusive. The memory model of C and C++ allows out-of-thin-air behaviour, while the Java memory model fails to capture some behaviours that are introduced in practice by compiler optimisations. In this thesis, we propose a memory model that forbids out-of-thin-air behaviour, yet allows the behaviours that do occur. Our memory model follows operational intuitions of how the hardware and compilers operate. We illustrate that it behaves as desired on a series of litmus tests. We show that it captures at least some of the expected behaviours, that it forms an envelope around some common compiler optimisations, and that it is implementable on common hardware using the expected compilation schemes. We also show that it supports some established programming idioms.

This thesis critically assesses ‘relaxed realism’ – a group of views that have entered the metaethical debate recently (Dworkin, 1996; Kramer, 2009; Parfit, 2011; Scanlon, 2014). Relaxed realism promises a novel perspective on our normative practice. In particular, it aims for a view that is genuinely distinct from traditional non-naturalism on the one hand, and sophisticated forms of expressivism on the other. This thesis calls into question whether such an aspiration can be met. The approach is twofold. First, the thesis argues that relaxed realism can meet various of its objectives better by relying on theoretical resources that expressivism offers. To argue for this claim, it discusses three challenges that relaxed realism should be able to meet according to its own objectives. With regards to each challenge, it then shows that as it stands relaxed realist views fail to adequately respond to it. Finally, the thesis suggests that relaxed realism can better respond to the respective challenges – and hence, better meet their own objectives – by endorsing certain expressivist resources. Second, the thesis argues that relaxed realism is an inherently unstable view. It does so by raising a dilemma. Either relaxed realism fails to establish the desired difference to expressivism or it succeeds, but at the expense of erasing the difference to traditional non-naturalism. The conclusion of the thesis is critical: the relaxed realist aspiration for a novel take on our normative practice – distinct from both traditional non-naturalism and expressivism – remains unmet.

Tato práce se zabývá různými charakteristikami komponovaných dokumentů a ukazuje potencionální výhody využití takových dokumentů v prostředí dnešního Webu. Hlavní pozornost je soustředěna na problémy spojené s validací komponovaných dokumentů. Práce zkoumá různé přístupy k řešení těchto problémů. Validační metoda NVDL (Namespace-based Validation Dispatching Language) je popsána detailně. Tato práce popisuje hlavní principy NVDL, zkoumá výhody a nevýhody oproti jiným přístupům a představuje JNVDL. JNVDL je kompletní implementace specifikace NVDL, která byla napsána v jazyce Java jako součást této práce. Popsány jsou nejen technické prvky implementace, ale JNVDL je představeno i z uživatelské perspektivy. Pro ověření využitelnosti bylo JNVDL integrováno do existujícího projektu pro validaci webových dokumentů s názvem Relaxed, aby jednoduše zpřístupnilo validaci komponovaných dokumentů autorům webového obsahu.

This thesis discusses graph marking game and graph colouring game. Suppose G=(V, E) is a graph. A marking game on G is played by two players, Alice and Bob, with Alice playing first. At the start of the game all vertices are unmarked. A play by either player consists of marking an unmarked vertex. The game ends when all vertices are marked. For each vertex v of G, write t(v)=j if v is marked at the jth step. Let s(v) denote the number of neighbours u of v for which t(u) < t(v), i.e., u is marked before v. The score of the game is $$s = 1+ max_{v in V} s(v).$$ Alice's goal is to minimize the score, while Bob's goal is to maximize it. The game colouring number colg(G) of G is the least s such that Alice has a strategy that results in a score at most s. Suppose r geq 1, d geq 0 are integers. In an (r, d)-relaxed colouring game of G, two players, Alice and Bob, take turns colouring the vertices of G with colours from a set X of r colours, with Alice having the first move. A colour i is legal for an uncoloured vertex x (at a certain step) if after colouring x with colour i, the subgraph induced by vertices of colour i has maximum degree at most d. Each player can only colour an uncoloured vertex with a legal colour. Alice's goal is to have all the vertices coloured, and Bob's goal is the opposite: to have an uncoloured vertex without legal colour. The d-relaxed game chromatic number of a graph G, denoted by $chi_g^{(d)}(G)$ is the least number r so that when playing the (r, d)-relaxed colouring game on G, Alice has a winning strategy. If d=0, then the parameter is called the game chromatic number of G and is also denoted by $chi_g(G)$. This thesis obtains upper and lower bounds for the game colouring number and relaxed game chromatic number of various classes of graphs. Let colg(PT_k) and colg(P) denote the maximum game colouring number of partial k trees and the maximum game colouring number of planar graphs, respectively. In this thesis, we prove that colg(PT_k) = 3k+2 and colg(P) geq 11. We also prove that the game colouring number colg(G) of a graph is a monotone parameter, i.e., if H is a subgraph of G, then colg(H) leq colg(G). For relaxed game chromatic number of graphs, this thesis proves that if G is an outerplanar graph, then $chi_g^{(d)}(G) leq 7-t$ for $t= 2, 3, 4$, for $d geq t$, and $chi_g^{(d)}(G) leq 2$ for $d geq 6$. In particular, the maximum $4$-relaxed game chromatic number of outerplanar graphs is equal to $3$. If $G$ is a tree then $chi_ g^{(d)}(G) leq 2$ for $d geq 2$.

In dynamic P2P networks, nodes join and depart from the system frequently, which partially damages the predefined P2P structure, and impairs the system performance such as basic lookup functionality. Therefore stabilization process has to be done to restore the logical topology. This paper presents an approach to relax the requirement on routing tables to provide provably better stability than fixed structured P2P systems. We propose a relaxed Chord that keeps the O(logN) number of hops for greedy lookup, but it requires less stabilization overhead. It allows a tradeoff between lookup efficiency and structure flexibility without adding any overhead to the system. In the relaxed routing structure, each routing entry ("finger") of the node is allowed to vary within a set of values. Each node only needs to keep a certain number of fingers that point to nodes in its anchor set. This relaxation reduces the burden of state management of the node. The relaxed routing scheme provides an alternative structure other than randomized P2P and deterministic P2P, by relaxing on finger selection. It provides good flexibility and therefore extends the system functioning time. / Singapore-MIT Alliance (SMA)

This thesis presents inference for the multiple linear regression model Y = beta_1 x_1 + ... + beta_p x_p + e after model or variable selection, including prediction intervals for a future value of the response variable Y_f, and testing hypotheses with the bootstrap. If n is the sample size, most results are for n/p large, but prediction intervals are developed that may increase in average length slowly as p increases for fixed n if the model is sparse: k predictors have nonzero coefficients beta_i where n/k is large.

xi, 172 p. : ill. (some col.) / Accretion shock waves are present in many important astrophysical systems and have been a focus of research for decades. These investigations provide a large body of understanding as to the nature, characteristics, and evolutionary behaviors of accretion shock waves over a wide range of conditions. However, largely absent are investigations into the properties of accretion shock waves in the presence of strong magnetic fields. In such cases these strong magnetic fields can significantly alter the stability behaviors and evolution of the accretion shock wave through the production and propagation of magnetic waves as well as magnetically constrained advection. With strong magnetic fields likely found in a number of accretion shock systems, such as compact binary and protostellar systems, a better understanding of the behaviors of magnetic accretion shock waves is needed. A new magnetohydrodynamics simulation tool, IMOGEN, was developed to carry out an investigation of instabilities in strong, slow magnetic accretion shocks by modelling their long-term, nonlinear evolution. IMOGEN implements a relaxed, second-order, total variation diminishing, monotonic upwind scheme for conservation laws and incorporates a staggered-grid constrained transport scheme for magnetic advection. Through the simulated evolution of magnetic accretion shocks over a wide range of initial conditions, it has been shown, for sufficiently high magnetic field strengths, that magnetic accretion shocks are generally susceptible to corrugation instabilities, which arise in the presence of perturbations of the initial shock front. As these corrugation instabilities grow, they manifest as magnetic wave propagation in the upstream region of the accretion column, which propagate away from the accretion shock front, and as density columns, or fingers, that grow into the higher density downstream flow, defined and constrained by current loops created during the early evolution of the instability. / Committee in charge: Dr. James Schombert, Chair; Dr. James Imamura, Advisor; Dr. Alan Rempel, Member; Dr. John Toner, Member; Dr. Kent Stevens, Outside Member