Biologically Inspired Autonomous Rover Control

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.     

Stability of Linear Difference and Differential Inclusions

Any given n×n matrix A is shown to be a restriction, to the A-invariant subspace, of a nonnegative N×N matrix B of spectral radius (B) arbitrarily close to (A). A difference inclusion , where is a compact set of matrices, is asymptotically stable if and only if can be extended to a set of nonnegative matrices B with or . Similar results are derived for differential inclusions.     

A Time-Splitting Spectral Method for the Generalized Zakharov System in Multi-Dimensions

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     

The Complexity of Learning According to Two Models of a Drifting Environment

We show that a bound on the rate of drift of the distribution generating the examples is sufficient for agnostic learning to relative accuracy , where c > 0 is a constant; this matches a known necessary condition to within a constant factor. We establish a sufficient condition for the realizable case, also matching a known necessary condition to within a constant factor. We provide a relatively simple proof of a bound of + on the sample complexity of agnostic learning in a fixed environment.     

Congruences et Automorphismes des Automates Finis

Summary We study a class of congruences of strongly connected finite automata, called the group congruences, which may be defined in this way: every element fixing any class of the congruence induces a permutation on this class. These congruences form an ideal of the lattice of all congruences of the automaton and we study the group associated with the maximal group congruence (maximal induced group) with respect to the Suschkevitch group of the transition monoid of . The transitivity equivalence of the subgroups of the automorphism group of are found to be the group congruences associated with regular groups, which form also in ideal of the lattice of congruences of . We then characterize the automorphism group of with respect to the maximal induced group. As an application, we show that, given a group G and an automaton , there exists an automaton whose automorphism group is isomorphic to G and such that the quotient by the automorphism congruence is .     

The computational complexity of recognizing permutation functions

Let be a finite field withq elements and a rational function over . No polynomial-time deterministic algorithm is known for the problem of deciding whetherf induces a permutation on . The problem has been shown to be in co-R co-NP, and in this paper we prove that it is inR NP and hence inZPP, and it is deterministic polynomial-time reducible to the problem of factoring univariate polynomials over . Besides the problem of recognizing prime numbers, it seems to be the only natural decision problem inZPP unknown to be inP. A deterministic test and a simple probabilistic test for permutation functions are also presented.     

Lower Bound Methods and Separation Results for On-Line Learning Models

We consider the complexity of concept learning in various common models for on-line learning, focusing on methods for proving lower bounds to the learning complexity of a concept class. Among others, we consider the model for learning with equivalence and membership queries. For this model we give lower bounds on the number of queries that are needed to learn a concept class in terms of the Vapnik-Chervonenkis dimension of , and in terms of the complexity of learning with arbitrary equivalence queries. Furthermore, we survey other known lower bound methods and we exhibit all known relationships between learning complexities in the models considered and some relevant combinatorial parameters. As it turns out, the picture is almost complete. This paper has been written so that it can be read without previous knowledge of Computational Learning Theory.     

Finiteness in Infinite-Valued Łukasiewicz Logic

In this paper we deepen Mundici's analysis on reducibility of the decision problem from infinite-valued ukasiewicz logic to a suitable m-valued ukasiewicz logic _m , where m only depends on the length of the formulas to be proved. Using geometrical arguments we find a better upper bound for the least integer m such that a formula is valid in if and only if it is also valid in _m. We also reduce the notion of logical consequence in to the same notion in a suitable finite set of finite-valued ukasiewicz logics. Finally, we define an analytic and internal sequent calculus for infinite-valued ukasiewicz logic.     

Computational Finite-Element Schemes for Optimal Control of an Elliptic System with Conjugation Conditions

New optimal control problems are considered for distributed systems described by elliptic equations with conjugate conditions and a quadratic minimized function. Highly accurate computational discretization schemes are constructed for the case where a feasible control set coincides with the full Hilbert space of controls.     

Combining the Perceptron Algorithm with Logarithmic Simulated Annealing

We present results of computational experiments with an extension of the Perceptron algorithm by a special type of simulated annealing. The simulated annealing procedure employs a logarithmic cooling schedule , where is a parameter that depends on the underlying configuration space. For sample sets S of n-dimensional vectors generated by randomly chosen polynomials , we try to approximate the positive and negative examples by linear threshold functions. The approximations are computed by both the classical Perceptron algorithm and our extension with logarithmic cooling schedules. For and , the extension outperforms the classical Perceptron algorithm by about 15% when the sample size is sufficiently large. The parameter was chosen according to estimations of the maximum escape depth from local minima of the associated energy landscape.      

A Parallel Logarithmic Order Algorithm for General Multibody System Dynamics

A novel optimal order optimal resource parallel multibody algorithm with general system applicability is derived directly from the sequential recursive methods and the most recent developments in recursive constraint treatments. This new Recursive Coordinate Reduction Parallelism (RCRP) is the first optimal order parallel direct method with a sequential implementation that is exactly the efficient algorithm. Consequently, the RCRP sets new benchmarks for performance over a wide range of problem size and parallel resources. Comparisons to existing methods also demonstrate that the RCRP is presently the best general parallel method.     

A semantically complete extension sequence of the system $$\mathcal{L}^* $$

In this paper, the method of well-combined semantics and syntax proposed by Pavelka is applied to the research of the propositional calculus formal system . The partial constant values are taken as formulas, formulas are fuzzified in two manners of semantics and syntax, and inferring processes are fuzzified. A sequence of new extensions { } of the system is proposed, and the completeness of is proved.     

Staircase visibility and computation of kernels

