Information sets and partial permutation decoding for codes from finite geometries

Mavron, Vassili; McDonough, T.P.; Key, J.D., (2006) 'Information sets and partial permutation decoding for codes from finite geometries', Finite Fields and their applications 12(2) pp.232-247 RAE2008

Geometric sensitivity of patient-specific finite element models of the spine to variability in user-selected anatomical landmarks

Software to create individualised finite element (FE) models of the osseoligamentous spine using pre-operative computed tomography (CT) data-sets for spinal surgery patients has recently been developed. This study presents a geometric sensitivity analysis of this software to assess the effect of intra-observer variability in user-selected anatomical landmarks. User-selected landmarks on the osseous anatomy were defined from CT data-sets for three scoliosis patients and these landmarks were used to reconstruct patient-specific anatomy of the spine and ribcage using parametric descriptions. The intra-observer errors in landmark co-ordinates for these anatomical landmarks were calculated. FE models of the spine and ribcage were created using the reconstructed anatomy for each patient and these models were analysed for a loadcase simulating clinical flexibility assessment. The intra-observer error in the anatomical measurements was low in comparison to the initial dimensions, with the exception of the angular measurements for disc wedge and zygapophyseal joint (z-joint) orientation and disc height. This variability suggested that CT resolution may influence such angular measurements, particularly for small anatomical features, such as the z-joints, and may also affect disc height. The results of the FE analysis showed low variation in the model predictions for spinal curvature with the mean intra-observer variability substantially less than the accepted error in clinical measurement. These findings demonstrate that intra-observer variability in landmark point selection has minimal effect on the subsequent FE predictions for a clinical loadcase.

On Games on Non-Wellfounded Sets and Stationary Sets

In this thesis we study a few games related to non-wellfounded and stationary sets. Games have turned out to be an important tool in mathematical logic ranging from semantic games defining the truth of a sentence in a given logic to for example games on real numbers whose determinacies have important effects on the consistency of certain large cardinal assumptions. The equality of non-wellfounded sets can be determined by a so called bisimulation game already used to identify processes in theoretical computer science and possible world models for modal logic. Here we present a game to classify non-wellfounded sets according to their branching structure. We also study games on stationary sets moving back to classical wellfounded set theory. We also describe a way to approximate non-wellfounded sets with hereditarily finite wellfounded sets. The framework used to do this is domain theory. In the Banach-Mazur game, also called the ideal game, the players play a descending sequence of stationary sets and the second player tries to keep their intersection stationary. The game is connected to precipitousness of the corresponding ideal. In the pressing down game first player plays regressive functions defined on stationary sets and the second player responds with a stationary set where the function is constant trying to keep the intersection stationary. This game has applications in model theory to the determinacy of the Ehrenfeucht-Fraisse game. We show that it is consistent that these games are not equivalent.

Parametrized actor-critic algorithms for finite-horizon MDPs

Due to their non-stationarity, finite-horizon Markov decision processes (FH-MDPs) have one probability transition matrix per stage. Thus the curse of dimensionality affects FH-MDPs more severely than infinite-horizon MDPs. We propose two parametrized 'actor-critic' algorithms to compute optimal policies for FH-MDPs. Both algorithms use the two-timescale stochastic approximation technique, thus simultaneously performing gradient search in the parametrized policy space (the 'actor') on a slower timescale and learning the policy gradient (the 'critic') via a faster recursion. This is in contrast to methods where critic recursions learn the cost-to-go proper. We show w.p 1 convergence to a set with the necessary condition for constrained optima. The proposed parameterization is for FHMDPs with compact action sets, although certain exceptions can be handled. Further, a third algorithm for stochastic control of stopping time processes is presented. We explain why current policy evaluation methods do not work as critic to the proposed actor recursion. Simulation results from flow-control in communication networks attest to the performance advantages of all three algorithms.

Playing Games on Sets and Models

