Dimensional properties of graphs and digital spaces

Many applications of digital image processing now deal with three- and higher-dimensional images. One way to represent n-dimensional digital images is to use the specialization graphs of subspaces of the Alexandroff topological space ⁿ (where denotes the integers with the Khalimsky line topology). In this paper the dimension of any such graph is defined in three ways, and the equivalence of the three definitions is established. Two of the definitions have a geometric basis and are closely related to the topological definition of inductive dimension; the third extends the Alexandroff dimension to graphs. Diagrams are given of graphs that are dimensionally correct discrete models of Euclidean spaces, n-dimensional spheres, a projective plane and a torus. New characterizations of n-dimensional (digital) surfaces are presented. Finally, the local structure of the space ⁿ is analyzed, and it is shown that ⁿ is an n-dimensional surface for all n1.     

Lattice Image Processing: A Unification of Morphological and Fuzzy Algebraic Systems

This paper explores some aspects of the algebraic theory of mathematical morphology from the viewpoints of minimax algebra and translation-invariant systems and extends them to a more general algebraic structure that includes generalized Minkowski operators and lattice fuzzy image operators. This algebraic structure is based on signal spaces that combine the sup-inf lattice structure with a scalar semi-ring arithmetic that possesses generalized additions and -multiplications. A unified analysis is developed for: (i) representations of translation-invariant operators compatible with these generalized algebraic structures as nonlinear sup- convolutions, and (ii) kernel representations of increasing translation-invariant operators as suprema of erosion-like nonlinear convolutions by kernel elements. The theoretical results of this paper develop foundations for unifying large classes of nonlinear translation-invariant image and signal processing systems of the max or min type. The envisioned applications lie in the broad intersection of mathematical morphology, minimax signal algebra and fuzzy logic.Petros Maragos received the Diploma degree in electrical engineering from the National Technical University of Athens in 1980, and the M.Sc.E.E. and Ph.D. degrees from Georgia Tech, Atlanta, USA, in 1982 and 1985.In 1985 he joined the faculty of the Division of Applied Sciences at Harvard University, Cambridge, Massachusetts, where heworked for 8 years as professor of electrical engineering, affiliated with the interdisciplinary Harvard Robotics Lab. He has also been a consultant to several industry research groups including Xeroxs research on document image analysis. In 1993, he joined the faculty of the School of Electrical and Computer Engineering at Georgia Tech. During parts of 1996-98 he was on academic leave working as a senior researcher at the Institute for Language and Speech Processing in Athens. In 1998, he joined the faculty of the National Technical University of Athens where he is currently working as professor of electrical and computer engineering. His current research and teaching interests include the general areas of signal processing, systems theory, pattern recognition, and their applications to image processing and computer vision, and computer speech processing and recognition.He has served as associate editor for the IEEE Trans. on Acoustics, Speech, and Signal Processing, editorial board member for the Journal of Visual Communications and Image Representation, and guest editor for the IEEE Trans. on Image Processing; general chairman for the 1992 SPIE Conference on Visual Communications and Image Processing, and co-chairman for the 1996 International Symposium on Mathematical Morphology; member of two IEEE DSP committees; and president of the International Society for Mathematical Morphology.Dr. Maragos research work has received several awards, including: a 1987 US National Science Foundation Presidential Young Investigator Award; the 1988 IEEE Signal Processing Societys Paper Award for the paper Morphological Filters; the 1994 IEEE Signal Processing Societys Senior Award and the 1995 IEEE Baker Award for the paper Energy Separation in Signal Modulations with Application to Speech Analysis; and the 1996 Pattern Recognition Societys Honorable Mention Award for the paper Min-Max Classifiers. In 1995, he was elected Fellow of IEEE for his contributions to the theory and applications of nonlinear signal processing systems.     

Primality testing with fewer random bits

In the usual formulations of the Miller-Rabin and Solovay-Strassen primality testing algorithms for a numbern, the algorithm chooses candidatesx ₁,x ₂, ...,x _k uniformly and independently at random from _n , and tests if any is a witness to the compositeness ofn. For either algorithm, the probabilty that it errs is at most 2^–k .In this paper, we study the error probabilities of these algorithms when the candidates are instead chosen asx, x+1, ..., x+k–1, wherex is chosen uniformly at random from _n . We prove that fork=[1/2log₂ n], the error probability of the Miller-Rabin test is no more thann ^–1/2+o(1), which improves on the boundn ^–1/4+o(1) previously obtained by Bach. We prove similar bounds for the Solovay-Strassen test, but they are not quite as strong; in particular, we only obtain a bound ofn ^–1/2+o(1) if the number of distinct prime factors ofn iso(logn/loglogn).     

