Some problems in automata theory which depend on the models of set theory

Olivier Finkel

Displaying similar documents to “Some problems in automata theory which depend on the models of set theory”

Optional splitting formula in a progressively enlarged filtration

Shiqi Song (2014)

ESAIM: Probability and Statistics

Similarity:

Let $𝔽_{}^{}$ F be a filtration andbe a random time. Let $𝔾_{}^{}$ G be the progressive enlargement of $𝔽_{}^{}$ F with. We study the following formula, called the optional splitting formula: For any $𝔾_{}^{}$ G-optional process, there exists an $𝔽_{}^{}$ F-optional process and a function defined on [0∞] × (ℝ × ) being $ℬ [0, \infty] \otimes 𝒪 (𝔽_{}^{})$ ℬ[0,∞]⊗x1d4aa;(F) measurable, such that $Y = Y^{'} 1_{[0, τ)}^{} + Y^{''} (τ) 1_{[τ, \infty)}^{} .$ Y=Y′1[0,τ)+Y′′(τ)1[τ,∞). (This formula can also be formulated for multiple random times ...

Gamma-convergence results for phase-field approximations of the 2D-Euler Elastica Functional

Luca Mugnai (2013)

ESAIM: Control, Optimisation and Calculus of Variations

Similarity:

We establish some new results about the -limit, with respect to the -topology, of two different (but related) phase-field approximations ${ℰ_{}}, {{\tilde{ℰ}}_{}}$ ℰ ε ε , x10ff65; ℰ ε ε of the so-called Euler’s Elastica Bending Energy for curves in the plane. In particular we characterize the-limit as → 0 of ℰ, and show that in general the -limits of ℰand $\tilde{ℰ}$ x10ff65; ℰ ε do not coincide on indicator functions of sets with non-smooth boundary. More precisely we show that the domain of the-limit...

A new H(div)-conforming p-interpolation operator in two dimensions

Alexei Bespalov, Norbert Heuer (2011)

ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique

Similarity:

In this paper we construct a new H(div)-conforming projection-based -interpolation operator that assumes only H() $\cap$ $\tilde{𝐇}$ (div, )-regularity ( > 0) on the reference element (either triangle or square) . We show that this operator is stable with respect to polynomial degrees and satisfies the commuting diagram property. We also establish an estimate for the interpolation error in the norm of the space $\tilde{𝐇}$ (div, ), which is closely related...

A new kind of augmentation of filtrations

Joseph Najnudel, Ashkan Nikeghbali (2011)

ESAIM: Probability and Statistics

Similarity:

Let (Ω, $ℱ$ , ( $ℱ_{t}$ ), $ℙ$ ) be a filtered probability space satisfying the usual assumptions: it is usually not possible to extend to $ℱ_{\infty}$ (the-algebra generated by ( $ℱ_{t}$ )) a coherent family of probability measures ( $ℚ_{t}$ ) indexed by , each of them being defined on $ℱ_{t}$ . It is known that for instance, on the Wiener space, this extension problem has a positive answer if one takes the filtration generated by the coordinate process, made right-continuous, but can have a negative...

Exact null internal controllability for the heat equation on unbounded convex domains

Viorel Barbu (2014)

ESAIM: Control, Optimisation and Calculus of Variations

Similarity:

The liner parabolic equation $\frac{y}{t} - \frac{1}{2} 𝔻 y + F \cdot y = {\vec{1}}_{_{0}} u$ ∂y ∂t − 1 2 Δy + F · ∇ y = 1 x1d4aa; 0 u with Neumann boundary condition on a convex open domain x1d4aa; ⊂ ℝ with smooth boundary is exactly null controllable on each finite interval if 𝒪is an open subset of x1d4aa; which contains a suitable neighbourhood of the recession cone of x1d4aa; . Here, : ℝ → ℝ is a bounded, -continuous function, and = ∇, where is convex and coercive.

Expansions for the distribution of M-estimates with applications to the Multi-Tone problem

Christopher S. Withers, Saralees Nadarajah (2011)

ESAIM: Probability and Statistics

Similarity:

We give a stochastic expansion for estimates $\hat{θ}$ that minimise the arithmetic mean of (typically independent) random functions of a known parameter. Examples include least squares estimates, maximum likelihood estimates and more generally -estimates. This is used to obtain leading cumulant coefficients of $\hat{θ}$ needed for the Edgeworth expansions for the distribution and density ) to magnitude (or to for the symmetric...

Necessary and sufficient condition for the existence of a Fréchet mean on the circle

Benjamin Charlier (2013)

ESAIM: Probability and Statistics

Similarity:

Let ( $𝕊^{1}, d_{𝕊^{1}}$ S 1 , d S 1 ) be the unit circle in ℝ endowed with the arclength distance. We give a sufficient and necessary condition for a general probability measure to admit a well defined Fréchet mean on ( $𝕊^{1}, d_{𝕊^{1}}$ S 1 , d S 1 ). We derive a new sufficient condition of existence() with no restriction on the support of the measure. Then, we study the convergence of the empirical Fréchet mean to the Fréchet mean and we give an algorithm to compute it.

Asymptotic behavior of second-order dissipative evolution equations combining potential with non-potential effects

Hedy Attouch, Paul-Émile Maingé (2011)

ESAIM: Control, Optimisation and Calculus of Variations

Similarity:

In the setting of a real Hilbert space $ℋ$ , we investigate the asymptotic behavior, as time goes to infinity, of trajectories of second-order evolution equations () + $\dot{u}$ () + (()) + (()) = 0, where is the gradient operator of a convex differentiable potential function : $ℋ \to ℝ$ ,: $ℋ \to ℋ$ is a maximal monotone operator which is assumed to be-cocoercive, and > 0 is a damping parameter. Potential and non-potential effects are associated...

Higher-order phase transitions with line-tension effect

Bernardo Galvão-Sousa (2011)

ESAIM: Control, Optimisation and Calculus of Variations

Similarity:

The behavior of energy minimizers at the boundary of the domain is of great importance in the Van de Waals-Cahn-Hilliard theory for fluid-fluid phase transitions, since it describes the effect of the container walls on the configuration of the liquid. This problem, also known as the liquid-drop problem, was studied by Modica in [ 4 (1987) 487–512], and in a different form by Alberti in [ is a scalar density function and and are double-well potentials, the exact scaling...

Numerical approximation of effective coefficients in stochastic homogenization of discrete elliptic equations

Antoine Gloria (2012)

ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique

Similarity:

We introduce and analyze a numerical strategy to approximate effective coefficients in stochastic homogenization of discrete elliptic equations. In particular, we consider the simplest case possible: An elliptic equation on the -dimensional lattice $ℤ^{d}$ with independent and identically distributed conductivities on the associated edges. Recent results by Otto and the author quantify the error made by approximating the homogenized coefficient by the averaged energy of a regularized corrector...

Compact convex sets of the plane and probability theory

Jean-François Marckert, David Renault (2014)

ESAIM: Probability and Statistics

Similarity:

The Gauss−Minkowski correspondence in ℝ states the existence of a homeomorphism between the probability measures on [0,2] such that $\int_{0}^{2 π} e^{i x} d μ (x) = 0$ ∫ 0 2 π e ix d μ ( x ) = 0 and the compact convex sets (CCS) of the plane with perimeter 1. In this article, we bring out explicit formulas relating the border of a CCS to its probability measure. As a consequence, we show that some natural operations on CCS – for example, the Minkowski sum – have natural translations in terms of probability measure operations,...

Relaxation in BV of integrals with superlinear growth

Parth Soneji (2014)

ESAIM: Control, Optimisation and Calculus of Variations

Similarity:

We study properties of the functional $\begin{matrix} ℱ_{loc} (u, Ω) : = inf_{(u_{j})} \{\underset{j \to \infty}{lim inf} \int_{Ω} f (\nabla u_{j}) x |\begin{matrix} (u_{j}) \subset W_{loc}^{1, r} (Ω,) \\ u_{j} u in (Ω,) \end{matrix}\}, \end{matrix}$ F loc ( u,Ω ) : = inf ( u j ) lim inf j → ∞ ∫ Ω f ( ∇ u j ) d x , whereu ∈ BV(Ω;R^N), and f:R^{N × n} → R is continuous and satisfies 0 ≤ f(ξ)...

Coarse quantization for random interleaved sampling of bandlimited signals

Alexander M. Powell, Jared Tanner, Yang Wang, Özgür Yılmaz (2012)

ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique

Similarity:

The compatibility of unsynchronized interleaved uniform sampling with Sigma-Delta analog-to-digital conversion is investigated. Let be a bandlimited signal that is sampled on a collection of interleaved grids { + } with offsets ${T_{n}}_{n = 1}^{N} \subset [0, T]$ T n n = 1 N ⊂ [ 0 ,T ] . If the offsets are chosen independently and uniformly at random from [0] and if the sample values of are quantized with a first order Sigma-Delta algorithm, then with high probability the quantization...

A bayesian framework for the ratio of two Poisson rates in the context of vaccine efficacy trials

Stéphane Laurent, Catherine Legrand (2012)

ESAIM: Probability and Statistics

Similarity:

In many applications, we assume that two random observations and are generated according to independent Poisson distributions $(λ S)$ x1d4ab;() and $(μ T)$ x1d4ab;() and we are interested in performing statistical inference on the ratio = / of the two incidence rates. In vaccine efficacy trials, and are typically the numbers of cases in the vaccine and the control groups respectively, is called the relative risk and the statistical model is called ‘partial immunity model’. In this paper we...

Strong unique continuation for the Lamé system with Lipschitz coefficients in three dimensions

Hang Yu (2011)

ESAIM: Control, Optimisation and Calculus of Variations

Similarity:

This paper studies the strong unique continuation property for the Lamé system of elasticity with variable Lamé coefficients , in three dimensions, $div (μ (\nabla u + \nabla u^{t})) + \nabla (λ div u) + V u = 0$ where and are Lipschitz continuous and . The method is based on the Carleman estimate with polynomial weights for the Lamé operator.

Exact simulation for solutions of one-dimensional Stochastic Differential Equations with discontinuous drift

Pierre Étoré, Miguel Martinez (2014)

ESAIM: Probability and Statistics

Similarity:

In this note we propose an exact simulation algorithm for the solution of (1) $d X_{t} = d W_{t} + \bar{b} (X_{t}) d t, X_{0} = x,$ d X t = d W t + b̅ ( X t ) d t, X 0 = x, where $\bar{b}$ b̅is a smooth real function except at point 0 where $\bar{b} (0 +) \neq \bar{b} (0 -)$ b̅(0 + ) ≠ b̅(0 −) . The main idea is to sample an exact skeleton of Xusing an algorithm deduced from the convergence of the solutions of the skew...

A Lower Bound For Reversible Automata

Pierre-Cyrille Héam (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

A reversible automaton is a finite automaton in which each letter induces a partial one-to-one map from the set of states into itself. We solve the following problem proposed by Pin. Given an alphabet , does there exist a sequence of languages on which can be accepted by a reversible automaton, and such that the number of states of the minimal automaton of is in (), while the minimal number of states of a reversible automaton accepting ...

A characterization of poly-slender context-free languages

Lucian Ilie, Grzegorz Rozenberg, Arto Salomaa (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

For a non-negative integer , we say that a language is if the number of words of length in is of order $𝒪 (n^{k})$ . We give a precise characterization of the -poly-slender context-free languages. The well-known characterization of the -poly-slender regular languages is an immediate consequence of ours.

Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata

Carlo Mereghetti, Beatrice Palano, Giovanni Pighizzini (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We investigate the succinctness of several kinds of unary automata by studying their state complexity in accepting the family {} of cyclic languages, where = | ∈ . In particular, we show that, for any , the number of states necessary and sufficient for accepting the unary language with isolated cut point on one-way probabilistic finite automata is $p_{1}^{α_{1}} + p_{2}^{α_{2}} + \dots + p_{s}^{α_{s}}$ , with $p_{1}^{α_{1}} p_{2}^{α_{2}} \dots p_{s}^{α_{s}}$ being the factorization of . To prove this result, we give a Moreover, we exhibit one-way quantum...