This paper investigates properties of space-bounded "two-dimensional Turing machines (2-tm's)," whose input tapes are restricted to square ones, with bounded input head reversals in vertical direction. We first investigate a relationship between determinism and nondeterminism for space-bounded and input head reversal-bounded 2-tm's. We then investigate how the number of input head reversals affects the accepting power of sublinearly space-bounded 2-tm's. Finally, we investigate necessary and sufficient spaces for three-way 2-tm's to simulate four-way two-dimensional finite automata with constant input head reversals.

This paper defines the distributed arrangement selection problem in a line network in a distributed context and describes the design of a strictly-time-optimal algorithm which solves the problem with a limited local memory space. The problem is regarded as a combined distributed sorting and k-selection problem, namely a problem of sorting elements that are not larger than the kth minimum element in predetermined processes. The algorithm also provides a solution to a resource allocation problem in a line network in a strictly-optimal time.

By a worst input (for the selection phase of Heapsort) of size n, we mean a heap of size n such that, if it is given to the selection phase of Heapsort, the number of movements of data is maximum among the numbers of movements for all heaps of size n. D. E. Knuth showed a special type of worst inputs which we will call the K-type heaps. His definition of K-type heaps was by the induction on the size n. We give one characterization of K-type worst heaps that is based on their tree structure. This characterization gives more information on the tree structure of K-type heaps than the Knuth's definition.

To measure temperature dependent complex permittivity of dielectric materials, a rectangular cavity resonator with a heating system has been developed. In the experiment, microwave power with the frequency of 2.45 GHz is applied to heat the dielectric material. In order to reduce the error of the complex permittivity of dielectric material obtained from the perturbation method, an electromagnetic (EM) field simulator is applied which uses the Transmission Line Modeling (TLM) method. The uniformity of the temperature is also discussed by the use of heat transfer equation which applies the results of TLM simulation. It is found from the results that the accurate temperature dependence of complex permittivity of the material can be obtained by the method presented here.

This letter presents parallel algorithms for matrix multiplication and the fast Fourier transform (FFT) that are significant problems arising in engineering and scientific applications. The proposed algorithms are designed on a 3-dimensional processor array with separable buses (PASb). We show that a PASb consisting of N N h processors can compute matrix multiplication of size N N and the FFT of size N in O(N/h+log N) time, respectively. In order to examine ease of hardware implementation, we also evaluate the VLSI complexity of the algorithms. A result obtained achieves an optimal bound on area-time complexity when h=O(N/log N).

Software obfuscation is a promising approach to protect intellectual property rights and secret information of software in untrusted environments. Unfortunately previous software obfuscation techniques share a major drawback that they do not have a theoretical basis and thus it is unclear how effective they are. Therefore we propose new software obfuscation techniques in this paper. The techniques are based on the difficulty of interprocedural analysis of software programs. The essence of our obfuscation techniques is a new complexity problem to precisely determine the address a function pointer points to in the presence of arrays of function pointers. We show that the problem is NP-hard and the fact provides a theoretical basis for our obfuscation techniques. Furthermore, we have already implemented a prototype tool that obfuscates C programs according to our proposed techniques and in this paper we describe the implementation and discuss the experiments results.

When we use an adaptive array antenna (AAA) with the minimum mean square error (MMSE) criterion under the multipath environment, where the receiving signal level varies, it is difficult for the AAA to converge because of the distortion of the desired wave. Then, we need the equalization both in space and time domains. A tapped-delay-line adaptive array antenna (TDL-AAA) and the AAA with linear equalizer (AAA-LE) have been proposed as simple space-temporal equalization. The AAA-LE has not utilized the recursive least square (RLS) algorithm. In this paper, we propose a space-temporal simultaneous processing equalizer (ST-SPE) that is an AAA-LE with the RLS algorithm. We proposed that the first tap weight of the LE should be fixed and the necessity of that is derived from a normal equation in the MMSE criterion. We achieved the space-temporal simultaneous equalization with the RLS algorithm by this configuration. The ST-SPE can reduce the computational complexity of the space-temporal joint equalization in comparison to the TDL-AAA, when the ST-SPE has almost the same performance as the TDL-AAA in multipath environment with minimum phase condition such as appeared at line-of-sight (LOS).

The fields in the junctions between straight and curved rectangular waveguides are analyzed by using the method of separating variables. This method was succeeded because the authors developed the method of numerical calculation of the cylindrical functions of complex order. As a result, we numerically calculate the reflection and transmission coefficients in the junctions in various situations, and we compare these results with the results by the perturbation method and with the results by Jui-Pang et al.

The UCHT (Unified Complex Hadamard Transform) has been proposed as a new family of spreading sequences for DS-SSMA systems recently. In this Letter, the periodic autocorrelation (PAC) properties of the Unified Complex Hadamard Transform (UCHT) sequences are analyzed. Upper bounds for the out-of-phase PAC are derived for two groups of the UCHT sequences, namely the HSP-UCHT and the NHSP-UCHT sequences (the later is a more general representation of the well-known Walsh-Hadamard (WH) sequences). A comparison of the two bounds is performed. It turns out that the HSP-UCHT sequences have a lower upper bound for the out-of-phase PAC. This makes the HSP-UCHT sequences more effective than the WH sequences in combating multipath effect for DS-SSMA systems.

