Turing machines with access to history

We study remembering Turing machines, that is Turing machines with the capability to access freely the history of their computations. These devices can detect in one step via the oracle mechanism whether the storage tapes have exactly the same contents at the moment of inquiry as at some past moment in the computation. The s(n)-space-bounded remembering Turing machines are shown to be able to recognize exactly the languages in the time-complexity class determined by bounds exponential in s(n). This is proved for deterministic, non-deterministic, and alternating Turing machines.     

A comparative study of stochastic optimization methods in electric motor design

The efficiency of universal electric motors that are widely used in home appliances can be improved by optimizing the geometry of the rotor and the stator. Expert designers traditionally approach this task by iteratively evaluating candidate designs and improving them according to their experience. However, the existence of reliable numerical simulators and powerful stochastic optimization techniques make it possible to automate the design procedure. We present a comparative study of six stochastic optimization algorithms in designing optimal rotor and stator geometries of a universal electric motor where the primary objective is to minimize the motor power losses. We compare three methods from the domain of evolutionary computation, generational evolutionary algorithm, steady-state evolutionary algorithm and differential evolution, two particle-based methods, particle-swarm optimization and electromagnetism-like algorithm, and a recently proposed multilevel ant stigmergy algorithm. By comparing their performance, the most efficient method for solving the problem is identified and an explanation of its success is offered.     

Maximum throughput of multiple access channels in adversarial environments

We consider deterministic distributed broadcasting on multiple access channels in the framework of adversarial queuing. Packets are injected dynamically by an adversary that is constrained by the injection rate and the number of packets that may be injected simultaneously; the latter we call burstiness. A protocol is stable when the number of packets in queues at the stations stays bounded. The maximum injection rate that a protocol can handle in a stable manner is called the throughput of the protocol. We consider adversaries of injection rate 1, that is, of one packet per round, to address the question if the maximum throughput 1 can be achieved, and if so then with what quality of service. We develop a protocol that achieves throughput 1 for any number of stations against leaky-bucket adversaries. The protocol has O(n²+\textburstiness){\mathcal{O}(n^2+\text{burstiness})} packets queued simultaneously at any time, where n is the number of stations; this upper bound is proved to be best possible. A protocol is called fair when each packet is eventually broadcast. We show that no protocol can be both stable and fair for a system of at least two stations against leaky-bucket adversaries. We study in detail small systems of exactly two and three stations against window adversaries to exhibit differences in quality of broadcast among classes of protocols. A protocol is said to have fair latency if the waiting time of packets is O(\textburstiness){\mathcal{O}(\text{burstiness})}. For two stations, we show that fair latency can be achieved by a full sensing protocol, while there is no stable acknowledgment based protocol. For three stations, we show that fair latency can be achieved by a general protocol, while no full sensing protocol can be stable. Finally, we show that protocols that either are fair or do not have the queue sizes affect the order of transmissions cannot be stable in systems of at least four stations against window adversaries.     

Operations on logic functions and variables through sign Haar spectra

A non-linear transform, called “sign Haar transform” has recently been introduced. The transform is unique and converts binary/ternary vectors into ternary spectral domain. Recursive definitions for the calculation of sign Haar transform are developed. Essential properties of logic functions and variables in the spectral domain of a quantized transform based on Haar functions are presented. Sign Haar transform has the smallest computational cost of all the quantized transforms. The properties of logic functions are listed for two different codings of incompletely specified functions.     

Visual Target Localization with the Spincopter

The goal of the Spincopter project was to design an energy efficient aircraft capable of autorotation glide that could be used for both indoor and outdoor surveillance. This paper demonstrates how to utilize the self-rotating capability of the Spincopter in order to acquire a 3D image of its environment and localize predefined object(s). The omnidirectional capabilities of such an UAV extends the otherwise very limited field of view of conventional cameras usually used for aerial photography and surveillance. The paper presents the theoretical background and the actual implementation of such a system. It presents the resulting images and offers a brief survey of the image quality.     

Hybrid Adaptive Control for Aerial Manipulation

This paper presents a control scheme to achieve dynamic stability in a mobile manipulating unmanned aerial vehicle (MM-UAV) using a combination of Gain scheduling and Lyapunov based model reference adaptive control (MRAC). Our test flight results indicate that we can accurately model and control our aerial vehicle when both moving the manipulators and interacting with target objects. Using the Lyapunov stability theory, the controller is proven to be stable. The simulation results showed how the MRAC is capable of stabilizing the oscillations produced from the unstable PI-D attitude control loop. Finally a high level control system based on a switching automaton is proposed in order to ensure the saftey of the aerial manipulation missions.     

Application of the Extended Distance Transformation in digital image colorization

In this paper we present a novel colorization scheme that takes advantage of the modified morphological distance transform to propagate the color, scribbled by a user on the grayscale image. First, based on the scribbled image, the topological distance values are computed for each image pixel, describing its distance to the inserted color markers. These values are then complemented with the structural information and luminance changes derived from the original grayscale image. The distances are then used along with gradient based features to reproduce original image structures while propagating the new colors obtained during the additive color blending process. Extensive experiments performed on various kinds of natural images demonstrated the effectiveness of the proposed colorization method. They also showed that the main advantage of the presented algorithm is its computational speed and ability to produce visually pleasing colorization results promptly after providing the color information.     

Embedding new observations via sparse-coding for non-linear manifold learning

Non-linear dimensionality reduction techniques are affected by two critical aspects: (i) the design of the adjacency graphs, and (ii) the embedding of new test data—the out-of-sample problem. For the first aspect, the proposed solutions, in general, were heuristically driven. For the second aspect, the difficulty resides in finding an accurate mapping that transfers unseen data samples into an existing manifold. Past works addressing these two aspects were heavily parametric in the sense that the optimal performance is only achieved for a suitable parameter choice that should be known in advance.