The most prominent objective of the thesis is the development of the generalized descriptive set theory, as we call it. There, we study the space of all functions from a fixed uncountable cardinal to itself, or to a finite set of size two. These correspond to generalized notions of the universal Baire space (functions from natural numbers to themselves with the product topology) and the Cantor space (functions from natural numbers to the {0,1}-set) respectively. We generalize the notion of Borel sets in three different ways and study the corresponding Borel structures with the aims of generalizing classical theorems of descriptive set theory or providing counter examples. In particular we are interested in equivalence relations on these spaces and their Borel reducibility to each other. The last chapter shows, using game-theoretic techniques, that the order of Borel equivalence relations under Borel reduciblity has very high complexity. The techniques in the above described set theoretical side of the thesis include forcing, general topological notions such as meager sets and combinatorial games of infinite length. By coding uncountable models to functions, we are able to apply the understanding of the generalized descriptive set theory to the model theory of uncountable models. The links between the theorems of model theory (including Shelah's classification theory) and the theorems in pure set theory are provided using game theoretic techniques from Ehrenfeucht-Fraïssé games in model theory to cub-games in set theory. The bottom line of the research declairs that the descriptive (set theoretic) complexity of an isomorphism relation of a first-order definable model class goes in synch with the stability theoretical complexity of the corresponding first-order theory. The first chapter of the thesis has slightly different focus and is purely concerned with a certain modification of the well known Ehrenfeucht-Fraïssé games. There we (me and my supervisor Tapani Hyttinen) answer some natural questions about that game mainly concerning determinacy and its relation to the standard EF-game

Geometric Characterizations for Patterson-Sullivan Measures of Geometrically Finite Kleinian Groups

The main results of this thesis show that a Patterson-Sullivan measure of a non-elementary geometrically finite Kleinian group can always be characterized using geometric covering and packing constructions. This means that if the standard covering and packing constructions are modified in a suitable way, one can use either one of them to construct a geometric measure which is identical to the Patterson-Sullivan measure. The main results generalize and modify results of D. Sullivan which show that one can sometimes use the standard covering construction to construct a suitable geometric measure and sometimes the standard packing construction. Sullivan has shown also that neither or both of the standard constructions can be used to construct the geometric measure in some situations. The main modifications of the standard constructions are based on certain geometric properties of limit sets of Kleinian groups studied first by P. Tukia. These geometric properties describe how closely the limit set of a given Kleinian group resembles euclidean planes or spheres of varying dimension on small scales. The main idea is to express these geometric properties in a quantitative form which can be incorporated into the gauge functions used in the modified covering and packing constructions. Certain estimation results for general conformal measures of Kleinian groups play a crucial role in the proofs of the main results. These estimation results are generalizations and modifications of similar results considered, among others, by B. Stratmann, D. Sullivan, P. Tukia and S. Velani. The modified constructions are in general defined without reference to Kleinian groups, so they or their variants may prove useful in some other contexts in addition to that of Kleinian groups.

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.

Badly approximable numbers and vectors in Cantor-like sets

We show that a large class of Cantor-like sets of R-d, d >= 1, contains uncountably many badly approximable numbers, respectively badly approximable vectors, when d >= 2. An analogous result is also proved for subsets of R-d arising in the study of geodesic flows corresponding to (d+1)-dimensional manifolds of constant negative curvature and finite volume, generalizing the set of badly approximable numbers in R. Furthermore, we describe a condition on sets, which is fulfilled by a large class, ensuring a large intersection with these Cantor-like sets.

A numerical approach to determine the sufficiency of given boundary data sets for uniquely estimating interior elastic properties

We consider an inverse elasticity problem in which forces and displacements are known on the boundary and the material property distribution inside the body is to be found. In other words, we need to estimate the distribution of constitutive properties using the finite boundary data sets. Uniqueness of the solution to this problem is proved in the literature only under certain assumptions for a given complete Dirichlet-to-Neumann map. Another complication in the numerical solution of this problem is that the number of boundary data sets needed to establish uniqueness is not known even under the restricted cases where uniqueness is proved theoretically. In this paper, we present a numerical technique that can assess the sufficiency of given boundary data sets by computing the rank of a sensitivity matrix that arises in the Gauss-Newton method used to solve the problem. Numerical experiments are presented to illustrate the method.

Achievable rate region of gaussian broadcast channel with finite input alphabet and quantized output

In this paper, we study the achievable rate region of two-user Gaussian broadcast channel (GBC) when the messages to be transmitted to both the users take values from finite signal sets and the received signal is quantized at both the users. We refer to this channel as quantized broadcast channel (QBC). We first observe that the capacity region defined for a GBC does not carry over as such to QBC. Also, we show that the optimal decoding scheme for GBC (i.e., high SNR user doing successive decoding and low SNR user decoding its message alone) is not optimal for QBC. We then propose an achievable rate region for QBC based on two different schemes. We present achievable rate region results for the case of uniform quantization at the receivers. We find that rotation of one of the user's input alphabet with respect to the other user's alphabet marginally enlarges the achievable rate region of QBC when almost equal powers are allotted to both the users.

A Smooth Discretization Bridging Finite Element and Mesh-free Methods Using Polynomial Reproducing Simplex Splines

This work sets forth a `hybrid' discretization scheme utilizing bivariate simplex splines as kernels in a polynomial reproducing scheme constructed over a conventional Finite Element Method (FEM)-like domain discretization based on Delaunay triangulation. Careful construction of the simplex spline knotset ensures the success of the polynomial reproduction procedure at all points in the domain of interest, a significant advancement over its precursor, the DMS-FEM. The shape functions in the proposed method inherit the global continuity (Cp-1) and local supports of the simplex splines of degree p. In the proposed scheme, the triangles comprising the domain discretization also serve as background cells for numerical integration which here are near-aligned to the supports of the shape functions (and their intersections), thus considerably ameliorating an oft-cited source of inaccuracy in the numerical integration of mesh-free (MF) schemes. Numerical experiments show the proposed method requires lower order quadrature rules for accurate evaluation of integrals in the Galerkin weak form. Numerical demonstrations of optimal convergence rates for a few test cases are given and the method is also implemented to compute crack-tip fields in a gradient-enhanced elasticity model.

Asymptotic behavior and interpretation of virtual states: The effects of confinement and of basis sets

A real-space high order finite difference method is used to analyze the effect of spherical domain size on the Hartree-Fock (and density functional theory) virtual eigenstates. We show the domain size dependence of both positive and negative virtual eigenvalues of the Hartree-Fock equations for small molecules. We demonstrate that positive states behave like a particle in spherical well and show how they approach zero. For the negative eigenstates, we show that large domains are needed to get the correct eigenvalues. We compare our results to those of Gaussian basis sets and draw some conclusions for real-space, basis-sets, and plane-waves calculations. (C) 2016 AIP Publishing LLC.

Admissible Hierachic Sets

In this paper we present a solution concept for abstract systems called the admissible hierarchic set. The solution we propose is a refinement of the hierarchic solution, a generalization of the von Neumann and Morgenstern solution. For finite abstract systems we show that the admissible hierarchic sets and the von Neumann and Morgenstern stable sets are the only outcomes of a coalition formation procedure (Wilson, 1972 and Roth, 1984). For coalitional games we prove that the core is either a vN&M stable set or an admissible hierarchic set.

A generalized Hausdorff dimension for functions and sets

Let E be a compact subset of the n-dimensional unit cube, 1_n, and let C be a collection of convex bodies, all of positive n-dimensional Lebesgue measure, such that C contains bodies with arbitrarily small measure. The dimension of E with respect to the covering class C is defined to be the number

d_C(E) = sup(β:H_{β, C}(E) > 0),

where H_{β, C} is the outer measure

inf(Ʃm(C_i)^β:UC_i Ↄ E, C_i ϵ C) .

Only the one and two-dimensional cases are studied. Moreover, the covering classes considered are those consisting of intervals and rectangles, parallel to the coordinate axes, and those closed under translations. A covering class is identified with a set of points in the left-open portion, 1’_n, of 1_n, whose closure intersects 1_n - 1’_n. For n = 2, the outer measure H_{β, C} is adopted in place of the usual:

Inf(Ʃ(diam. (C_i))^β: UC_i Ↄ E, C_i ϵ C),

for the purpose of studying the influence of the shape of the covering sets on the dimension d_C(E).

If E is a closed set in 1₁, let M(E) be the class of all non-decreasing functions μ(x), supported on E with μ(x) = 0, x ≤ 0 and μ(x) = 1, x ≥ 1. Define for each μ ϵ M(E),

d_C(μ) = lim/c → inf/0 log ∆μ(c)/log c , (c ϵ C)

where ∆μ(c) = v/x (μ(x+c) – μ(x)). It is shown that

d_C(E) = sup (d_C(μ):μ ϵ M(E)).

This notion of dimension is extended to a certain class Ӻ of sub-additive functions, and the problem of studying the behavior of d_C(E) as a function of the covering class C is reduced to the study of d_C(f) where f ϵ Ӻ. Specifically, the set of points in 1₁,

(*) {d_B(F), d_C(f)): f ϵ Ӻ}

is characterized by a comparison of the relative positions of the points of B and C. A region of the form (*) is always closed and doubly-starred with respect to the points (0, 0) and (1, 1). Conversely, given any closed region in 1₂, doubly-starred with respect to (0, 0) and (1, 1), there are covering classes B and C such that (*) is exactly that region. All of the results are shown to apply to the dimension of closed sets E. Similar results can be obtained when a finite number of covering classes are considered.

In two dimensions, the notion of dimension is extended to the class M, of functions f(x, y), non-decreasing in x and y, supported on 1₂ with f(x, y) = 0 for x · y = 0 and f(1, 1) = 1, by the formula

d_C(f) = lim/s · t → inf/0 log ∆f(s, t)/log s · t , (s, t) ϵ C

where

∆f(s, t) = V/x, y (f(x+s, y+t) – f(x+s, y) – f(x, y+t) + f(x, t)).

A characterization of the equivalence d_C1(f) = d_C2(f) for all f ϵ M, is given by comparison of the gaps in the sets of products s · t and quotients s/t, (s, t) ϵ C_i (I = 1, 2).