Helmut Seidl, Damian Niwiński (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
For every fixed-point expression of alternation-depth , we construct a new fixed-point expression of alternation-depth 2 and size . Expression is equivalent to whenever operators are distributive and the underlying complete lattice has a co-continuous least upper bound. We alternation-depth but also w.r.t. the increase in size of the resulting expression.
Michele Zito (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
We prove that, with high probability, the space complexity of refuting a random unsatisfiable Boolean formula in -CNF on variables and clauses is .
Galina Jirásková, Alexander Okhotin (2007)
RAIRO - Theoretical Informatics and Applications
Similarity:
The cyclic shift of a language , defined as SHIFT() = {}, is an operation known to preserve both regularity and context-freeness. Its descriptional complexity has been addressed in Maslov's pioneering paper on the state complexity of regular language operations [ (1970) 1373–1375], where a high lower bound for partial DFAs using a growing alphabet was given. We improve this result by using a fixed 4-letter alphabet, obtaining a lower bound (n-1)! . 2(n-1)(n-2), which...
Emilio Carrizosa, E. Conde, A. Castaño, D. Romero–Morales (2010)
RAIRO - Operations Research
Similarity:
The -principal points of a random variable with finite second moment are those points in minimizing the expected squared distance from to the closest point. Although the determination of principal points involves in general the resolution of a multiextremal optimization problem, existing procedures in the literature provide just a local optimum. In this paper we show that standard Global Optimization techniques can be applied.