The lossy magnetic composite material made from soft magnetic metal powder and rubber is widely used as an EMI countermeasure material, due to its higher magnetic loss than those of spinel ferrites in microwave frequencies. In this paper, we clarify the material characteristics by measuring the relative complex permeability r and relative complex permittivity r of two kinds of composite materials in microwave frequencies. Since the composite materials are anisotropic, both r and r are measured as diagonal tensors by utilizing extended S-parameter method. The results show that the imaginary part of r of flaky-powder composite exceeded the Snoek's limit for the spinel ferrites which has been reported so far. The measured r and r are partially compared with those measured by cavity resonator method, and good agreement is obtained.

Hypercomplex coefficient digital filters provide several attractive advantages such as compact realization with reduced system order, inherent parallelism. However, they also possess a drawback in that a multiplier requires a large amount of computations. This paper proposes a computationally efficient implementation of digital filters whose coefficient is a type of hypercomplex number; a bicomplex number. By decomposing a bicomplex multiplier into two parallel complex multipliers, we show that hypercomplex digital filters can be implemented as two parallel complex digital filters. The proposed implementation offers more than a 60% reduction in the count of real multipliers.

In this paper a low-complexity and high-resolution algorithm to estimate the magnitude of complex numbers is presented. Starting from a review of previous art, the new algorithm has been derived to improve precision performance without any penalty in hardware complexity. As a case example, a semi-custom VLSI implementation for 10 bit 2's complement input data has been performed. A mean square error and mean error performance improvement of nearly one order of magnitude has been demonstrated for an hardware complexity increase of roughly 34% with respect to previously presented solutions.

STM/STS measurements have been carried out for TTF-TCNQ complex films evaporated on hydrogen-terminated silicon substrates, and the variation of tunneling spectra has been investigated on morphologically different crystal grains. Very thin semiconductive adsorbed layers were found to cover the as-deposited film surfaces. By removing the adsorbed layers, the intrinsic electronic structures of two different phases were revealed. A 'needle phase' which appears at the early stage of film growth has a semiconductive character and a 'granular phase' which grows later has a metallic character similar to bulk crystals. The electronic structure of the needle phase is considered to be affected by the substrate although the crystallographic structure is similar to the bulk crystal of TTF-TCNQ.

In order for a service discipline to be used for guaranteed service networks at very high speed, its overall implementation must be scalable while it provides as wide a network schedulability region as possible. From this point of view, GPS-based service disciplines provide a narrow network schedulability region while EDF-based disciplines suffer from the implementation complexities of rate-controllers and admission control. Alternatively, although service disciplines based on service-curves can provide a wider network schedulability region than GPS-based and EDF-based disciplines, they may have even worse implementation complexities than EDF-based disciplines. In this paper, we propose to employ a service discipline based on our specific service-curves. We show that our service discipline has comparable implementation complexity to GPS-based disciplines while providing the same wide network schedulability region that EDF-based disciplines can provide. In fact, this service discipline is an SCED service discipline proposed in [14]. However, our specific service-curves provide the SCED service discipline with the same network schedulability region that EDF-based disciplines can provide, O(1) complexity for deadline calculation, and O(N) complexity for admission control where N is the number of sessions.

This letter treats computational complexity of bounded asymmetric choice (AC) net. AC net is a subclass of Petri net that properly includes the class of well-known extended free choice net. It is shown that satisfiability problem of Boolean expressions is polynomial time reducible to liveness problem of bounded AC nets. This implies that the problem is NP-hard.

Properly representation of the complexity of class structure will be useful in object oriented software developments. Although some class complexity metrics have been proposed, they have ignored directions of coupling relationships among methods and attributes, such as whether a method writes data onto an attribute or reads data from the attribute. In this paper, we use a directed graph model to represent such coupling relationships. Based on the directed graph model, we propose a metric of class structural complexity. The proposed metric satisfies necessary conditions of complexity metric suggested by Briand and others. The following fact is showed by experimental data of Java classes. While the proposed metric follows a conventional metric, the proposed metric can capture an aspect of class structural complexity which is lost by the conventional one.

We give an overview of the computational complexity of linear and mesh-connected cellular and iterative arrays with respect to well known models of sequential and parallel computation. We discuss one-way communication versus two-way communication, serial input versus parallel input, and space-efficient simulations. In particular, we look at the parallel complexity of cellular arrays in terms of the PRAM theory and its implications, e.g., to the parallel complexity of recurrence equations and loops. We also point out some important and fundamental open problems that remain unresolved. Next, we investigate the solvability of some reachability and safety problems concerning machines operating in parallel and cite some possible applications. Finally, we briefly discuss the complexity of the "commutativity analysis" technique that is used in the areas of parallel computing and parallelizing compilers.

In this paper, we discuss an IF image rejection system with variable bandwidth and center frequency. The system is consists of a pair of frequency mixers multiplied by the complex sinusoid and a complex analog filter. By employing the complex leapfrog structure using OTA-C configuration and the frequency transformation from the normalized LPF, the proposed system is capable of variable bandwidth and center frequency characteristics. SPICE simulations result more than 43 [dB] image rejection is achieved for 6 [kHz] and 12 [kHz] bandwidths at 50 [kHz] IF.

This paper investigates the accepting powers of one-way alternating and deterministic multi-counter automata operating in realtime. We partially solve the open problem posed in [4], and show that for each k1, there is a language accepted by a realtime one-way deterministic (k+3)-counter automaton, but not accepted by any realtime one-way alternating k-counter automaton.

A numerically efficient analysis method, combining closed-form Green's functions with the method of moments (MoM) of the mixed potential integral equation (MPIE) approach, is considered for the electromagnetic coupling problem through an aperture into a parallel plate waveguide (PPW), as a complementary problem to the microstrip patch structure problem, and then applied to the electromagnetic pulse (EMP) penetration problem. Some discussion on the advantages of the present method is also presented from the perspective of computational electromagnetics.