Categories with families and first-order logic with dependent sorts

First-order logic with dependent sorts, such as Makkai's first-order logic with dependent sorts (FOLDS), or Aczel's and Belo's dependently typed (intuitionistic) first-order logic (DFOL), may be regarded as logic enriched dependent type theories. Categories with families (cwfs) is an established semantical structure for dependent type theories, such as Martin-Löf type theory. We introduce in this article a notion of hyperdoctrine over a cwf, and show how FOLDS and DFOL fit in this semantical framework. A soundness and completeness theorem is proved for DFOL. The semantics is functorial in the sense of Lawvere, and uses a dependent version of the Lindenbaum-Tarski algebra for a DFOL theory. Agreement with standard first-order semantics is established. Applications of DFOL to constructive mathematics and categorical foundations are given. A key feature is a local propositions-as-types principle.     

A Problem with Nonlocal Conditions for Partial Differential Equations with Variable Coefficients

We establish conditions for the unique solvability of a problem for partial differential equations with coefficients dependent on variables t and x in a rectangular domain with nonlocal two-point conditions with respect to t and local boundary conditions with respect to x. We prove metric statements related to lower bounds of small denominators appearing in the course of solution of the problem.     

The Wiener integral with respect to second order processes with stationary increments

We prove that for any second order stochastic process X with stationary increments with continuous paths and continuous variance function, there exists a tempered measure μ (for which we give an explicit expression) related with the domain of the Wiener integral with respect to X as follows: the space of tempered distributions f such that the Fourier transform of f is square integrable with respect to μ is always a dense subset of the domain of the Wiener integral. Moreover, we provide sufficient conditions on μ in order that the domain of the integral is exactly this space of distributions. We apply our results to the fractional Brownian motion. In particular, it is proved that the domain of the Wiener integral with respect to the fractional Brownian motion with Hurst parameter H>1/2 contains distributions that are not given by locally integrable functions, this fact was suggested by Pipiras and Taqqu (2000) in [5]. We have also considered the example of the process given by Ornstein and Uhlenbeck as a model for the position of a Brownian particle.     

Insider Models with Finite Utility in Markets with Jumps

In this article we consider, under a Lévy process model for the stock price, the utility optimization problem for an insider agent whose additional information is the final price of the stock blurred with an additional independent noise which vanishes as the final time approaches. Our main interest is establishing conditions under which the utility of the insider is finite. Mathematically, the problem entails the study of a “progressive” enlargement of filtration with respect to random measures. We study the jump structure of the process which leads to the conclusion that in most cases the utility of the insider is finite and his optimal portfolio is bounded. This can be explained financially by the high risks involved in models with jumps.     

Competitive Lotka-Volterra population dynamics with jumps

This paper considers competitive Lotka-Volterra population dynamics with jumps. The contributions of this paper are as follows. (a) We show that a stochastic differential equation (SDE) with jumps associated with the model has a unique global positive solution; (b) we discuss the uniform boundedness of the pth moment with p>0 and reveal the sample Lyapunov exponents; (c) using a variation-of-constants formula for a class of SDEs with jumps, we provide an explicit solution for one-dimensional competitive Lotka-Volterra population dynamics with jumps, and investigate the sample Lyapunov exponent for each component and the extinction of our n-dimensional model.     

A problem with nonlocal conditions for partial differential equations with constant coefficients

We study the correctness of a problem with nonlocal conditions for untypical partial differential equations with constant coefficients in a cylindrical domain, which is a product of a segment by a torus. We establish conditions of the correctness of this problem for almost all values (with respect to Lebesgue’s measure) of its two chosen parameters.     

Tverberg's theorem with constraints

The topological Tverberg theorem claims that for any continuous map of the (q−1)(d+1)-simplex σ(d+1)(q−1) to Rd there are q disjoint faces of σ(d+1)(q−1) such that their images have a non-empty intersection. This has been proved for affine maps, and if q is a prime power, but not in general.We extend the topological Tverberg theorem in the following way: Pairs of vertices are forced to end up in different faces. This leads to the concept of constraint graphs. In Tverberg's theorem with constraints, we come up with a list of constraints graphs for the topological Tverberg theorem.The proof is based on connectivity results of chessboard-type complexes. Moreover, Tverberg's theorem with constraints implies new lower bounds for the number of Tverberg partitions. As a consequence, we prove Sierksma's conjecture for d=2 and q=3.     

Preemptive scheduling with rejection

 We consider the problem of preemptively scheduling a set of n jobs on m (identical, uniformly related, or unrelated) parallel machines. The scheduler may reject a subset of the jobs and thereby incur job-dependent penalties for each rejected job, and he must construct a schedule for the remaining jobs so as to optimize the preemptive makespan on the m machines plus the sum of the penalties of the jobs rejected. We provide a complete classification of these scheduling problems with respect to complexity and approximability. Our main results are on the variant with an arbitrary number of unrelated machines. This variant is APX-hard, and we design a 1.58-approximation algorithm for it. All other considered variants are weakly -hard, and we provide fully polynomial time approximation schemes for them. Finally, we argue that our results for unrelated machines can be carried over to the corresponding preemptive open shop scheduling problem with rejection. Received: October 30, 2000 / Accepted: September 26, 2001 Published online: September 5, 2002 Key words. scheduling – preemption – approximation algorithm – worst case ratio – computational complexity – in-approximability Supported in part by the EU Thematic Network APPOL, Approximation and Online Algorithms, IST-1999-14084 Supported by the START program Y43-MAT of the Austrian Ministry of Science.     

