共查询到20条相似文献,搜索用时 46 毫秒
1.
Terry Huntsberger 《Autonomous Robots》2001,11(3):341-346
Robotic missions beyond 2013 will likely be precursors to a manned habitat deployment on Mars. Such missions require robust control systems for long duration activities. Current single rover missions will evolve into deployment of multiple, heterogeneous cooperating robotic colonies. This paper describes the map-making memory and action selection mechanism of BISMARC (
iologically
nspired
ystem for
ap-based
utonomous
over
ontrol) that is currently under development at the Jet Propulsion Laboratory in Pasadena, CA (Huntsberger and Rose, Neutral Networks, 11(7/8):1497–1510). BISMARC is an integrated control system for long duration missions involving robots performing cooperative tasks. 相似文献
2.
A. Jamiołkowski 《Open Systems & Information Dynamics》2004,11(4):385-390
The main objective of this paper is to discuss correspondence between the concept of entanglement witnesses (self-adjoint operators on a composite Hilbert space
that are, in general, not positive, but are positive on separable states) and positive maps
which are not completely positive. The notion of minimal length of linear positive map is introduced and the role of this quantity in the constructing of entanglement witnesses is explained.Presented at the 36th Symposium on Mathematical Physics, ‘Open Systems & Quantum Information’, Toruń, Poland, June 9-12, 2004.Supported by the Grant PBZ-MIN-008/P03/2003. 相似文献
3.
Agent Communication Languages (ACLs) have been developed to provide a way for agents to communicate with each other supporting
cooperation in Multi-Agent Systems (MAS). In the past few years many ACLs have been proposed for MAS and new standards are
emerging such as the ACL developed by the Foundation for Intelligent Physical Agents (FIPA). Despite these efforts, an important
issue in the research on ACLs is still open and concerns how these languages should deal with failures of agents in asynchronous MAS. The Fault Tolerant Agent Communication Language (
-
) presented in this paper addresses this issue dealing with crash failures of agents.
-
provides high-level communication primitives which support a fault-tolerant anonymous interaction protocol designed for open
MAS. We present a formal semantics for
-
and a formal specification of the underlying agent architecture. This formal framework allows us to prove that the ACL satisfies
a set of well defined knowledge-level programming requirements. To illustrate the language features we show how
-
can be effectively used to write high-level executable specifications of fault tolerant protocols, such as the Contract Net
one. 相似文献
5.
Emanuele Viola 《Computational Complexity》2005,13(3-4):147-188
We study the complexity of constructing pseudorandom generators (PRGs) from hard functions, focussing on constant-depth circuits. We show that, starting from a function
computable in alternating time O(l) with O(1) alternations that is hard on average (i.e. there is a constant
such that every circuit of size
fails to compute f on at least a 1/poly(l) fraction of inputs) we can construct a
computable by DLOGTIME-uniform constant-depth circuits of size polynomial in n. Such a PRG implies
under DLOGTIME-uniformity. On the negative side, we prove that starting from a worst-case hard function
(i.e. there is a constant
such that every circuit of size
fails to compute f on some input) for every positive constant
there is no black-box construction of a
computable by constant-depth circuits of size polynomial in n. We also study worst-case hardness amplification, which is the related problem of producing an average-case hard function starting from a worst-case hard one. In particular, we deduce that there is no blackbox worst-case hardness amplification within the polynomial time hierarchy. These negative results are obtained by showing that polynomialsize constant-depth circuits cannot compute good extractors and listdecodable codes. 相似文献
6.
Coupling and self-stabilization 总被引:1,自引:0,他引:1
A randomized self-stabilizing algorithm
is an algorithm that, whatever the initial configuration is, reaches a set
of М legal configurations} in finite time with probability 1. The proof of convergence towards
is generally done by exhibiting a potential function
, which measures the “vertical” distance of any configuration to
, such that
decreases with non-null probability at each step of
. We propose here a method, based on the notion of coupling, which makes use of a “horizontal” distance
between any pair of configurations, such that
decreases in expectation at each step of
. In contrast with classical methods, our coupling method does not require the knowledge of
. In addition to the proof of convergence, the method allows us to assess the convergence rate according to two different
measures. Proofs produced by the method are often simpler or give better upper bounds than their classical counterparts, as
examplified here on Herman's mutual exclusion and Iterated Prisoner's Dilemma algorithms in the case of cyclic graphs. 相似文献
7.
8.
R. E. Nettleton 《Open Systems & Information Dynamics》1998,5(3):201-208
A linear evolution equation for a thermodynamic variable F, odd under time-reversal, is obtained from the exact equation derived by Robertson from the Liouville equation for the information-theoretic phase-space distribution. One obtains an exact expression for , the relaxation time for F. For very short
, is time-independent for t >
if C(t) F{exp(-i t)}Fo, the equilibrium time correlation, decays exponentially for t >
. is the Liouville operator. So long as C(t) is such that
decays rapidly to a steady-state value, the t limit of agrees with the fluctuation-dissipation theorem in applications to fluid transport. 相似文献
9.
10.
We give an elementary self-contained proof that the minimal Renyi entropy output of arbitrary products of channels
is additive. 相似文献
11.
12.
Hierarchical matrices (
-matrices) approximate matrices in a data-sparse way, and the approximate arithmetic for
-matrices is almost optimal. In this paper we present an algebraic approach for constructing
-matrices which combines multilevel clustering methods with
-matrix arithmetic to compute the
-inverse,
-LU, and the
-Cholesky factors of a matrix. Then the
-inverse,
-LU or
-Cholesky factors can be used as preconditioners in iterative methods to solve systems of linear equations. The numerical
results show that this method is efficient and greatly speeds up convergence compared to other approaches, such as JOR or
AMG, for solving some large, sparse linear systems, and is comparable to other
-matrix constructions based on Nested Dissection. 相似文献
13.
We present new baby steps/giant steps algorithms of asymptotically fast running time for dense matrix problems. Our algorithms compute the determinant, characteristic polynomial, Frobenius normal form and Smith normal form of a dense n × n matrix A with integer entries in
and
bit operations; here
denotes the largest entry in absolute value and the exponent adjustment by +o(1) captures additional factors
for positive real constants C1, C2, C3. The bit complexity
results from using the classical cubic matrix multiplication algorithm. Our algorithms are randomized, and we can certify that the output is the determinant of A in a Las Vegas fashion. The second category of problems deals with the setting where the matrix A has elements from an abstract commutative ring, that is, when no divisions in the domain of entries are possible. We present algorithms that deterministically compute the determinant, characteristic polynomial and adjoint of A with n3.2+o(1) and O(n2.697263) ring additions, subtractions and multiplications.To B. David Saunders on the occasion of his 60th birthday 相似文献
14.
Eric Allender Anna Bernasconi Carsten Damm Joachim von zur Gathen Michael Saks Igor Shparlinski 《Computational Complexity》2003,12(1-2):23-47
We study various combinatorial complexity measures of
Boolean functions related to some natural arithmetic problems about
binary polynomials, that is, polynomials over
.
In particular, we consider
the Boolean function deciding whether a given polynomial over
is squarefree. We obtain an exponential lower bound on the size of a
decision tree for this function, and derive an asymptotic formula, having
a linear main term, for its average sensitivity. This allows us to estimate
other complexity characteristics such as the formula size, the average decision
tree depth and the degrees of exact and approximative polynomial
representations of this function. Finally, using a different method, we
show that testing squarefreeness and irreducibility of polynomials over
cannot be done in
for any odd prime p. Similar results are
obtained for deciding coprimality of two polynomials over
as well. 相似文献
15.
The condition-based approach studies restrictions on the inputs to a distributed problem, called conditions, that facilitate its solution. Previous work considered mostly the asynchronous model of computation. This paper studies
conditions for consensus in a synchronous system where processes can fail by crashing. It describes a full classification
of conditions for consensus, establishing a continuum between the asynchronous and synchronous models, with the following
hierarchy
where
includes all conditions (and in particular the trivial one made up of all possible input vectors). For a condition
, we have:
After having established the complete hierarchy, the paper concentrates on the two last items:
. The main result is that the necessary and sufficient number of rounds needed to solve uniform consensus for a condition
(such that
) is d +1.
In more detail, the paper presents a generic synchronous early-deciding uniform consensus protocol that enjoys the following
properties. Let f be the number of actual crashes, I the input vector and
the condition the protocol is instantiated with. The protocol terminates in two rounds when
and
, and in at most d +1 rounds when
and
. (It also terminates in one round when
and
.) Moreover, whether I belongs or not to C, no process requires more than min
rounds to decide. The paper then proves a corresponding lower bound stating that at least d +1 rounds are necessary to get a decision in the worst case when
(for
and
).
This paper is based on the DISC’03 and DISC’04 conference versions MRR03,MRR04
A. Mostefaoui is currently Associate Professor at the Computer Science Department of the University of Rennes, France. He received his
Engineer Degree in Computer Science in 1990 from the University of Algiers, and a Ph.D. in Computer Science in 1994 from the
University of Rennes, France. His research interests include fault-tolerance and synchronization in distributed systems, group
communication, data consistency and distributed checkpointing. Achour Mostefaoui has published more than 70 scientific publications
and served as a reviewer for more than 20 major journals and conferences. Moreover, Achour Mostéfaoui is heading the software
engineer degree of the University of Rennes
S. Rajsbaum received a degree in Computer Engineering from the National Autonomous University of Mexico (UNAM) in 1985, and a PhD in
the Computer Science from the Technion, Israel, in 1991. Since then he has been a member of the Institute of Mathematics at
UNAM, where he is now a Full Professor with Tenure. He has been a regular visiting scientist at the Laboratory for Computer
Science of MIT. Also, he was a member of the Cambridge Research Laboratory of HP from 2000 to 2002. He was chair of the program
committee for Latin American Theoretical Informatics LATIN2002, and for ACM Principles of Distributed Computing PODC03, and
member of the Program Committee of various international conferences such as ADHOC, DISC, ICDCS, IPDPS, LADC, PODC, and SIROCCO.
His research interests are in the theory of distributed computing, especially issues related to coordination, complexity and
computability, and fault-tolerance. He has also published in graph theory and algorithms. Overall, he has published over fifty
papers in journals and international conferences. He runs the Distributed Computing Column of SIGACT News, the newsletter
of the ACM Special Interest Group on Algorithms and Computation Theory. He has been editor of several special journal issues,
such as the Special 20th PODC Anniversary Special Issue of Distributed Computing Journal (with H. Attiya) and of Computer
Networks journal special issue on algorithms.
M. Raynalhas been a professor of computer science since 1981. At IRISA (CNRS-INRIA-University joint computing research laboratory located
in Rennes), he founded a research group on Distributed Algorithms in 1983. His research interests include distributed algorithms,
distributed computing systems, networks and dependability. His main interest lies in the fundamental principles that underly
the design and the construction of distributed computing systems. He has been Principal Investigator of a number of research
grants in these areas, and has been invited by many universities all over the world to give lectures on distributed algorithms
and distributed computing. He belongs to the editorial board of several international journals. Professor Michel Raynal has
published more than 90 papers in journals (JACM, Acta Informatica, Distributed Computing, Comm. of the ACM, Information and
Computation, Journal of Computer and System Sciences, JPDC, IEEE Transactions on Computers, IEEE Transactions on SE, IEEE
Transactions on KDE, IEEE Transactions on TPDS, IEEE Computer, IEEE Software, IPL, PPL, Theoretical Computer Science, Real-Time
Systems Journal, The Computer Journal, etc.); and more than 190 papers in conferences (ACM STOC, ACM PODC, ACM SPAA, IEEE
ICDCS, IEEE DSN, DISC, IEEE IPDPS, Europar, FST&TCS, IEEE SRDS, etc.). He has also written seven books devoted to parallelism,
distributed algorithms and systems (MIT Press and Wiley). Michel Raynal has served in program committees for more than 70
international conferences (including ACM PODC, DISC, ICDCS, IPDPS, DSN, LADC, SRDS, SIROCCO, etc.) and chaired the program
committee of more than 15 international conferences (including DISC -twice-, ICDCS, SIROCCO and ISORC). He served as the chair
of the steering committee leading the DISC symposium series in 2002-2004. Michel Raynal received the IEEE ICDCS best paper
Award three times in a row: 1999, 2000 and 2001. He is a general co-chair of the IEEE ICDCS conference that will be held in
Lisbon in 2006. 相似文献
– | For values of consensus is solvable in an asynchronous system with t failures, and we obtain the known hierarchy of conditions that allows solving asynchronous consensus with more and more efficient protocols as we go from d = 0 to d = −t. |
– | For values of consensus is solvable in an asynchronous system with t failures, and we obtain the known hierarchy of conditions that allows solving asynchronous consensus with more and more efficient protocols as we go from d = 0 to d = −t. |
– | For values of d<0 consensus is known not solvable in an asynchronous system with t failures, but we obtain a hierarchy of conditions that allows solving synchronous consensus with protocols that can take more and more rounds, as we go from d = 0 to d = t. |
– | d = 0 is the borderline case where consensus can be solved in an asynchronous system with t failures, and can be solved optimally in a synchronous system. |
16.
Remco Duits Michael Felsberg Gösta Granlund Bart ter Haar Romeny 《International Journal of Computer Vision》2007,72(1):79-102
Inspired by the early visual system of many mammalians we consider the construction of-and reconstruction from- an orientation
score
as a local orientation representation of an image,
. The mapping
is a wavelet transform
corresponding to a reducible representation of the Euclidean motion group onto
and oriented wavelet
. This wavelet transform is a special case of a recently developed generalization of the standard wavelet theory and has the
practical advantage over the usual wavelet approaches in image analysis (constructed by irreducible representations of the
similitude group) that it allows a stable reconstruction from one (single scale) orientation score. Since our wavelet transform
is a unitary mapping with stable inverse, we directly relate operations on orientation scores to operations on images in a
robust manner.
Furthermore, by geometrical examination of the Euclidean motion group
, which is the domain of our orientation scores, we deduce that an operator Φ on orientation scores must be left invariant
to ensure that the corresponding operator
on images is Euclidean invariant. As an example we consider all linear second order left invariant evolutions on orientation
scores corresponding to stochastic processes on G. As an application we detect elongated structures in (medical) images and automatically close the gaps between them.
Finally, we consider robust orientation estimates by means of channel representations, where we combine robust orientation
estimation and learning of wavelets resulting in an auto-associative processing of orientation features. Here linear averaging
of the channel representation is equivalent to robust orientation estimation and an adaptation of the wavelet to the statistics
of the considered image class leads to an auto-associative behavior of the system.
The Netherlands Organization for Scientific Research is gratefully acknowledged for financial support. This work has been
supported by EC Grant IST-2003-004176 COSPAL. 相似文献
17.
We construct a linear interval system Ax = b with a 4 × 4 interval matrix whose all proper interval coefficients (there are also some noninterval ones) are of the form [–, ]. It is proved that for each > 0, the interval hull
and interval hull of the midpoint preconditioned system
satisfy
and
, hence midpoint preconditioning produces a 100% overestimation of
independently of in this case. The example was obtained as a result of an extensive MATLAB search. 相似文献
18.
The generalized Zakharov system (ZS) couples a dispersive field E (scalar or vectorial) and
nondispersive fields
with a propagating speed of
. In this paper, we extend our one-dimensional time-splitting spectral method (TSSP) for the generalized ZS into higher dimension.
A main new idea is to reformulate the multi-dimensional wave equations for the nondispersive fields into a first-order system
using a change of variable defined in the Fourier space. The proposed scheme TSSP is unconditionally stable, second-order
in time and spectrally accurate in space. Moreover, in the subsonic regime, it allows numerical capturing of the subsonic
limit without resolving the small parameters
. Numerical examples confirm these properties of this method 相似文献
19.
20.
Mark A. Reynolds 《Nexus Network Journal》2002,4(1):85-96
The square root of the Golden Section,
, is at times not given its due in discussions regarding the Golden Section. This is an unfortunate situation because its
geometric properties provide us with a unique and rarely applied design tool. In this column, geometer Mark Reynolds focuses
on the
rectangle and its abilities to create an exciting tiling, R-Tiles. 相似文献