共查询到20条相似文献,搜索用时 31 毫秒
1.
A. Blaquière 《Dynamics and Control》1991,1(1):7-24
In the framework of stochastic mechanics, the following problem is considered: in a set of admissible feedback controls v, with range inE
n
, find one minimizing the expectationE
sx
{
s
T
L(t, (t), (t, (t)))dt + W
T
((T))} for all (s, x) [0,T) E
n
, whereL(t, x, ) = (/12)m
2
– U(t, x) is the classical action integrand and is an-dimensional diffusion process in the weak sense, (see Bensoussan, 1982) with drift and diffusion coefficientD constant > 0.W
T
andU are given real functions. Sufficiency conditions for the existence of such an optimal feedback control are given.
Dedicated to George Leitmann
Recommended by G.J. Olsder
Presented at the Third Workshop on Control Mechanics in honor of George Leitmann, January 22–24, 1990, University of Southern California, Los Angeles, California (USA). 相似文献
2.
A theory is developed for the construction of carry-save networks with minimal delay, using a given collection of carry-save adders each of which may receive inputs and produce outputs using several different representation standards.The construction of some new carry-save adders is described. Using these carry-save adders optimally, as prescribed by the above theory, we get {, , }-circuits of depth 3.48 log2
n and {, , }-circuits of depth 4.95 log2
n for the carry-save addition ofn numbers of arbitrary length. As a consequence we get multiplication circuits of the same depth. These circuits put out two numbers whose sum is the result of the multiplication. If a single output number is required then the depth of the multiplication circuits increases respectively to 4.48 log2
n and 5.95 log2
n.We also get {, , }-formulae of sizeO (n
3.13) and {, }-formulae of sizeO (n
4.57) for all the output bits of a carry-save addition ofn numbers. As a consequence we get formulae of the same size for the majority function and many other symmetric Boolean functions. 相似文献
3.
A New Class of Depth-Size Optimal Parallel Prefix Circuits 总被引:1,自引:1,他引:0
Given n values x1, x2, ... ,xn and an associative binary operation o, the prefix problem is to compute x1ox2o··· oxi, 1in. Many combinational circuits for solving the prefix problem, called prefix circuits, have been designed. It has been proved that the size s(D(n)) and the depth d(D(n)) of an n-input prefix circuit D(n) satisfy the inequality d(D(n))+s(D(n))2n–2; thus, a prefix circuit is depth-size optimal if d(D(n))+s(D(n))=2n–2. In this paper, we construct a new depth-size optimal prefix circuit SL(n). In addition, we can build depth-size optimal prefix circuits whose depth can be any integer between d(SL(n)) and n–1. SL(n) has the same maximum fan-out lgn+1 as Snir's SN(n), but the depth of SL(n) is smaller; thus, SL(n) is faster. Compared with another optimal prefix circuit LYD(n), d(LYD(n))+2d(SL(n))d(LYD(n)). However, LYD(n) may have a fan-out of at most 2 lgn–2, and the fan-out of LYD(n) is greater than that of SL(n) for almost all n12. Because an operation node with greater fan-out occupies more chip area and is slower in VLSI implementation, in most cases, SL(n) needs less area and may be faster than LYD(n). Moreover, it is much easier to design SL(n) than LYD(n). 相似文献
4.
S. A. Greibach 《Acta Informatica》1978,11(1):89-101
Summary For a family of languages , CAL() is defined as the family of images of under nondeterministic two-way finite state transducers, while FINITE · VISIT() is the closure of under deterministic two-way finite state transducers; CAL0()= and for n0, CAL
n+1()=CAL
n
(CAL()). For any semiAFL , if FINITE · VISIT() CAL(), then CAL
n
() forms a proper hierarchy and for every n0, FINITE · VISIT(CALn()) CAL
n+1() FINITE · VISIT(CAL
n+1()). If is a SLIP semiAFL or a weakly k-iterative full semiAFL or a semiAFL contained in any full bounded AFL, then FINITE · VISIT() CAL() and in the last two cases, FINITE · VISIT(). If is a substitution closed full principal semiAFL and FINITE · VISIT(), then FINITE · VISIT() CAL(). If is a substitution closed full principal semiAFL generated by a language without an infinite regular set and 1 is a full semiAFL, then is contained in CALm(1) if and only if it is contained in 1. Among the applications of these results are the following. For the following families , CAL
n
() forms a proper hierarchy: =INDEXED, =ETOL, and any semiAFL contained in CF. The family CF is incomparable with CAL
m
(NESA) where NESA is the family of one-way nonerasing stack languages and INDEXED is incomparable with CAL
m
(STACK) where STACK is the family of one-way stack languages.This work was supported in part by the National Science Foundation under Grants No. DCR74-15091 and MCS-78-04725 相似文献
5.
The basic problem of interval computations is: given a function f(x
1,..., x
n) and n intervals [x
i, x
i], find the (interval) range yof the given function on the given intervals. It is known that even for quadratic polynomials f(x
1,..., x
n), this problem is NP-hard. In this paper, following the advice of A. Neumaier, we analyze the complexity of asymptotic range estimation, when the bound on the width of the input intervals tends to 0. We show that for small c > 0, if we want to compute the range with an accuracy c 2, then the problem is still NP-hard; on the other hand, for every > 0, there exists a feasible algorithm which asymptotically, estimates the range with an accuracy c 2–. 相似文献
6.
In this paper we study the problem of scheduling a set of periodic tasks nonpreemptively in hard-real-time systems, where it is critical for all requests of the tasks to be processed in time. A taskT is characterized by itsarrival time A, itsperiod P, and itsexecution time C. Starting fromA, a new request ofT arrives in everyP units of time, requestingC units of processing time, and itsdeadline coincides with the arrival of the next request ofT. All requests must be processed nonpreemptively to meet their corresponding deadlines. We show that the problem of testing the feasibility of a given task set {T
1,T
2,,T
n} satisfyingP
1+1=ki pi, wherek
i; is an integer 1 for 1i n–1, on a single processor is NP-hard in the strong sense, even if all tasks have the same arrival time. For task sets satisfyingP
i+1=K Pi, whereK is an integer 2 for 1 i n–1 and all tasks have the same arrival time, we present linear-time (in the number of requests) optimal scheduling algorithms as well as linear-time (in the number of tasks, i.e.,n) algorithms for testing feasibility in both uniprocessor and multiprocessor systems. We also extend our results to more general task sets. 相似文献
7.
Using the results obtained for the one-dimensional case in Part I (Reliable Computing
9(1) (2003), pp. 1–20) of the paper, an analysis of the two-dimensional relational expression a
1 x
1 + a
2 x
2 b, where {, , , =}, is conducted with the help of a midpoint-radius diagram and other auxiliary diagrams. The solution sets are obtained with a simple boundary-line selection rule derived using these tools, and are characterized by types of one-dimensional cuts through the solution space. A classification of basic possible solution types is provided in detail. The generalization of the approach for n-dimensional interval systems and avenues for further research are also outlined. 相似文献
8.
Luc Devroye 《Acta Informatica》1984,21(3):229-237
Summary We consider binary tries formed by using the binary fractional expansions of X
1, ...,X
n, a sequence of independent random variables with common density f on [0,1]. For H
n, the height of the trie, we show that either E(Hn)21og2
n or E(Hn)= for all n2 according to whether f
2(x)dx is finite or infinite. Thus, the average height is asymptotically twice the average depth (which is log2
n when f
2(x)dx>). The asymptotic distribution of H
n is derived as well.If f is square integrable, then the average number of bit comparisons in triesort is nlog2
n+0(n), and the average number of nodes in the trie is 0(n).Research of the author was supported in part by FCAC Grant EQ-1678 相似文献
9.
James R. Ward 《Theory of Computing Systems》1977,11(1):177-197
LetB be a Banach space ofR
n valued continuous functions on [0, ) withfB. Consider the nonlinear Volterra integral equation (*)x(t)+
o
t
K(t,s,x(s))ds. We use the implicit function theorem to give sufficient conditions onB andK (t,s,x) for the existence of a unique solutionxB to (*) for eachf B with f
B
sufficiently small. Moreover, there is a constantM>0 independent off with MfB.Part of this work was done while the author was visiting at Wright State University. 相似文献
10.
Mutual convertibility of bound entangled states under local quantum operations and classical communication (LOCC) is studied. We focus on states associated with unextendible product bases (UPB) in a system of three qubits. A complete classification of such UPBs is suggested. We prove that for any pair of UPBs S and T the associated bound entangled states S and T cannot be converted to each other by LOCC, unless S and T coincide up to local unitaries. More specifically, there exists a finite precision (S,T) > 0 such that for any LOCC protocol mapping S into a probabilistic ensemble (p, ), the fidelity between T and any possible final state satisfies F(T, ) = 1 - (S,T).PACS: 03.65.Bz; 03.67.-a; 89.70+c. 相似文献
11.
Ulrich Huckenbeck 《Theory of Computing Systems》1992,25(1):3-22
The termF-cardinality of (=F-card()) is introduced whereF:
n
n
is a partial function and is a set of partial functionsf:
n
n
. TheF-cardinality yields a lower bound for the worst-case complexity of computingF if only functionsf can be evaluated by the underlying abstract automaton without conditional jumps. This complexity bound isindependent from the oracles available for the abstract machine. Thus it is shown that any automaton which can only apply the four basic arithmetic operations needs (n logn) worst-case time to sortn numbers; this result is even true if conditional jumps witharbitrary conditions are possible. The main result of this paper is the following: Given a total functionF:
n
n
and a natural numberk, it is almost always possible to construct a set such that itsF-cardinality has the valuek; in addition, can be required to be closed under composition of functionsf,g . Moreover, ifF is continuous, then consists of continuous functions. 相似文献
12.
John H. Halton 《Journal of scientific computing》1991,6(1):61-77
This article deals with the generation of arbitrarily distributed sequences of random variables in a Fréchet space, using sequences ofcanonical random variables (c.r.v.)-i.e., independently uniformly distributed random variables taking real values in the unit interval [0, 1)-orcanonical random digits (c.r.d.)-i.e., independently uniformly distributed random variables taking integer values in some finite interval [0,B–1]. Two main results are established. First, that the members of a sequence of real random variables in [0, 1) are c.r.v. if and only if all the digits of all thebase- B digital representations of the members of the sequence are c.r.d. Secondly, that, given any sequence of random variables in a Fréchet space, there is a sequence of functions
n(
1,
2, ...,
n), forn=1, 2, 3,... (where
1,
2,...,
n,... are c.r.v.) which is distributed identically to. 相似文献
13.
In many application areas,it is important to detect outliers. The traditional engineering approach to outlier detection is that we start with some normal values x1, ...,xn, compute the sample average E, the sample standard variation , and then mark a value x as an outlier if x is outside the k0-sigma interval [E – k0 , E + k0 ] (for some pre-selected parameter k0).In real life,we often have only interval ranges [
] for the normal values x1, ...,xn. In this case,we only have intervals of possible values for the bounds
and
. We can therefore identify outliers as values that are outside all k0-sigma intervals.Once we identify a value as an outlier for a fixed k0, it is also desirable to find out to what degree this value is an outlier, i.e., what is the largest value k0 for which this value is an outlier.In this paper,we analyze the computational complexity of these outlier detection problems, provide efficient algorithms that solve some of these problems (under reasonable conditions), and list related open problems. 相似文献
14.
Consider a binary string x
0 of Kolmogorov complexity K(x
0) n. The question is whether there exist two strings x
1 and x
2 such that the approximate equalities K(x
i
x
j
) n and K(x
i
x
j
, x
k
) n hold for all 0 i, j, k 2, i j k, i k. We prove that the answer is positive if we require the equalities to hold up to an additive term O(log K(x
0)). It becomes negative in the case of better accuracy, namely, O(log n). 相似文献
15.
In this paper, we study the complexity of computing better solutions to optimization problems given other solutions. We use a model of computation suitable for this purpose, the counterexample computation model. We first prove that, if PH
P
3
, polynomial time transducers cannot compute optimal solutions for many problems, even givenn
1–
non-trivial solutions, for any >0. These results are then used to establish sharp lower bounds for several problems in the counterexample model. We extend the model by defining probabilistic counterexample computations and show that our results hold even in the presence of randomness. 相似文献
16.
On Bounding Solutions of Underdetermined Systems 总被引:1,自引:0,他引:1
Sufficient conditions for the existence and uniqueness of a solution x* D (R
n
) of Y(x) = 0 where : R
n
R
m
(m n) with C
2(D) where D R
n
is an open convex set and Y = (x)+ are given, and are compared with similar results due to Zhang, Li and Shen (Reliable Computing
5(1) (1999)). An algorithm for bounding zeros of f (·) is described, and numerical results for several examples are given. 相似文献
17.
We develop a theory of communication within branching programs that provides exponential lower bounds on the size of branching programs that are bounded alternating. Our theory is based on the algebraic concept of -branching programs, : , a semiring homomorphism, that generalizes ordinary branching programs, -branching programs [M2] andMOD
p-branching programs [DKMW].Due to certain exponential lower and polynomial upper bounds on the size of bounded alternating -branching programs we are able to separate the corresponding complexity classesN
ba
,co-N
ba
ba
, andMOD
p
-
ba
,p prime, from each other, and from that classes corresponding to oblivious linear length-bounded branching programs investigated in the past. 相似文献
18.
Conditions are presented under which the maximum of the Kolmogorov complexity (algorithmic entropy) K(1...
N
) is attained, given the cost
f(
i
) of a message 1...
N
. Various extremal relations between the message cost and the Kolmogorov complexity are also considered; in particular, the minimization problem for the function
f(
i
) – K(1...
N
) is studied. Here, is a parameter, called the temperature by analogy with thermodynamics. We also study domains of small variation of this function. 相似文献
19.
James F. Lynch 《Theory of Computing Systems》1981,15(1):127-144
LetL
* be accepted in timef(n) by a nondeterministic Turing machine. Then there is a monadic existential second-order sentence in the language of + such that for everyx*,xL if and only if a certain structureU
x
f
of cardinalityf(|x|) satisfies . It follows that ifL is accepted in nondeterministic timen
d, d a natural number, then there is a sentence whose relational symbols ared-ary or less, whose finite spectrum isL.
This research was partially supported by NSF Grants MCS78-01832 and MCS-8002695. 相似文献
20.
We consider the half-space range-reporting problem: Given a setS ofn points in d, preprocess it into a data structure, so that, given a query half-space , allk points ofS can be reported efficiently. We extend previously known static solutions to dynamic ones, supporting insertions and deletions of points ofS. For a given parameterm,n m n
d/2 and an arbitrarily small positive constant , we achieveO(m
1+) space and preprocessing time, O((n/m
d/2 logn+k) query time, and O(m1+n) amortized update time (d 3). We present, among others, the following applications: an O(n1+)-time algorithm for computing convex layers in 3, and an output sensitive algorithm for computing a level in an arrangements of planes in 3, whose time complexity is O((b+n) n, whereb is the size of the level.Work by the first author has been supported by National Science Foundation Grant CCR-91-06514. A preliminary version of this paper appeared in Agarwalet al. [2], which also contains the results of [20] on dynamic bichromatic closest pair and minimum spanning trees. 相似文献