This paper investigates some fundamental properties of 2-way alternating multi-counter automata (2amca's) with only existential (universal) states which have sublinear space and 1 inkdot. It is shown that for any function s(n) log n such that log s(n)=o(log n), s(n) space-bounded 1-inkdot 2amca's with only existential states are incomparable with the ones with only universal states, and the ones with only existential (universal) states are not closed under complementation.

A new phasor model of neural networks is proposed in which the state of each neuron possibly takes the value at the origin as well as on the unit circle. A stability property of equilibria is studied in association with the energy landscape. It is shown that a simple condition guarantees an equilibrium to be asymptotically stable.

The mathematical theory of bicomplex electromagnetic waves in two-dimensional scattering and diffraction problems is developed. The Vekua's integral expression for the two-dimensional fields valid only in the closed source-free region is generalized into the radiating field. The boundary-value problems for scattering and diffraction are formulated in the bicomplex space. The complex function of a single variable, which obeys the Cauchy-Riemann relations and thus expresses low-frequency aspects of the near field at a wedge of the scatterer, is connected with the radiating field by an integral operator having a suitable kernel. The behaviors of this complex function in the whole space are discussed together with those of the far-zone field or the amplitude of angular spectrum. The Hilbert's factorization scheme is used to find out a linear transformation from the far-zone field to the bicomplex-valued function of a single variable. This transformation is shown to be unique. The new integral expression for the field scattered by a thin metallic strip is also obtained.

An analytical solution of the London equation for the weakly coupled grain model of high Tc superconducting thin films has been obtained in the case of finite thickness by taking full account of anisotropic conductivities. Using the solution, we provide general expressions for the transmission-line parameters of high Tc superconducting transmission lines. Dependences of the inductance and resistance on the grain size, coupling strength and film thickness have been numerically evaluated and discussed.

We proposed a soft-decision decoding algorithm for cyclic codes based on energy minimization principle. This letter presents the algorithm which improves decoding performance and decoding complexity of the previous method by giving more initial positions and introducing a new criterion for terminating the decoding procedure. Computer simulation results show that both the decoded block error rate and the decoding complexity decrease by this method more than by the previous method.

We analyze the extended stochastic complexity (ESC) which has been proposed by K. Yamanishi. The ESC can be applied to learning algorithms for on-line prediction and batch-learning settings. Yamanishi derived the upper bound of ESC satisfying uniformly for all data sequences and that of the asymptotic expectation of ESC. However, Yamanishi concentrates mainly on the worst case performance and the lower bound has not been derived. In this paper, we show some interesting properties of ESC which are similar to Bayesian statistics: the Bayes rule and the asymptotic normality. We then derive the asymptotic formula of ESC in the meaning of almost sure and mean convergence within an error of o(1) using these properties.

Recent developments in computer technology allow us to analyze all the data in a huge database. Data mining is to analyze all the data in such a database and to obtain useful information for database users. One of the well-studied problems in data mining is the search for meaningful association rules in a market basket database which contains massive amounts of transactions. One way to find meaningful association rules is to find all the large itemsets first, and then to find meaningful association rules from the large itemsets. Although a number of algorithms for computing all the large itemsets have been proposed, the computational complexity of them is scarcely disscussed. In this paper, we show that it is NP-complete to decide whether there exists a large itemset that has a given cardinality. Also, we propose subclasses of databases in which all the meaningful association rules can be computed in time polynomial of the size of a database.

Two classes of nonlinear feedforward logic (NLFFL) pseudonoise (PN) code generators based on the use of AND and majority logic (ML) gates are compared. Cross-correlation and code-division multiple-access (CDMA) properties of properly designed NLFFL sequences are found to be comparable with the properties of well-known linear PN codes. It is determined that code design employing ML gates with an odd number of inputs is easier compared with designing with AND gates. This is especially true when the degree of nonlinearity is large, since the nonbalance problem, e. g. , at the output of an AND gate, can be avoided. ML type sequences are less vulnerable to correlation attack and jamming by the m-sequence of an NLFFL generator

In this paper, comparison of various orthogonal transforms in Wiener filtering is discussed. The study involves the family of discrete orthogonal transforms called Complex Hadamard Transform, which has been recently introduced by the same authors. Basic definitions, properties and transformation kernel of Complex Hadamard Transform are also shown.

We address, in this paper, the main features of hybrid modes propagating in a rectangular waveguide partially filled with pseudochiral Ω-slabs. For the particular case of a uniaxial Ω-slab, we show that LSE and LSM hybrid modes can propagate in this inhomogeneously filled rectangular waveguide. The influence of the Ω-parameter, which characterizes the magnetoelectric tensors of the bianisotropic slab, on LSM modes is analyzed--namely an increase in the bandwidth for monomodal operation is reported. In addition, a field displacement effect and a variable phase shift proportional to the change of the Ω-parameter are attained. Finally, it is shown that the propagation characteristics are independent of the direction of propagation and so, unlike the case of magnetically biased ferrite loading, reciprocal devices can be achieved.

This paper proposes a new distortion analysis method for frequency-dependent FET amplifiers, which uses a novel Frequency-Dependent Complex Power Series (FDCPS) model. This model consists of a frequency-independent nonlinear amplifier represented by an odd-order complex power series and frequency-dependent input and output filters. The in-band frequency characteristics of the saturation region are represented by the frequency-dependent output filter, while the in-band frequency characteristics of the linear region are represented by the frequency-dependent input and output filters. In this method, the time-domain analysis is carried out to calculate the frequency-independent nonlinear amplifier characteristics, and the frequency-domain analysis is applied to calculate the frequency-dependent input and output filter characteristics. The third-order intermodulation (IM3) calculated by this method for a GaAs MESFET amplifier is in good agreement with the numerical results obtained by the Harmonic Balance (HB) method. Moreover, the IM3 calculated by this method also agrees well with the measured data for an L-band 3-stage GaAs MESFET amplifier. It is shown that this method is effective for calculating frequency-dependent distortion of a nonlinear amplifier with broadband modulation signals.

We show that the permanent of an m n rectangular matrix can be computed with O(n 2m 3m) multiplications and additions. Asymptotically, this is better than straightforward extensions of the best known algorithms for the permanent of a square matrix when m/n log3 2 and n .

Digital Signal Processors with complex arithmetic capability (DSP-C) are useful for various applications. In this paper, we propose a method for the effective implementation of specific circuits with real coefficients on DSP-C. DSP-C has special hardware such as a complex multiplier so that a complex calculation can be performed with only one instruction. First, we show that nodes with two real coefficient input branches can be implemented by complex multiplications. We apply this implementation to 2D circuits and transversal circuits with real coefficients. Next, we introduce a new computational mode (Advanced mode) and a new multiplier into PSI, a kind of DSP-C which has been proposed already, in order to process the circuits effectively. The effectiveness of the proposed method is shown by simulation in the last part.

The time-memory trade-off cryptanalysis for block ciphers with a search space of size 2N (N: key length) cannot achieve a success probability excceding 63%. This is caused by some unavoidable overlapping of keys in the space. For elavating the success probability of finding the correct key, a larger search space is necessary. That is, the increase of time complexity for precomputation would be inevitable. This paper theoretically shows, however, no further price is required for the size of look-up tables for the number of encryptions for searching for the key that matches the given ciphertext - plaintext pairs. This theory is confirmed by some empilical results.

In 1992 Burmester studied how to adapt the Guillou-Quisquater identification scheme to a proven zero-knowledge proof without significantly increasing the communication complexity and computational overhead. He proposed an almost constant round version of Guillou-Quisquater. Di Crescenzo and Persiano presented a 4-move constant round zero-knowledge interactive proof of membership for the corresponding language. A straightforward adaptation of the ideas of Bellare-Micali-Ostrovsky will also give a constant round protocol. However, these protocols significantly increase the communication and computational complexity of the scheme. In this paper we present constant round variants of the protocols of Guillou-Quisquater and Schnorr with the same (order-wise) communication and computational complexity as the original schemes. Note that in our schemes the probability that a dishonest prover will fool a honest verifier may be exponentially small, while it can only be one over a superpolynomial in Burmester's scheme. Our protocols are perfect zero-knowledge under no cryptographic assumptions.

Informally, private information retrieval for k 1 databases (k-PIR) is an interactive scheme that enables a user to make access to (separated) k replicated copies of a database and privately retrieve any single bit out of the n bits of data stored in the database. In this model, "privacy" implies that the user retrieves the bit he is interested in but releases to each database nothing about which bit he really tries to get. Chor et. al. proposed 2-PIR with communication complexity 12 n1/32 that is based on the covering codes. Then Ambainis recursively extended the scheme by Chor et. al. and showed that for each k 2, there exists k-PIR with communication complexity at most ckn1/(2k-1) some constant ck > 0. In this paper, we relax the condition for the covering codes and present time-efficient 2-PIR with communication complexity 12 n1/3. In addition, we generally formulate the recursive scheme by Ambainis and show that for each k 4, there exists k-PIR with communication complexity at most ck' n1/(2k-1) for some constant ck' << ck.

In this paper, we represent a class structure using directed graph in which each node corresponds to each member of the class. To quantify the dependence relationship among members, we define weighted closure. Using this quantified relationship and effort equation proposed by M. H. Halstead, we propose a metric for class structural complexity.

Image classification is an important task in document image analysis and understanding, page segmentation-based document image compression, and image retrieval. In this paper, we present a new approach for distinguishing textual images from pictorial images using the Kolmogorov Complexity (KC) measure with randomly extracted blocks. In this approach, a number of blocks are extracted randomly from a binarized image and each block image is converted into a one-dimensional binary sequence using either horizontal or vertical scanning. The complexities of these blocks are then computed and the mean value and standard deviation of the block complexities are used to classify the image into textual or pictorial image based on two simple fuzzy rules. Experimental results on different textual and pictorial images show that the KC measure with randomly extracted blocks can efficiently classified 29 out 30 images. The performance of our approach, where an explicit training process is not needed, is comparable favorably to that of a neural network-based approach.

The maximum order complexity (MOC) of a sequence is a very natural generalization of the well-known linear complexity (LC) by allowing nonlinear feedback functions for the feedback shift register which generates a given sequence. It is expected that MOC is effective to reduce such an instability of LC as an extreme increase caused by the minimum changes of a periodic sequence, i. e. , one-symbol substitution, one-symbol insertion or one-symbol deletion per each period. In this paper we will give the bounds (lower and upper bounds) of MOC for the minimum changes of an m-sequence over GF(q) with period qn-1, which shows that MOC is much more natural than LC as a measure for the randomness of sequences in this case.

The complex conductivities of high Tc superconducting YBa2Cu3Ox thin films have been studied using the coplanar waveguide resonator technique. In order to evaluate the magnetic penetration depth precisely, we measured the temperature dependence of the resonant frequency and compared it with the numerical results self-consistently. The observed temperature dependence of the complex conductivities is shown to be able to distinguish the effects of the weaklink from the intrinsic property of the grain of an epitaxial thin film and demonstrate the weakly coupled grain model of YBa2Cu3Ox thin films.