Assignment of availability objectives to components of heterogenous distributed computer systems

This paper provides a scheme to assign availability objectives to various components of a heterogenous distributed computer system using a minimum cost criteria. The availability is viewed from a user (client) perspective rather than the traditional system perspective. The user availability objectives are classified in terms of operational and inherent availabilities. Such a classification enables the designers to take into account the user expectations in a more realistic way thus minimizing the high cost of providing fault tolerant systems. The user availability objectives are then translated into the system availability objectives by relating the availability needs of each distinct user group to system components utilized by that group.     

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.     

The Possibilistic Handling of Irrelevance in Exception-Tolerant Reasoning

In nonmonotonic reasoning, the preferential system P is known to provide reasonable but very cautious conclusions, and in particular, preferential inference is blocked by the presence of irrelevant properties. When using Lehmann's rational closure, the inference machinery, which is then more productive, may still remain too cautious. These two types of inference can be represented using a possibility theory-based semantics. To overcome the cautiousness of system P, we first progressively augment preferential inference with two extensions which are in between system P and rational closure. Then, in order to overcome some remaining limitations of rational closure the second half of this paper focuses more particularly on the use of (contextual) independence assumptions of the form: the fact that is true (or is false) does not affect the validity of the rule normally if then . The modelling of such independence assumptions is discussed in the possibilistic framework. Algorithms are provided to jointly handle default rules and independence relations, and to check their multual consistency.     

Architecture and Environment for Enabling Interactive Grids

Traditional use of grid computing allows a user to submit batch jobs in a grid environment. We believe, next generation grids will extend the application domain to include interactive graphical sessions. We term such grids Interactive Grids. In this paper, we describe some of the challenges involved in building Interactive Grids. These include fine grain access control, performance QoS guarantees, dynamic account management, scheduling, and user data management. We present the key architectural concepts in building Interactive Grids viz. hierarchical sessions, hierarchical admission control, hierarchical agents, classes of dynamic accounts, application profiling, user data management, scheduling for interactive sessions, persistent environment settings, and exporting remote desktop. We also describe IGENV, an environment for enabling interactive grids. IGENV consists of GISH –Grid Interactive Shell, Controlled Desktop, SAC –Session Admission Control module, GMMA –Grid Monitoring and Management Agents, and Policy Engine. We also present our testbed implementation for Interactive Grids using and extending Globus Toolkit 2.0 for the Grid middleware infrastructure, and VNC as the remote display technology.     

A criterion on thinning in digital pictures

Letp = (²,m,n,B) be a two-dimensional digital picture, where adjacency (m, n) is (4,8), (8,4) or (6,6). We give the conditions for obtaining those points which can be deleted inp, preserving the topology type. In particular, the connectivity and Euler's characteristics of the picture remain unchanged.The necessary computations for the implementation of this deletion procedure are, to a great extent, simplified with respect to the results known up to now, since it is not necessary to explicitly obtain the simple points of the two-dimensional digital picture.     

Impedance Control with On-Line Neural Network Compensator for Dual-Arm Robots

A controller design strategy of dual-arm robots is proposed in this paper. The controller consists of a central controller and three force controllers. The central controller is used to calculate each arms force command according to the desired object motion. A force controller is used in each arm to track the commanding force. Another force controller is used to track the desired contact force between the manipulated object and its environment. The force controller can be partitioned into three parts. The computed torque method is used to linearize and decouple the dynamics of a manipulator. An impedance controller is then added to regulate the mechanical impedance between the manipulator and its environment. In order to track a reference force signal, an on-line neural network is used to compensate the effect of unknown parameters of the manipulator and environment. The simulation results are reported to show the performance of the neural network compensator.     

The (n,k)-bounded emptiness-problem for probabilistic acceptors and related problems

