Weighted context-free grammar (WCFG) is a quantitative extension of context-free grammar (CFG). It is known that unambiguous weighted automata (WA), finitely-ambiguous WA, polynomially-ambiguous WA and general WA over the tropical semiring have different expressive powers. We prove that there exists a similar ambiguity hierarchy of WCFG over the tropical semiring, using an extended Ogden's lemma. In addition, we prove that each of the classes of finitely-ambiguous, polynomially-ambiguous, and exponentially-ambiguous WCFG can be subdivided into a finer strict hierarchy. We further show that the hierarchy we proved is different from the known ambiguity hierarchy of unweighted CFG.

Register context-free grammars (RCFG), register pushdown automata (RPDA) and register tree automata (RTA) are extensions of their classical counterparts to handle data values in a restricted way. These extended models are paid attention as models of query languages for structured documents such as XML with data values. This paper investigates the computational complexity of the basic decision problems for the models. We show that the membership and emptiness problems for RCFG are EXPTIME-complete and also show the membership problem becomes PSPACE-complete and NP-complete for ε-rule free RCFG and growing RCFG, respectively while the emptiness problem remains EXPTIME-complete for these subclasses. The complexities of these problems for RPDA and RTA as well as their language expressive powers are also investigated.

Fifth-generation mobile communication systems (5G) require significantly higher system capacity than 4G in order to accommodate rapidly increasing mobile data traffic. Cell densification is considered to be one of the most effective ways to increase the system capacity. However, severe inter-cell interference degrades the system capacity due to the increase of the line-of-sight (LOS) environment between the transmission point (TP) and the user equipment (UE). We have proposed large-scale coordinated multi-user multiple-input multiple-output (LSC-MU-MIMO), which is the combination of MU-MIMO and joint transmission from all the TPs connected to a centralized baseband unit, to increase the system capacity in dense cell environments. In this paper, we introduce our recent results of indoor experimental trials with up to sixteen TPs coordination and show that the system capacity is almost proportional to the number of TPs with LSC-MU-MIMO. We also study how to locate TPs in order to exploit potential performance of LSC-MU-MIMO. Both simulation and experimental results show that the throughput is significantly improved by deploying TPs to make at least a channel of TP LOS with a high probability. Therefore TPs are preferable to be located that UEs have at least one TP with LOS condition.

In this paper, we make a summary report of our 5G R&D activities for “High Capacity Technologies with Ultra High-Density Multi-Band and Multi-Access Layered Cells”, funded by the Ministry of Internal Affairs and Communications (MIC) in Japan. This national project consists of three research subjects: “Ultra high-density distributed antenna systems”, “Optical access technologies accommodating highly densified small cells” and “Multi-RAT system technologies for multi-band and multi-access layered cells”. We describe the research and development result for each subject.

In fifth-generation (5G) mobile communication systems, it is necessary to significantly increase system capacity compared with 4G in order to support rapidly increasing mobile data traffic. The multi-user (MU) MIMO, which spatially multiplexes multiple user equipments (UE) in the same time and frequency resource, is the most promising technology. We have been studying large-scale coordinated MIMO, which uses zero forcing (ZF) precoding at the transmitter side, for a distributed antenna system. However, channel mismatch between channel estimation timing and data transmission timing drastically degrades throughput performance. In this paper, we propose a novel scheduler that preferentially schedules high speed UEs in small-delay slots from channel estimation timing by exploiting the diversity in terms of UE moving speed. The proposed scheduling is realized by the signal to interference plus noise ratio (SINR) prediction from channel variation between two most recent channel estimates and by inputting the predicted SINR into the proportional fairness (PF) scheduler. Computer simulations show that the proposed method significantly improves the mean UE throughput for high speed UEs while keeping almost the same mean UE throughput for low speed UEs.

