Displaying similar documents to “Depth Lower Bounds for Monotone Semi-Unbounded Fan-in Circuits”

Monotone (co)inductive types and positive fixed-point types

Ralph Matthes (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We study five extensions of the polymorphically typed lambda-calculus (system ) by type constructs intended to model fixed-points of monotone operators. Building on work by Geuvers concerning the relation between term rewrite systems for least pre-fixed-points and greatest post-fixed-points of positive type schemes (, non-nested positive inductive and coinductive types) and so-called retract types, we show that there are reduction-preserving embeddings even between systems of monotone...

Convolution property and exponential bounds for symmetric monotone densities

Claude Lefèvre, Sergey Utev (2013)

ESAIM: Probability and Statistics

Similarity:

Our first theorem states that the convolution of two symmetric densities which are -monotone on (0∞) is again (symmetric) -monotone provided 0   ≤ 1. We then apply this result, together with an extremality approach, to derive sharp moment and exponential bounds for distributions having such shape constrained densities.

Undecidability of infinite post correspondence problem for instances of size 8

Jing Dong, Qinghui Liu (2012)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

The infinite Post Correspondence Problem (PCP) was shown to be undecidable by Ruohonen (1985) in general. Blondel and Canterini [36 (2003) 231–245] showed that PCP is undecidable for domain alphabets of size 105, Halava and Harju [40 (2006) 551–557] showed that PCP is undecidable for domain alphabets of size 9. By designing a special coding, we delete a letter from Halava and Harju’s construction. So we prove that PCP is undecidable for domain alphabets of size 8.

Hereditary properties of words

József Balogh, Béla Bollobás (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Let be a hereditary property of words, , an infinite class of finite words such that every subword (block) of a word belonging to is also in . Extending the classical Morse-Hedlund theorem, we show that either contains at least words of length for every  or, for some , it contains at most words of length for every . More importantly, we prove the following quantitative extension of this result: if has words of length then, for every , it contains at most ⌈( + 1)/2⌉⌈( + 1)/2⌈...

Square-root rule of two-dimensional bandwidth problem

Lan Lin, Yixun Lin (2011)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

The bandwidth minimization problem is of significance in network communication and related areas. Let be a graph of vertices. The two-dimensional bandwidth () of is the minimum value of the maximum distance between adjacent vertices when is embedded into an  ×  grid in the plane. As a discrete optimization problem, determining () is NP-hard in general. However, exact results for this parameter can be derived for some special classes of graphs. This...

Semi-continuité inférieure d'intégrales multiples et d'intégrandes convergentes

Zhiping Li (2010)

ESAIM: Control, Optimisation and Calculus of Variations

Similarity:

Lower semicontinuity of multiple integrals ∫ and ∫ are studied. It is proved that the two can derive from each other under certain general hypotheses such as uniform lower compactness property and locally uniform convergence of . The result is applied to obtain some general lower semicontinuity theorems on multiple integrals with quasiconvex integrand ƒ, while are not required to be quasiconvex.

Three generators for minimal writing-space computations

Serge Burckel, Marianne Morillon (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We construct, for each integer , three functions from {0,1} to {0,1} such that any boolean mapping from {0,1} to {0,1} can be computed with a finite sequence of assignations only using the input variables and those three functions.

Pointwise constrained radially increasing minimizers in the quasi-scalar calculus of variations

Luís Balsa Bicho, António Ornelas (2014)

ESAIM: Control, Optimisation and Calculus of Variations

Similarity:

We prove of vector minimizers () =  (||) to multiple integrals ∫ ((), |()|)  on a  ⊂ ℝ, among the Sobolev functions (·) in + (, ℝ), using a  : ℝ×ℝ → [0,∞] with (·) and . Besides such basic hypotheses, (·,·) is assumed to satisfy also...

Efficiency of automata in semi-commutation verification techniques

Gérard Cécé, Pierre-Cyrille Héam, Yann Mainier (2007)

RAIRO - Theoretical Informatics and Applications

Similarity:

Computing the image of a regular language by the transitive closure of a relation is a central question in regular model checking. In a recent paper Bouajjani [ (2001) 399–408] proved that the class of regular languages – called APC – of the form U ..., where the union is finite and each is either a single symbol or a language of the form with a subset of the alphabet, is closed under all semi-commutation relations . Moreover...

Upper large deviations for maximal flows through a tilted cylinder

Marie Theret (2014)

ESAIM: Probability and Statistics

Similarity:

We consider the standard first passage percolation model in ℤ for  ≥ 2 and we study the maximal flow from the upper half part to the lower half part (respectively from the top to the bottom) of a cylinder whose basis is a hyperrectangle of sidelength proportional to and whose height is () for a certain height function . We denote this maximal flow by (respectively ). We emphasize the fact that the cylinder may be tilted. We look at the probability that...