Suballowable sequences and geometric permutations

We define suballowable sequences of permutations as a generalization of allowable sequences. We give a characterization of allowable sequences in the class of suballowable sequences, prove a Helly-type result on sets of permutations which form suballowable sequences, and show how suballowable sequences are related to problems of geometric realizability. We discuss configurations of points and geometric permutations in the plane. In particular, we find a characterization of pairwise realizability of planar geometric permutations, give two necessary conditions for realizability of planar geometric permutations, and show that these conditions are not sufficient.     

Computational implementation of Fujishige's graph realizability algorithm

Fujishige's PQ-graph algorithm is one of the most computationally efficient algorithms for testing the graph realizability of a (0,1) matrix E. This paper reports the first computational implementation of the algorithm. Computational testing, carried out on randomly generated matrices with up to 500 rows and 9000 columns, validates the almost linear time computational complexity of Fujishige's algorithm.     

Provably total functions of Basic Arithmetic

It is shown that all the provably total functions of Basic Arithmetic BA, a theory introduced by Ruitenburg based on Predicate Basic Calculus, are primitive recursive. Along the proof a new kind of primitive recursive realizability to which BA is sound, is introduced. This realizability is similar to Kleene's recursive realizability, except that recursive functions are restricted to primitive recursives.     

Pontryagin–Thom construction for approximation of mappings by embeddings

Let n3 and be positive integers, f :Sⁿ→Sⁿ be a C⁰-mapping, and denote the standard embedding. As an application of the Pontryagin–Thom construction in the special case of the two-point configuration space, we construct complete algebraic obstructions O(f) and to discrete and isotopic realizability (realizability as an embedding) of the mapping Jf. The obstructions are described in terms of stable (equivariant) homotopy groups of neighborhoods of the singular set Σ(f)={(x,y)Sⁿ×Sⁿf(x)=f(y), x≠y}.

A standard method of solving problems in differential topology is to translate them into homotopy theory by means of bordism theory and Pontryagin–Thom construction. By this method we give a generalization of the van-Kampen–Skopenkov obstruction to discrete realizability of f and the van-Kampen–Melikhov obstruction to isotopic realizability of f. The latter are complete only in the case d=0 and are the images of our obstructions under a Hurewicz homomorphism.

We consider several examples of computation of the obstructions.     

Proof interpretations with truth