Recently, we proposed large-scale coordinated multi-user MIMO (LSC-MU-MIMO), which combines joint transmission from multiple transmission points (TPs) and MU-MIMO, to increase the system capacity of ultra high-density distributed antenna systems. Applying hybrid beamforming (BF) to LSC-MU-MIMO is effective in further increasing the system capacity. However, since the previously proposed scheduler for LSC-MU-MIMO requires all downlink channel matrices between TP and user equipment (UE) to estimate the SINR of each UE, those of all analog BF candidates are necessary when applying hybrid BF, which results in a huge channel state information (CSI) feedback overhead. Besides, the conventional scheduler has high computational complexity since it requires inverse matrix calculation. In this paper, we propose a scheduler with low CSI feedback overhead and low computational complexity for LSC-MU-MIMO with hybrid BF. The proposed scheduler estimates the SINR of each UE using the received signal power of each analog BF without inverse matrix calculation. Simulation results show that the proposed scheduler achieves almost the same throughput performance as the scheduler using full-CSI feedback and inverse matrix calculation.

In order to tackle rapidly increasing traffic, distributed Massive MIMO (DM-MIMO) has been proposed for fifth-generation (5G) mobile communication systems. DM-MIMO coordinates lots of distributed transmission points (TPs) that are located in ultra-high density (UHD) and that use an appropriate number of antenna elements. Furthermore, DM-MIMO with UHD-TPs can create user-centric virtual cells corresponding to user mobility. To deploy TPs for DM-MIMO, some key parameters such as the number of the distributed TPs, the number of antenna elements for each TP, and proper distance between TPs should be determined. Conventional works have shown such key parameters for DM-MIMO with UHD-TPs by computer simulations. However, these parameters have not been evaluated in actual deployment environments. We measure low-SHF- band (4.5 GHz) radio propagation channel in indoor and outdoor experiments of DM-MIMO with UHD-TPs. Then, by exploiting the experimental results, the appropriate numbers of antenna elements based on maximum system throughput criterion are shown for 5G DM-MIMO by computer simulations.

In fifth-generation mobile communication systems (5G), it is necessary to significantly increase system capacity compared with 4G in order to accommodate rapidly increasing mobile data traffic. Cell densification has been considered an effective way to increase system capacity. However, severe intercell interference degrades the system capacity due to the increase of the line-of-sight environment between the transmission point (TP) and user equipment (UE). We propose large-scale coordinated multi-user multiple-input multiple-output (LSC-MU-MIMO), which combines joint transmission from all the TPs connected to a centralized baseband unit and MU-MIMO. We have investigated the downlink performance of LSC-MU-MIMO via both computer simulation and field experiments and showed that LSC-MU-MIMO can significantly reduce severe inter-TP interference and improve the system capacity of high-density small cells. In this paper, we introduce our recent field experiment results where reception antennas of UEs are mounted on a vehicle driving at speeds of 5 km/h to 40 km/h. We also compare distributed TP deployment with localized TP deployment when fixing the total number of transmission antennas.

A hybrid scheme of femtocell and distributed antenna system (DAS) is proposed that utilizes a subband dedicatedly assigned to each of multiple femtocells for system capacity gain and a subband shared for DAS simulcasting for cell-edge interference reduction. This paper presents a fundamental downlink performance evaluation and analysis of the in-building wireless system. Proportional fair (PF) scheduling is used for the user assignment, and the throughput performance is evaluated under various conditions. Simulation results show that the system can provide remarkable gains in cell-edge throughput while maintaining high average throughput, particularly in situations where high signal quality is available at the subband shared for the DAS and the system is of high upper bound of spectrum efficiency.

