This paper investigates a relationship between accepting powers of two-way deterministic one-counter automata and one-pebble off-line deterministic Turing machines operating in space between loglog n and log n, and shows that they are incomparable.

Given a binary picture represented by a region quadtree, it is desirable to identify the amount of (rightward and downward) shifts of the foreground components such that it gives the minimum number of nodes of its quadtree. This problem is called "quadtree normalization. " For this problem, it is unknown whether there exists a linear time algorithm with respect to the size of given images (i. e. , the number of pixels). In this study, we investigate the "one-dimensional version" of the quadtree normalization problem, i. e. , given a binary string represented by a regional binary tree, the task is to identify the amount of (rightward) shift of the foreground components such that it gives the minimum number of nodes of its binary tree. We show that there exists a linear time algorithm for this version.

This paper introduces a probabilistic rebound automaton (pra), and investigates its accepting power and closure property. We show that (1) the class of languages recognized by pra's with error probability less than 1/2, PRA, is incomparable with the class of context-free languages, (2) there is a language accepted by a two-way nondeterministic one counter automaton, but not in PRA, and (3) there is a language accepted by a deterministic one-marker rebound automaton, but not in PRA. We also show that PRA is not closed under concatenation and Kleene + .

An optimized low-power optical memory access network is proposed to alleviate the cost of microring resonators (MRs) in kilocore systems, such as the pass-by loss and integration difficulty. Compared with traditional electronic bus interconnect, the proposed network reduces power consumption and latency by 80% to 89% and 21% to 24%. Moreover, the new network decreases the number of MRs by 90.6% without an increase in power consumption and latency when making a comparison with Optical Ring Network-on-Chip (ORNoC).

This paper first investigates a relationship between inkdot-depth and inkdot-size of inkdot two-way alternating Turing machines and pushdown automata with sublogarithmic space, and shows that there exists a language accepted by a strongly loglog n space-bounded alternating pushdown automaton with inkdot-depth 1, but not accepted by any weakly o (log n) space-bounded and d (n) inkdot-size bounded alternating Turing machine, for any function d (n) such that limn [d (n)log n/n1/2] = 0. In this paper, we also show that there exists an infinite space hierarchy among two-way alternating pushdown automata with sublogarithmic space.