Summary This paper investigates some problems which change their status from being unsolvable to solvable when varying the values of parameters. Let EMPTY(n, k) be the problem to decide for all rational probabilistic acceptors B with at most n states and k input symbols and for all rational numbers , whether the accepted language L(B,) is empty. It turns out that EMPTY(2, k) is solvable for all k, while EMPTY (9,9) and EMPTY (65,2) are not. Some problems of the theory of -rational power series are shown to be unsolvable, too, even for small values of the problemparameters.     

Control surface failure detection and accommodation using neuro-controllers

The ability of neural networks to learn from repeated exposure to system characteristics has made them a popular choice for many applications in linear and non-linear control. In this paper, the capabilities of neural networks in detecting and accommodating control surface failures for a modified F/A-18 super-manoeuverable fighter aircraft are examined. To detect and accommodate a failure in the thrust vectoring vane during a pitch manoeuvre, a hierarchical neuro-controller is designed using thrust vectoring, symmetric leading edge flap and the throttle. This neuro- controller is then used as the fault accommodating neuro- controller. A separate neural network is trained to detect failures in the thrust vectoring vane. The performance of the controller and fault-detection networks are verified using a numerical simulation of a longitudinal model of the aircraft.     

New Sequences with Zero Autocorrelation

New families of unimodular sequences of length p = 3f + 1 with zero autocorrelation are described, p being a prime. The construction is based on employing Gauss periods. It is shown that in this case elements of the sequences are algebraic numbers defined by irreducible polynomials over of degree 12 (for the first family) and 6 (for the second family). In turn, these polynomials are factorized in some extension of the field into polynomials of degree, respectively, 4 and 2, which are written explicitly. For p = 13, using the exhaustive search method, full classification of unimodular sequences with zero autocorrelation is given.     

Localization of hybrid controllers for manipulation on unknown constraints

A robotic control problem is proposed in which a six degree of freedom manipulator is to explore the surface of an object which isa priori unknown to the controller. Choice of an exploration strategy is discussed. The exploration strategy developed uses the maximal freedom of choice allowed under the restrictions of the problem. In particular, it is shown that any admissible reference trajectory can be used, provided it lies in a two-dimensional manifold which maps continuously into the surface. The inverse kinematic velocity problem is then solved using pseudo-inverses which fully exploit the redundancy of the system. The controller used as an example uses computed torque for linearization and compliant motion theory for movement along the desired path. The solution to the inverse kinematic problem together with the on-line generation of selection-mappings constitute a hybrid force/velocity controller. Successful exploration is shown to depend heavily on reliable force control, so PI force feedback is also proposed. Simulation and experimental results demonstrate the effectiveness of the overall design.This work was supported in part by the National Science Foundation under grant No. MSM-8700753 and in part by the Office of Naval Research under grant No. N00014-91-J-1621.     

Context calibration

The basic starting point of this paper is that context constitutes most of the user interface when doing VR-related experiments, but even so one bases performance measures on only a few active tasks. Thus, in order to meaningfully compare results obtained in vastly different experiments one needs to somehow subtract the contribution to observables that are due to the context. For the case where one is investigating whether changes in one observable causes changes in another, a method, context calibration, is proposed that does just that. This method is expected to, to a large extent, factor out the part of one's results that are due to factors that are not explicitly considered when evaluating the experiment, factors that the experimenter might not even suspect influences the experiment. A procedure for systematically investigating the theoretical assumptions underlying context calibration is also discussed as is an initial experiment adhering to the proposed methodology.     

Application of artificial neural network and fuzzy logic in a case-based system for initial process parameter setting of injection molding

Determination of initial process meters for injection molding is a highly skilled job and based on skilled operators know-how and intuitive sense acquired through long-term experience rather than a theoretical and analytical approach. Facing with the global competition, the current trial-and-error practice becomes inadequate. In this paper, application of artificial neural network and fuzzy logic in a case-based system for initial process meter setting of injection molding is described. Artificial neural network was introduced in the case adaptation while fuzzy logic was employed in the case indexing and similarity analysis. A computer-aided system for the determination of initial process meter setting for injection molding based on the proposed techniques was developed and validated in a simulation environment. The preliminary validation tests of the system have indicated that the system can determine a set of initial process meters for injection molding quickly without relying on experienced molding personnel, from which good quality molded parts can be produced.     

Proof complexity in algebraic systems and bounded depth Frege systems with modular counting