Non-orthogonal multiple access (NOMA), which uses superposition coding at the transmitter side and successive interference cancellation at the receiver side, is a promising new downlink multiple access scheme. The product of user average throughputs among all users within a cell can be maximized by optimal proportional fair (PF) scheduling, but this is computationally complex because it requires an exhaustive search for all possible user sets and optimal power allocation among users. In this work, we propose a novel method of selecting user sets for PF scheduling in downlink NOMA. Unlike conventional suboptimal methods, the proposed method is based on the mathematical characteristics of the PF metric. The proposed method can reduce the complexity when the maximum number of multiplexed users is three and four as well as two by judging whether a user set is worth multiplexing or not on the basis of a simple condition between the weakest two users within the set. Computer simulation showed that the proposed method can significantly reduce the average number of searched user sets while achieving almost the same total and cell-edge throughput as the optimal method.

An autonomous downlink interference control method for closed subscriber group (CSG) Long Term Evolution (LTE) femtocells is proposed. The proposed method integrates three interference control methods - power control, timing synchronization, and resource partitioning - by leveraging measurement results in various environments. The interferences on physical downlink data channel (PDSCH) and physical downlink control channel (PDCCH) are separated by using the timing synchronization between macrocells and femtocells, and these two interferences are handled independently. The interference on PDCCH is controlled by the transmission power control and that on PDSCH is controlled by the frequency resource partitioning. Moreover, it can deal with both inter-tier and intra-tier interference on the PDSCH and PDCCH. Computer simulations in accordance with 3GPP specifications are conducted in order to evaluate the effect of the proposed method compared with an existing transmission power control method. The results of the simulations show that the proposed method reduced PDCCH outage probability for both macro users and femto users. They also show that the proposed method can reduce downlink femtocell interference for macro users (victim UEs) without reducing femtocell throughput.

This paper reports estimates of TV white space (TVWS) availability in Japan that are based on the separation distances calculated using D/U-based and I/N-based rules. Calculating the TVWS availability with various TVWS-device parameters-antenna height, transmission power, protected area threshold, and adjacent channel leakage ratio (ACLR)-revealed the parameter dependence of the availability of TVWS channels. The effect of changing the protected area threshold is shown to differ between D/U-based and I/N-based rules: only in D/U-based rule do both separation distance and protected area decrease when the protected area threshold increases. We also show that the effect of the ACLR is smaller than that of the other parameters. Our estimates can be utilized as reference data showing how changes in TVWS availability depend on various TVWS device parameters.

This paper analyzes TV white space (TVWS) availability in Japan by estimating the amount and distribution of TVWSs across Japan and comparing them with those across the USA. While TVWS regulation is still under discussion in Japan, the expected availability is likely to be more encouraging than that in the USA. Japanese metropolitan areas tend to have more available channels than those in the USA. Including the Tokyo metropolitan area which is the most populated area in Japan, 84.3% of areas (66.7% of the population) may expect greater than 100-MHz TVWSs. The Tokyo metropolitan area is also relatively unaffected by restricted use of the adjacent channel or increase in separation distance.

In this paper, we are interested in blind and semi-blind identification of multiple-input multiple-output (MIMO) channel for orthogonal frequency division multiplexing (OFDM) systems. Using the sparsity property of wireless channel impulse response, we propose an iterative method which minimizes a cost function to result from the combination of blind or semi-blind criterion and the lp norm. This norm is considered as a good sparsity measure. The simulations show that the proposed method outperforms existing techniques in terms of estimation error and robustness to channel order overestimation.

A novel de-centralized dynamic inter-cell interference coordination (ICIC) method, which can change cell-edge bands dynamically by using an X2 interface and can be applied to current downlink long-term evolution (LTE) systems, is proposed. This dynamic ICIC method can autonomously optimize fractional frequency reuse (FFR) parameters and thus increase throughput. In addition, it works well even in the presence of control delays in time-variable environments. Static and dynamic system-level simulation (SLS) demonstrated that the throughput achieved by the proposed method is superior to that of conventional FFR methods.