Let be some set of orientations, that is, . We consider the consequences of defining visibility based on curves that are monotone with respect to the orientations in . We call such curves -staircases. Two points p andq in a polygonP are said to -see each other if an -staircase fromp toq exists that is completely contained inP. The -kernel of a polygonP is then the set of all points which -see all other points. The -kernel of a simple polygon can be obtained as the intersection of all {}-kernels, with . With the help of this observation we are able to develop an algorithm to compute the -kernel of a simple polygon, for finite . We also show how to compute theexternal -kernel of a polygon in optimal time . The two algorithms are combined to compute the ( -kernel of a polygon with holes in time .This work was supported by the Deutsche Forschungsgemeinschaft under Grant No. Ot 64/5-4 and the Natural Sciences and Engineering Research Council of Canada and Information Technology Research Centre of Ontario.     

Renormalization group analysis of turbulence. I. Basic theory

We develop the dynamic renormalization group (RNG) method for hydrodynamic turbulence. This procedure, which uses dynamic scaling and invariance together with iterated perturbation methods, allows us to evaluate transport coefficients and transport equations for the large-scale (slow) modes. The RNG theory, which does not include any experimentally adjustable parameters, gives the following numerical values for important constants of turbulent flows: Kolmogorov constant for the inertial-range spectrumC _K=1.617; turbulent Prandtl number for high-Reynolds-number heat transferP _t =0.7179; Batchelor constantBa=1.161; and skewness factor¯S ₃=0.4878. A differentialK- model is derived, which, in the high-Reynolds-number regions of the flow, gives the algebraic relationv=0.0837 K²/ , decay of isotropic turbulence asK=O(t ^–1.3307), and the von Karman constant=0.372. A differential transport model, based on differential relations betweenK, , and, is derived that is not divergent whenK 0 and is finite. This latter model is particularly useful near walls.     

A Modular Algorithm for Computing Cohomologies of Lie Algebras and Superalgebras

The paper describes an improved algorithm for computing cohomologies of Lie (super)algebras. The original algorithm developed earlier by the author of this paper is based on the decomposition of the entire cochain complex into minimal subcomplexes. The suggested improvement consists in the replacement of the arithmetic of rational or integer numbers by a more efficient arithmetic of modular fields and the use of the relationship dim H ^k( _p) dimH ^k() between the dimensions of cohomologies over an arbitrary modular field _p = /p and the filed of rational numbers . This inequality allows us to rapidly find subcomplexes for which dimH ^k( _p) > 0 (the number of such subcomplexes is usually not great) using computations over an arbitrary _p and, then, carry out all required computations over in these subcomplexes.     

Modelling Asynchrony with a Synchronous Model

The I/O automaton paradigm of Lynch and Tuttle models asynchrony through an interleaving parallel composition. The recognition that such interleaving models in fact can be viewed as special cases of synchronous parallel composition has been very limited. Let be any set of finite-state I/O automata drawing actions from a fixed finite set containing a subset . In this article we establish a translation T : to a class of -automata closed under a synchronous parallel composition, for which T is monotonic with respect to implementation relative to , and linear with respect to composition. Thus, for A¹, ..., A, B¹, ..., B and A = A¹ ... A, B = B¹ ... B, if is the set of actions common to both A and B, then A implements B (in the sense of I/O automata) if and only if the -automaton language containment (T(A¹) ... T(A)) (T(B¹) ... T(B)) obtains, where denotes the interleaving parallel composition on and denotes the synchronous parallel composition on . For the class , we use the L-process model of -automata. This result enables one to verify systems specified by I/O automata through model-checkers such as COSPAN or SMV, that operate on models with synchronous parallel composition. The translation technique generalizes to other interleaving models, although in each case, the translation map must match the specific model.     

A Note on the Rational Closure of Knowledge Bases with Both Positive and Negative Knowledge

The notion of the rational closure of a positive knowledge base K of conditional assertions | (standing for if then normally ) was first introduced by Lehmann (1989) and developed by Lehmann and Magidor (1992). Following those authors we would also argue that the rational closure is, in a strong sense, the minimal information, or simplest, rational consequence relation satisfying K. In practice, however, one might expect a knowledge base to consist not just of positive conditional assertions, | , but also negative conditional assertions, _i (standing for not if then normally . Restricting ourselves to a finite language we show that the rational closure still exists for satisfiable knowledge bases containing both positive and negative conditional assertions and has similar properties to those exhibited in Lehmann and Magidor (1992). In particular an algorithm in Lehmann and Magidor (1992) which constructs the rational closure can be adapted to this case and yields, in turn, completeness theorems for the conditional assertions entailed by such a mixed knowledge base.     

An Algebraic Approach to Propositional Fuzzy Logic

We investigate the variety corresponding to a logic (introduced in Esteva and Godo, 1998, and called there), which is the combination of ukasiewicz Logic and Product Logic, and in which Gödel Logic is interpretable. We present an alternative (and slightly simpler) axiomatization of such variety. We also investigate the variety, called the variety of algebras, corresponding to the logic obtained from by the adding of a constant and of a defining axiom for one half. We also connect algebras with structures, called f-semifields, arising from the theory of lattice-ordered rings, and prove that every algebra can be regarded as a structure whose domain is the interval [0, 1] of an f-semifield , and whose operations are the truncations of the operations of to [0, 1]. We prove that such a structure is uniquely determined by up to isomorphism, and we establish an equivalence between the category of algebras and that of f-semifields.     

Concurrent Sample Path Analysis of Discrete Event Systems

The sample path constructability problem for Discrete Event Systems (DES) involves the observation of a sample path under a particular parameter value of the system with the requirement to concurrently construct multiple sample paths of the DES under different values using only information available along the given sample path. This allows the on-line estimation of performance measures , not available in closed form, over a range of values of . We present a sample path coupling approach that solves the problem without imposing any restrictions on the event processes in the system. A specific time warping algorithm is described and its performance is analyzed in terms of computational cost. Our approach is illustrated through a number of simulation results.