We prove a lower bound of the formN ⁽¹⁾ on the degree of polynomials in a Nullstellensatz refutation of theCount _q polynomials over _m , whereq is a prime not dividingm. In addition, we give an explicit construction of a degreeN ⁽¹⁾ design for theCount _q principle over _m . As a corollary, using Beameet al. (1994) we obtain a lower bound of the form 2 ^N(1) for the number of formulas in a constant-depth Frege proof of the modular counting principleCount _q ^N from instances of the counting principleCount _m ^M .We discuss the polynomial calculus proof system and give a method of converting tree-like polynomial calculus derivations into low degree Nullstellensatz derivations.Further we shwo that a lower bound for proofs in a bounded depth Frege system in the language with the modular counting connectiveMOD _p follows from a lower bound on the degree of Nullstellensatz proofs with a constant number of levels of extension axioms, where the extension axioms comprise a formalization of the approximation method of Razborov (1987) and Smolensky (1987) (in fact, these two proof systems are basically equivalent).     

Modular Control and Coordination of Discrete-Event Systems

In the supervisory control of discrete-event systems based on controllable languages, a standard way to handle state explosion in large systems is by modular supervision: either horizontal (decentralized) or vertical (hierarchical). However, unless all the relevant languages are prefix-closed, a well-known potential hazard with modularity is that of conflict. In decentralized control, modular supervisors that are individually nonblocking for the plant may nevertheless produce blocking, or even deadlock, when operating on-line concurrently. Similarly, a high-level hierarchical supervisor that predicts nonblocking at its aggregated level of abstraction may inadvertently admit blocking in a low-level implementation. In two previous papers, the authors showed that nonblocking hierarchical control can be guaranteed provided high-level aggregation is sufficiently fine; the appropriate conditions were formalized in terms of control structures and observers. In this paper we apply the same technique to decentralized control, when specifications are imposed on local models of the global process; in this way we remove the restriction in some earlier work that the plant and specification (marked) languages be prefix-closed. We then solve a more general problem of coordination: namely how to determine a high level coordinator that forestalls conflict in a decentralized architecture when it potentially arises, but is otherwise minimally intrusive on low-level control action. Coordination thus combines both vertical and horizontal modularity. The example of a simple production process is provided as a practical illustration. We conclude with an appraisal of the computational effort involved.     

Two and three-quarter dimensional meshing facilitators

This paper presents generated enhancements for robust two and three-quarter dimensional meshing, including: (1) automated interval assignment by integer programming for submapped surfaces and volumes, (2) surface submapping, and (3) volume submapping. An introduction to the simplex method, an optimization technique of integer programming, is presented. Simplification of complex geometry is required for the formulation of the integer programming problem. A method of i-j unfolding is defined which explains how irregular geometry can be realigned into a simplified form that is suitable for submap interval assignment solutions. Also presented is the processes by which submapping eliminates the decomposition of surface geometry, through a pseudodecomposition process, producing suitable mapped meshes. The process of submapping involves the creation of interpolated virtual edges, user defined vertex types and i-j-k space traversals. The creation of interpolated virtual edges is the method by which submapping automatically subdivides surface geometry. The interpolated virtual edge is formulated according to an interpolation scheme using the node discretization of curves on the surface. User defined vertex types allow direct user control of surface decomposition and interval assignment by modifying i-j-k space traversals. Volume submapping takes the geometry decomposition to a higher level by using mapped virtual surfaces to eliminate decomposition of complex volumes.     

Neural networks for the EMOBOT robot control architecture

Within the EMOBOT approach to adaptive behaviour, the task of learning to control the behaviour is one of the most interesting challenges. Learned action selection between classically implemented control mechanisms, with respect to internal values and sensor readings, provides a way to modulate a variety of behavioural capabilities. To demonstrate the potential of the learning emotional controller, we chose a 10-5-12 MLP to implement the , controller of the EMOBOT. Since no teacher vector is available for the chosen task, the neural network is trained with a reinforcement strategy. The emotion-value-dependent reinforcement signal, together with the output of the network, is the basis with which to compute an artificial teacher vector. Then, the established gradient descent method (backpropagation of error) is applied to train the neural network. First results obtained by extensive simulations show that a still unrevealed richness in behaviour can be realised when using the neural-network-based learning emotional controller.