We have been proposing multi-beam MIMO (MB- MIMO) as an Evolved UTRA downlink MIMO scheme for 3GPP long term evolution (LTE). MB-MIMO is a pre-coding MIMO scheme that uses a simple combination of multi-beam multiple-data-stream transmission and user equipment (UE)- based adaptive beam selection. The scheme benefits from its simple uplink feedback signalling, because MB-MIMO requires only a subset of the beam indices to be fed back. In this paper via computer simulation, we compare the performance of MB-MIMO and closed-loop MIMO that utilizes antenna selection only without beam-forming at the transmitter. In this comparison we consider the correlation between antenna elements in a temporally and spatially dispersed multi-path channel. Simulation results revealed that MB-MIMO has superior performance due to its beam-forming gain, even with limited feedback signalling. In this paper, we also introduce the MB-MIMO scheme using the cross-polarized (X-pol) antenna arrays and demonstrate its throughput performance comparing to the MB-MIMO using the 4-antenna linear array.

We have been proposing multi-beam MIMO (MB-MIMO) as an evolved UTRA downlink MIMO scheme for 3GPP long term evolution (LTE). MB-MIMO is a pre-coding MIMO scheme that uses a simple combination of multi-beam multiple-data-stream transmission and user equipment (UE)-based adaptive beam selection. The scheme benefits from its simple uplink feedback signaling, because MB-MIMO requires only a subset of the beam (codebook) indices to be fed back. However, a hardware calibrator (HW-CAL), which increases the complexity of RF components at a transmitter, should be installed in order to achieve a high beam-forming gain with a small codebook size. In this paper, we propose a novel codebook design for MB-MIMO, which realizes a superior performance without any HW-CAL with a small increase of the codebook size and the feedback signaling. We performed a computer simulation to evaluate the throughput performance of the proposed scheme, considering the phase variation between antenna elements in a spatially distributed multi-path fading channel model.

We propose a new architecture for trust management in ubiquitous environments that deals with RBAC policy, digital signatures, and user presence in a uniform framework. The proposed architecture includes inferences about user presence from incomplete sensor signals based on the hidden Markov model. We implemented a prototype system for a connection service in an office computer network with an RFID tag sensor system.Experimental results show that the proposed architecture is effective in providing both useful and secure services in a ubiquitous environment.