This paper investigates some fundamental properties of alternating one-way (or two-way) pushdown automata (pda's) with sublogarithmic space. We first show that strongly (weakly) sublogarithmic space-bounded two-way alternating pda's are more powerful than one-way alternating pda's with the same space-bound. Then, we show that weakly sublogarithmic space-bounded two-way (one-way) alternating pda's are more powerful than two-way (one-way) nondeterministic pda's and alternating pda's with only universal states using the same space, and we also show that weakly sublogarithmic space-bounded one-way nondeterministic Turing machines are incomparable with one-way alternating Turing machines with only universal states using the same space. Furthermore, we investigate several fundamental closure properties, and show that the class of languages accepted by weakly sublogarithmic space-bounded one-way alternating pda's and the class of languages accepted by sublogarithmic space-bounded two-way deterministic pda's (nondeterministic pda's, alternating pda's with only universal states) are not closed under concatenation, Kleene closure, and length preserving homomorphism. Finally, we briefly investigate a relationship between 'strongly' and 'weakly'.

An approach to the enhancement of speech signals corrupted by additive colored noise is proposed and the system architecture to implement the proposed idea in real-time communication is introduced in this paper. A combination of a bandpass FIR filtering technique with wiener filtering is used to improve the SNR for speech signals. The average SNR improvement (between input and output SNR) is 22.48 dB. The additive noises are the sound from a turbo prop aircraft. The system, which shows excellent performance, is designed based on a 16 bits fixed point DSP (ADSP-2181) from Analog Devices. Experiment results demonstrate that the FIR filter leads to a significant gain in SNR, thus visibly improvement for the quality and the intelligibility of the speech.

This paper is concerned with a comparative study of the accepting powers of deterministic, Las Vegas, self-verifying nondeterminisic, and nondeterministic (simple) multihead finite automata. We show that (1) for each k 2, one-way deterministic k-head (resp., simple k-head) finite automata are less powerful than one-way Las Vegas k-head (resp., simple k-head) finite automata, (2) there is a language accepted by a one-way self-verifying nondeterministic simple 2-head finite automaton, but not accepted by any one-way deterministic simple multihead finite automaton, (3) there is a language accepted by a one-way nondeterministic 2-head (resp., simple 2-head) finite automaton, but not accepted by any one-way self-verifying nondeterministic multihead (resp., simple multihead) finite automaton, (4) for each k 1, two-way Las Vegas k-head (resp., simple k-head) finite automata have the same accepting powers as two-way self-verifying nondeterministic k-head (resp., simple k-head) finite automata, and (5) two-way Las Vegas simple 2-head finite automata are more powerful than two-way deterministic simple 2-head finite automata.

The hierarchies of multihead finite automata over a one-letter alphabet are investigated. Let SeH(k) [NSeH(k) ] denote the class of languages over a one-letter alphabet accepted by deterministic [nondeterministic] sensing two-way k-head finite automata. Let H (k)s[NH(k)s] denote the class of sets of square tapes over a one-letter alphabet accepted by two-dimensional four-way deterministic [nondeterministic] k-head finite automata. Let SeH(k)s[NSeH(k)s] denote the class of sets of square tapes over a one-letter alphabet accepted by two-dimensional four-way sensing deterministic [nondeterministic] k-head finite automata. This paper shows that SeH(k) SeH(k1) and NSeH(k) NSeH(k1) hold for all k3. It is also shown that H(k)s[NH(k)s] H(k1)s[NH (k1)s] and SeH (k)s[NSeH(k)s] SeH(k1)s[NSeH(k1)s] hold for all k1.

For each two positive integers r, s, let [1DCM(r)-Time(ns)] ([1NCM(r)-Time(ns)]) and [1DCM(r)-Space(ns)] ([1NCM(r)-Space(ns)]) be the classes of languages accepted in time ns and in space ns, respectively, by one-way deterministic (nondeterministic) r-counter machines. We show that for each X{D, N}, [1XCM(r)-Time(ns)][1XCM(r+1)-Time(ns)] and [1XCM(r)-Space(ns)][1XCM(r+1)-Space(ns)]. We also investigate the relationships between one-way multicounter machines and cooperating systems of one-way finite automata. In particular, it is shown that one-way (one-) counter machines and cooperating systems of two one-way finite automata are equivalent in accepting power.

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 introduces a new class of machines called multihead marker finite automata, and investigates how the number of markers affects its accepting power. Let HM{0}(i, j)(NHM{0}(i, j))denote the class of languages over a one-letter alphabet accepted by two-way deterministic (nondeterminstic) i-head finite automata with j markers. We show that HM{0} (i, j) HM{0}(i, j1) and NHM{0}(i, j) NHM{0}(i, j+1) for each i2, j0.

Effective capacity (EC) is an important performance metric for a time-varying wireless channel in order to evaluate the communication rate in the physical layer (PHL) while satisfying the statistical delay quality of service (QoS) requirement in data-link layer (DLL). This paper analyzes EC of amplify-and-forward wireless relay network with different relay selection (RS) protocols. First, through the analysis of the probability density function (PDF) of received signal-to-noise ratio (SNR), the exact expressions of EC for direct transmission (DT), random relay (RR), random relay with direct transmission (RR-WDT), best relay (BR) protocols are derived. Then a novel best relay with direct transmission (BR-WDT) protocol is proposed to maximize EC and an exact expression of EC for BR-WDT protocol is developed. Simulations demonstrate that the derived analytical results well match those of Monte-Carlo simulations. The proposed BR-WDT protocol can always achieve larger EC than other protocols while guaranteeing the delay QoS requirement. Moreover, the influence of distance between source and relay on EC is discussed, and optimal relay position for different RS protocols is estimated. Furthermore, EC of all protocols becomes smaller while delay QoS exponent becomes larger, and EC of BR-WDT becomes better while the number of relays becomes larger.

This paper introduces an alternating rebound Turing machine and investigates some fundamental properties of it. Let DRTM (NRTM,ARTM) denote a deterministic (nondeterministic and alternating) rebound Turing machine, and URTM denote an ARTM with only universal states. We first investigate a relationship between the accepting powers of rebound machines and ordinary machines, and show, for example, that (1) there exists a language accepted by a deterministic rebound automaton, but not accepted by any o(log n) space-bounded alternating Turing machine, (2) alternating rebound automata are equivalent to two-way alternating counter automata, and (3) deterministic rebound counter automata are more powerful than two-way deterministic counter automata. We next investigate a relationship among the accepting powers of DRTM's, NRTM's, URTM's and ARTM's, and show that there exists a language accepted by alternating rebound automata, but not accepted by any o(logn) space-bounded NRTM (URTM). Then we show that there exists an infinite space hierarchy for DRTM's (NRTM's, URTM's) with spaces below log n. Furthermore, we investigate a relationship between the strong and weak modes of space complexity, and finally show that the classes of languages accepted by o(logn) space-bounded DRTM's (NRTM's, URTM's) are not closed under concatenation and Kleene .

Since most of energy consumed by the telecommunication infrastructure is due to the Base Transceiver Station (BTS), switching off BTSs when traffic load is low has been recognized as an effective way of saving energy. In this letter, an energy saving scheme is proposed to minimize the number of active BTSs based on the space-time structure of traffic loads as determined by principal component analysis. Compared to existing methods, our approach models traffic loads more accurately, and has a much smaller input size. As it is implemented in an off-line manner, our scheme also avoids excessive communications and computing overheads. Simulation results show that the proposed method has a comparable performance in energy savings.

Radio Frequency Identification (RFID) plays a crucial role in IoT development. With the extensive use of RFID, the fact that a single RFID tag integrates multiple applications has become a mainstream. To facilitate users to use the multi-application RFID tag and revoke some applications in the tag securely and efficiently, a secure RFID application revocation scheme is proposed in this paper. In the scheme, each response for the challenge between tag and reader is different, and a group has the feature of many tags. Even if the group index number and corresponding group are revealed, a specific tag does not be precisely found and tracked. Users are anonymous completely. The scheme also allows users to set the validity period for an application or some applications. If the application contains the validity period and expires, the server will remove the validity period and revoke the application automatically in the tag when the RFID tag accesses server again. The proposed scheme cannot only be used in multi-application RFID tag but also be used in one-application RFID tag. Furthermore, compared with other existing schemes, the scheme provides a higher level of security and has an advantage of performance. Our scheme has the ability of mutual authentication and Anti-replay by adding a random number r2, and it is easy to against synchronization attack. Security proof is given in our paper and performance advantage are mainly reflected in the following points such as forward security, synchronization, storage complexity, computational complexity, etc. Finally, the proposed scheme can be used in multi-application RFID tag to promote the development of the IoT.

This paper shows that nondeterministic sensing semi-one-way simple k-head finite automata are more powerful than nondeterministic sensing one-way simple k-head finite automata for any k2, and sensing semi-one-way simple 2-head finite automata are more powerful than semi-one-way simple 2-head finite automata, which gives an affirmative answer and a partial solution to two open problems on sensing semi-one-way simple multi-head finite automata in Ref.[3].

For each positive integer r 1, a nondeterministic machine M is r path-bounded if for any input word x, there are r computation paths of M on x. This paper investigates the accepting powers of path-bounded one-way (simple) multihead nondeterministic finite automata. It is shown that for each k 2 and r 1, there is a language accepted by an (r + 1) path-bounded one-way nondeterministic k head finite automaton, but not accepted by any r path-bounded one-way nondeterministic k head finite automaton whether or not simple.

In this paper, we propose a robust registration method, named Bounded-Variables Least Median of Squares (BVLMS). It overcomes both the misassociations and the ill-conditioning due to the interactions between Bounded-Variables Least Squares (BVLS) and Least Median of Squares (LMS). Simulation results demonstrate the feasibility of this new registration method.

This paper investigates the accepting powers of multi-inkdot two-way alternating pushdown automata (Turing machines) with sublogarithmic space and constant leaf-size. For each k1, and each m0, let weak-ASPACEm [L(n),k] denote the class of languages accepted by simultaneously weakly L(n) space-bounded and k leaf-bounded m-inkdot two-way alternating Turing machines, and let strong-2APDAm[L(n),k] denote the class of languages accepted by simultaneously strongly L(n) space-bounded and k leaf-bounded m-inkdot two-way alternating pushdown automata. We show that(1) strong-2APDAm [log log n,k+1]weak-ASPACEm[o(log n),k]φfor each k1 and each m1, and(2) strong-2APDA(m+1) [log log n,k]weak-ASPACEm[o(log n),k]φfor each k1 and each m0.