This article systematically investigates so‐called “truth variants” of several functional interpretations. We start by showing a close relation between two variants of modified realizability, namely modified realizability with truth and q‐modified realizability. Both variants are shown tobe derived from a single “functional interpretation with truth” of intuitionistic linear logic. This analysis suggests that several functional interpretations have truth and q‐variants. These variants, however, require a more involved modification than the ones previously considered. Following this lead we present truth and q‐variants of the Diller‐Nahm interpretation, the bounded modified realizability and the bounded functional interpretation (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Arithmetical realizability and primitive recursive realizability

The semantics of the predicate logic based on the absolute arithmetical realizability is proved to differ from the semantics based on the primitive recursive realizability by Salehi.     

On hyperarithmetical realizability

The notion of hyperarithmetical realizability is introduced for various extensions of the language of formal arithmetic. The correctness of classical, intuitionistic, and basic logic with respect to the semantics based on hyperarithmetical realizability is studied.     

Analytic constraints and realizability for analytic input-output operators

For input-output (i-o) operators, an equivalence is shown betweenrealizability by state-space systems and the existence of analyticconstrainsts on higher-order derivatives of i-o signals. Thisprovides a precise characterization of realizability, extendingto the general analytic case the previous work that dealt withthe equivalence between algebraic realizability and algebraici-o equations.     

Automatic realizability of Galois groups of order 16

This article examines the realizability of small groups of order , as Galois groups over arbitrary fields of characteristic not 2. In particular we consider automatic realizability of certain groups given the realizability of others.

     

Nonnegative realizations of systems over nonnegative quasi-fields

In this paper, several sufficient conditions of nonnegative realizability of nonnegative systems have been derived. The authors have also pointed out the relation between two kinds of nonnegative realizability.The project supported by Natural Science Foundation of China.     

On Galois cohomology and realizability of 2-groups as Galois groups

In this paper we develop some new theoretical criteria for the realizability of p-groups as Galois groups over arbitrary fields. We provide necessary and sufficient conditions for the realizability of 14 of the 22 non-abelian 2-groups having a cyclic subgroup of index 4 that are not direct products of groups.     

Galois realizability of groups of order 64

This article examines the realizability of groups of order 64 as Galois groups over arbitrary fields. Specifically, we provide necessary and sufficient conditions for the realizability of 134 of the 200 noncyclic groups of order 64 that are not direct products of smaller groups.     

Sheaf toposes for realizability

We compare realizability models over partial combinatory algebras by embedding them into sheaf toposes. We then use the machinery of Grothendieck toposes and geometric morphisms to study the relationship between realizability models over different partial combinatory algebras. This research is part of the Logic of Types and Computation project at Carnegie Mellon University under the direction of Dana Scott.     

Symmetric nonnegative realizability via partitioned majorization

A sufficient condition for symmetric nonnegative realizability of a spectrum is given in terms of (weak) majorization of a partition of the negative eigenvalues by a selection of the positive eigenvalues. If there are more than two positive eigenvalues, an additional condition, besides majorization, is needed on the partition. This generalizes observations of Suleǐmanova and Loewy about the cases of one and two positive eigenvalues, respectively. It may be used to provide insight into realizability of 5-element spectra and beyond.     

A completeness result for the simply typed -calculus

In this paper, we define a realizability semantics for the simply typed λμ-calculus. We show that, if a term is typable, then it inhabits the interpretation of its type. This result serves to give characterizations of the computational behavior of some closed typed terms. We also prove a completeness result of our realizability semantics using a particular term model.     

On Galois cohomology and realizability of 2-groups as Galois groups II

In [Michailov I.M., On Galois cohomology and realizability of 2-groups as Galois groups, Cent. Eur. J. Math., 2011, 9(2), 403–419] we calculated the obstructions to the realizability as Galois groups of 14 non-abelian groups of order 2 ⁿ , n ≥ 4, having a cyclic subgroup of order 2 ⁿ⁻², over fields containing a primitive 2 ⁿ⁻³th root of unity. In the present paper we obtain necessary and sufficient conditions for the realizability of the remaining 8 groups that are not direct products of smaller groups.     

On non-symmetric commutative association schemes with exactly one pair of non-symmetric relations

For a given non-symmetric commutative association scheme, by fusing all the non-symmetric relations pairwise with their symmetric counterparts, we can obtain a new symmetric association scheme. In this paper, we introduce a set of feasibility and realizability conditions for a class e symmetric association scheme to be split into a class e+1 non-symmetric commutative association scheme. By applying the feasibility and realizability conditions, we obtain a classification into six categories of the class 4 non-symmetric fission schemes of group-divisible 3-schemes. Complete solutions for three of the six categories and partial results for the remaining cases are presented.     

Nonrealizable Minimal Vertex Triangulations of Surfaces: Showing Nonrealizability Using Oriented Matroids and Satisfiability Solvers

We show that no minimal vertex triangulation of a closed, connected, orientable 2-manifold of genus 6 admits a polyhedral embedding in ℝ³. We also provide examples of minimal vertex triangulations of closed, connected, orientable 2-manifolds of genus 5 that do not admit any polyhedral embeddings. Correcting a previous error in the literature, we construct the first infinite family of such nonrealizable triangulations of surfaces. These results were achieved by transforming the problem of finding suitable oriented matroids into a satisfiability problem. This method can be applied to other geometric realizability problems, e.g., for face lattices of polytopes.     

On the theory of dynamic thermoelasticity : PMM, vol. 42, no. 6, 1978, pp. 1093–1098

Use of the causality principle as radiation condition in dynamical problems of thermoelasticity is proposed. It follows from an analysis of the fundamental mathematical models describing the thermoelastic behavior of a continuous medium and used in the solution of specific problems, that some will yield physically unrealizable solutions. To eliminate the ambiguity in the solution which occurs, an approach is possible which has an explicit physical meaning and is based on the causality principle [1, 2]; it is required that the time source not yield a response earlier than the time of starting up of the source. Different kinds of radiation conditions of the Sommerfeld type are known in thermoelasticity problems [3 – 6].

To extract the unique solution in dynamical thermoelasticity problems, it is proposed in this paper to use the causality principle, which is equivalent to the requirement of analyticity of the solution in the upper half of the complex frequency plane; there are studied the analytic properties of the solutions of the fundamental boundary value problems for the models used most often for thermoelastic media, and there are made deductions about their physical realizability.     

Simple Realizability of Complete Abstract Topological Graphs in P

An abstract topological graph (briefly an AT-graph) is a pair A=(G,R)A=(G,\mathcal{R}) where G=(V,E) is a graph and R í ((E) || 2)\mathcal {R}\subseteq {E \choose 2} is a set of pairs of its edges. An AT-graph A is simply realizable if G can be drawn in the plane in such a way that each pair of edges from R\mathcal{R} crosses exactly once and no other pair crosses. We present a polynomial algorithm which decides whether a given complete AT-graph is simply realizable. On the other hand, we show that other similar realizability problems for (complete) AT-graphs are NP-hard.