Search results for "Set theory"

Classification générique de synthèses temps minimales avec cible de codimension un et applications

1997

In this article we consider the problem of constructing the optimal closed loop control in the time minimal control problem, with terminal constraints belonging to a manifold of codimension one, for systems of the form v = X + uY, v ϵ R2, R3, |u| ≤ 1 under generic assumptions. The analysis is localized near the terminal manifold and is motivated by the problem of controlling a class of chemical systems.

Co-learnability and FIN-identifiability of enumerable classes of total recursive functions

1994

Co-learnability is an inference process where instead of producing the final result, the strategy produces all the natural numbers but one, and the omitted number is an encoding of the correct result. It has been proved in [1] that co-learnability of Goedel numbers is equivalent to EX-identifiability. We consider co-learnability of indices in recursively enumerable (r.e.) numberings. The power of co-learnability depends on the numberings used. Every r.e. class of total recursive functions is co-learnable in some r.e. numbering. FIN-identifiable classes are co-learnable in all r.e. numberings, and classes containing a function being accumulation point are not co-learnable in some r.e. number…

Exceptional Configurations of Quantum Walks with Grover’s Coin

2016

We study search by quantum walk on a two-dimensional grid using the algorithm of Ambainis, Kempe and Rivosh [AKR05]. We show what the most natural coin transformation -- Grover's diffusion transformation -- has a wide class of exceptional configurations of marked locations, for which the probability of finding any of the marked locations does not grow over time. This extends the class of known exceptional configurations; until now the only known such configuration was the "diagonal construction" by [AR08].

Stochastic Processes on Ends of Tree and Dirichlet Forms

2016

We present main ideas and compare two constructions of stochastic processes on the ends (leaves) of the trees with varying numbers of edges at the nods. In one of them the trees are represented by spaces of numerical sequences and the processes are obtained by solving a class of Chapman-Kolmogorov Equations. In the other the trees are described by the set of nodes and edges. To each node there is naturally associated a finite dimensional function space and the Dirichlet form on it. Having a class of Dirichlet forms at the nodes one can under certain conditions build a Dirichlet form on L2 space of funcions on the ends of the trees. We show that the state spaces of two approaches are homeomo…

Presentations for the Mapping Class Groups of Nonorientable Surfaces

2014

Sigma-fragmentability and the property SLD in C(K) spaces

2009

Abstract We characterize two topological properties in Banach spaces of type C ( K ) , namely, being σ-fragmented by the norm metric and having a countable cover by sets of small local norm-diameter (briefly, the property norm-SLD). We apply our results to deduce that C p ( K ) is σ-fragmented by the norm metric when K belongs to a certain class of Rosenthal compacta as well as to characterize the property norm-SLD in C p ( K ) in case K is scattered.

Circuit Lower Bounds via Ehrenfeucht-Fraisse Games

2006

In this paper we prove that the class of functions expressible by first order formulas with only two variables coincides with the class of functions computable by AC/sup 0/ circuits with a linear number of gates. We then investigate the feasibility of using Ehrenfeucht-Fraisse games to prove lower bounds for that class of circuits, as well as for general AC/sup 0/ circuits.

Complexity of decision trees for boolean functions

2004

For every positive integer k we present an example of a Boolean function f/sub k/ of n = (/sub k//sup 2k/) + 2k variables, an optimal deterministic tree T/sub k/' for f/sub k/ of complexity 2k + 1 as well as a nondeterministic decision tree T/sub k/ computing f/sub k/. with complexity k + 2; thus of complexity about 1/2 of the optimal deterministic decision tree. Certain leaves of T/sub k/ are called priority leaves. For every input a /spl isin/ {0, 1}/sup n/ if any of the parallel computation reaches a priority leaves then its label is f/sub k/ (a). If the priority leaves are not reached at all then the label on any of the remaining leaves reached by the computation is f/sub k/. (a).

A NOTE ON THE ASYMPTOTIC PROBABILITIES OF EXISTENTIAL SECOND-ORDER MINIMAL GÖDEL SENTENCES WITH EQUALITY

1995

The minimal Gödel class is the class of first-order prenex sentences whose quantifier prefix consists of two universal quantifiers followed by just one existential quantifier. We prove that asymptotic probabilities of existential second-order sentences, whose first-order part is in the minimal Gödel class, form a dense subset of the unit interval.

A Group-theoretical Finiteness Theorem

2008

We start with the universal covering space $${\*M^n}$$ of a closed n-manifold and with a tree of fundamental domains which zips it $${T\longrightarrow\*M^n}$$ . Our result is that, between T and $${\* M^n}$$ , is an intermediary object, $${T\stackrel{p} {\longrightarrow} G \stackrel{F}{\longrightarrow} \*M^n}$$ , obtained by zipping, such that each fiber of p is finite and $${T\stackrel{p}{\longrightarrow}G\stackrel{F}{\longrightarrow} \*M^n}$$ admits a section.