Perturbed Markov Chains with Damping Component

The paper is devoted to studies of regularly and singularly perturbed Markov chains with damping component. In such models, a matrix of transition probabilities is regularised by adding a special damping matrix multiplied by a small damping (perturbation) parameter ε. We perform a detailed perturbation analysis for such Markov chains, particularly, give effective upper bounds for the rate of approximation for stationary distributions of unperturbed Markov chains by stationary distributions of perturbed Markov chains with regularised matrices of transition probabilities, asymptotic expansions for approximating stationary distributions with respect to damping parameter, explicit coupling type upper bounds for the rate of convergence in ergodic theorems for n-step transition probabilities, as well as ergodic theorems in triangular array mode.

     

Bifurcation with a two-dimensional kernel

We present a theorem ensuring the existence of local solution branches for one-parameter bifurcation problems in which the linearization at the trivial solution possesses a two-dimensional kernel. In particular, we provide a straightforward “test” that is sufficient for the existence of local solution continua. We demonstrate our abstract theorem with several concrete examples for second-order systems of elliptic partial differential equations with symmetry.     

Three sphere inequality for second order elliptic equations with coefficients with jump discontinuity

This is a short note to complete the paper appeared in Francini et al. (2016) [4], where a rough version of the classical well known Hadamard three-circle theorem for solution of an elliptic PDE in divergence form has been proved. Precisely, instead of circles, the authors obtain a similar inequality in a more complicated geometry. In this paper we clean the geometry and obtain a generalized version of the three-circle inequality for elliptic equation with coefficients with discontinuity of jump type.     

Monadic Algebras with finite degree

A monadic algebraA has finite degreen ifA/M has at most 2 ⁿ elements for every maximal idealM ofA and this bound is obtained for someM. Every countable monadic algebra with a finite degree is isomorphic to an algebra Γ(X, S) whereX is a Boolean space andS is a subsheaf of a constant sheaf with a finite simple stalk. This representation is used to prove that every proper equational class of monadic algebras has a decidable first-order theory.     

Greedy Algorithms with Regard to Multivariate Systems with Special Structure

The question of finding an optimal dictionary for nonlinear m -term approximation is studied in this paper. We consider this problem in the periodic multivariate (d variables) case for classes of functions with mixed smoothness. We prove that the well-known dictionary U ^d which consists of trigonometric polynomials (shifts of the Dirichlet kernels) is nearly optimal among orthonormal dictionaries. Next, it is established that for these classes near-best m -term approximation, with regard to U ^d , can be achieved by simple greedy-type (thresholding-type) algorithms. The univariate dictionary U is used to construct a dictionary which is optimal among dictionaries with the tensor product structure. June 22, 1998. Date revised: March 26, 1999. Date accepted: March 22, 1999.     

Associative rings with large center

A ring R is called a ring with large center if any nonzero ideal of R has nonzero intersection with the center of R. We give some conditions for an ideal of a ring with large center to be itself a ring with large center, and also we provide an example of a ring with large center R and its ideal I ? R such that I is not a ring with large center.     

Repeated Games with Bonuses

This paper deals with 2-player zero-sum repeated games in which player 1 receives a bonus at stage t if he repeats the action he played at stage t−1. We investigate the optimality of simple strategies for player 1. A simple strategy for player 1 consists of playing the same mixed action at every stage, irrespective of past play. Furthermore, for games in which player 1 has a simple optimal strategy, we characterize the set of stationary optimal strategies for player 2.     

因式分解广义逆

在因式分解范畴中定义态射的因式分解广义逆,给出了它的显形式,讨论了其唯一性.应用于范畴C^m×n中,态射A:m→n的满秩分解(A₁,r,A₂)可刻划A的具有指定值域和零空间的(1,2)逆,并给出了具有指定值域和零空间的(1,2)逆表成因式分解广义逆的充要条件.     

Boolean functions with MacWilliams duality

We introduce a new class of Boolean functions for which the MacWilliams duality holds, called MacWilliams-dual functions, by considering a dual notion on Boolean functions. By using the MacWilliams duality, we prove the Gleason-type theorem on MacWilliams-dual functions. We show that a collection of MacWilliams-dual functions contains all the bent functions and all formally self-dual functions. We also obtain the Pless power moments for MacWilliams-dual functions. Furthermore, as an application, we prove the nonexistence of bent functions in 2n variables with minimum degree n?k for any nonnegative integer k and n ≥ N with some positive integer N under a certain condition.     

Hadamard expansions for integrals with saddles coalescing with an endpoint

Hadamard expansions are constructed for Laplace-type integrals containing a parameter and an asymptotic variable $x$, which may be real or complex. These expansions yield a method of hyperasymptotic evaluation that remains valid throughout a range of the parameter corresponding to coalescence of a saddle point with an endpoint of the integration path. Numerical examples are given to illustrate the practical aspects of the computations.