This paper proposes likelihood function generation of complexity-reduced maximum likelihood detection with QR decomposition and M-algorithm (QRM-MLD) suitable for soft-decision turbo decoding and investigates the throughput performance using QRM-MLD with the proposed likelihood function in multipath Rayleigh fading channels for orthogonal frequency and code division multiplexing (OFCDM) with multiple-input multiple-output (MIMO) multiplexing. Simulation results show that by using the proposed likelihood function generation scheme for soft-decision turbo decoding following QRM-MLD in 4-by-4 MIMO multiplexing, the required average received signal energy per bit-to-noise power spectrum density ratio (E/sub b//N/sub o/) at the average block error rate (BLER) of 10/sup -2/ at a 1-Gbps data rate is significantly reduced compared to that using hard-decision decoding in OFCDM access with 16 QAM modulation, the coding rate of 8/9, and 8-code multiplexing with a spreading factor of 8 assuming a 100-MHz bandwidth. Furthermore, we show that by employing QRM-MLD associated with soft-decision turbo decoding for 4-by-4 MIMO multiplexing, the throughput values of 500 Mbps and 1 Gbps are achieved at the average received E/sub b//N/sub o/ of approximately 4.5 and 9.3 dB by QPSK with the coding rate of R = 8/9 and 16 QAM with R = 8/9, respectively, for OFCDM access assuming a 100-MHz bandwidth in a twelve-path Rayleigh fading channel.

This paper discusses temporal reasoning with respect to constraints on two concurrent sequences of events. If two given sequences of events can be mapped into one sequence that satisfies a given constraint, then the constraint is said to be consistent. First, we mention that the consistency of such constraints is NP-complete. Then we introduce the notion of graph representations of constraints. If a graph representation of a given constraint c can be constructed in polynomial time, then the consistency of c is decidable in polynomial time. However, it is shown that the graph representability of a given c is coNP-complete. Next, we propose a subclass CDC$^{\neq} of constraints such that for each constraint c in CDC$^{\neq}$, a graph representation of c can be constructed in polynomial time. The expressive power of CDC$^{\neq}$ is incomparable to any other subclasses of constraints for which the consistency problem is known to be tractable.

Stack inspection is a key technology for runtime access control of programs in a network environment. In this paper, a verification problem to decide whether a given program with stack inspection satisfies a given security property is discussed. First, the computational complexity of the problem is investigated. Since the result implies the problem is computationally intractable in general, we introduce a practically important subclass of programs which exactly model programs containing check Permission of Java development kit 1.2. We show that the problem for this subclass is solvable in linear time in the size of a program.

The choice of the spatial frequency reuse and the channel plan in multi-cellular wireless systems plays an important role in effectively combating co-channel interference (CCI) and enhancing system capacity. In this paper, we compare the performance of four different interleaved channel and polarization assignment combinations of three spatial frequency reuse schemes in quad-sector cell architecture. The schemes are further compared with the traditional tri-sector cell cluster size N=3. For the tri-sector cell, a 90 degree sector antenna is proposed while a 60 degree one is chosen for the quad-sector cell. The relative beamwidths, from off-the-shelf antenna radiation patterns, are tradeoffs between minimizing CCI and maximizing the sector coverage at the sector boundaries. We demonstrate that (a) the quad-sector architecture has a higher capacity for 90% area coverage than the tri-sector cell. (b) the combination of interleaved channel assignment (ICA) and interleaved polarization assignment (IPA) offered the most enhanced capacity. For a reuse cluster size N=1, capacity enhancement with combined ICA and IPA measured 45% better than without using any assignment. For N=2, this measured 85% while for N=3, it measured 63%. These improvements pertain to cross-polarization discrimination (XPD) of 6 dB. (c) IPA and rotating channel assignment (RCA) in the tri-sector reuse cluster of N=3 are not effective tools for enhancing capacity.

Co-channel interference (CCI) from other reuse cells restricts the channel capacity of cellular communication systems. In fixed wireless access systems, the deployment of directional antennas at the customer premises equipment (CPE) that point towards their base stations suggest a direct and easy method to combat CCI and enhance capacity in a line-of-sight (LOS) propagation scenario. However, in a non-line-of-sight (NLOS) scenario, the effect of using a directional antenna at the CPE depends on the multipath angle of arrival (AOA) distribution of the propagating channel. In this paper, we demonstrate and compare the downlink performance of the directional antenna at the CPE under different AOA conditions. Two multipath channel models are assumed: circular and elliptical scattering models. We also calculate the performance of the adaptive array antenna deployed at the CPE and calculate its beamwidth effect. The capacity performance of the adaptive array antenna is compared with that of the single directional antenna.

Java development kit 1.2 provides a runtime access control mechanism which inspects a control stack to examine whether the program has appropriate access permissions. Guaranteeing that each execution of a program with stack inspection satisfies required security properties is desirable. Jensen et al. introduced a verification problem of deciding for a given program P and a given security property written in a temporal logic formula, whether every reachable state of P satisfies . They showed that the problem is decidable for the class of programs which do not contain mutual recursion. In this paper, we show that the set of state sequences of a program is always an indexed language and consequently the verification problem is decidable. Our result is stronger than Jensen's in that a security property can be specified by a regular language, whose expressive power is stronger than temporal logic, and in that a program can contain mutual recursion.

In this paper, we propose a method to estimate geometrical relations among grasping points of robots handling an unknown single object in coordination. The method utilizes the velocity relation between a grasping point of a robot and that of the reference robot. The relation among the grasping points of robots is estimated recursively by the extended Kalman filter. Simulation and experimental results using two mobile robots illustrate the effectiveness of the proposed method.

We propose a method to calibrate the orientation error between the leader coordinate system and each of the follower for the leader-follower type decentralized coordinated motion control system of multiple robots using motion estimators. This method uses the relation between the velocity vector of the manipulated object in the leader coordinate system and the velocity vector in each of the follower coordinate system. The orientation error is estimated recursively by using the extended Kalman filter. Experimental results illustrate the effectiveness of the proposed method.

We propose a decentralized control algorithm of multiple manipulators handling a single object in coordination. The proposed algorithm is a leader-follower type; the motion command of the object is given to one of the manipulators, referred to as a leader, and the other manipulators, referred to as followers, estimate the motion of the leader by themselves through the motion of the object and handle the object based on the estimated motion. Different from the conventional leader-follower type of control algorithms, each manipulator is impedence-controlled and has equal dynamic characteristics. The stability of the resultant system with the decentralized control algorithm is also guaranteed. The proposed control algorithm is experimentally implemented in two industrial manipulators and the experimental results illustrate the validity of the system.

A number of grammatical formalisms have been proposed to describe the syntax of natural languages, and the universal recognition problems for some of those classes of grammars have been studied. A universal recognition problem for a class Q of grammars is the one to decide, taking a grammar G ∈ G and a string ui as an input, whether G can generate w or not. In this paper, the computational complexities of the universal recognition problems for parallel multiple context‐free grammars, multiple context‐free grammars, and their subclasses are discussed.

A number of grammatical formalisms were introduced to define the syntax of natural languages. Among them are parallel multiple context-free grammars (pmcfg's) and lexical-functional grammars (lfg's). Pmcfg's and their subclass called multiple context-free grammars (mcfg's) are natural extensions of cfg's, and pmcfg's are known to be recognizable in polynomial time. Some subclasses of lfg's have been proposed, but they were shown to generate an NP-complete language. Finite state translation systems (fts') were introduced as a computational model of transformational grammars. In this paper, three subclasses of lfg's called nc-lfg's, dc-lfg's and fc-lfg's are introduced and the generative capacities of the above mentioned grammatical formalisms are investigated. First, we show that the generative capacity of fts' is equal to that of nc-lfg's. As relations among subclasses of those formalisms, it is shown that the generative capacities of deterministic fts', dc-lfg's, and pmcfg's are equal to each other, and the generative capacity of fc-lfg's is equal to that of mcfg's. It is also shown that at least one NP-complete language is generated by fts'. Consequently, deterministic fts', dc-lfg's and fc-lfg's can be recognized in polynomial time. However, fts' (and nc-lfg's) cannot, if P ≠ NP.

A method of translating natural language specifications of communication protocols into algebraic specifications is presented. Such a natural language specification specifies action sequences performed by the protocol machine (program). Usually, a sentence implicitly specifies the state of the protocol machine in which the described actions should be performed. A method of analyzing the implicitly specified states of the protocol machine is proposed, taking the OSI session protocol specification as an example. The method uses the following properties: (a) syntactic properties of a natural language; (b) syntactic properties introduced by the target algebraic specifications, e.g., subtype relations; and (c) properties of a data type, e.g., properties of timer. The results of applying this method to the main part of the OSI session protocol specification is shown.>

We propose a method for detecting the generation of garbage cells by analyzing a source text written in a functional programming language which uses ordinary linked lists to implement list-type values. For a subexpression such as F ( G ( . . . )) in a program where the function values of F and G are of list type, if a cell c is created during the computation of G and if c does not appear in a list-type value of F , then c becomes a garbage cell at the end of the computation of F . We discuss this problem on the basis of formal languages derived from the functional program text and show some sufficient conditions that predict the generation of garbage cells. Also, we give an efficient algorithm to detect at compile time the generation of garbage cells which are linearly linked. We have implemented these algorithms in an experimental LISP system. By executing several sample programs on the system, we conclude that our method is effective in detecting the generation of garbage cells.