We propose a new inferring programmers' intention system COSMO based on a classification of assignment statements. COSMO is a subsystem of our intelligent programming environment for programming education. The programming environment consists of a program understanding system designed for novice programmers and a novice program evaluation support system designed for teachers, both of which use the technique of the program slicing. Usually, the method of program slicing requires selection of slicing criteria. However, automatic selection of effective slicing criteria is difficult. Here we propose a new inferring programmers' intention system COSMO with automatic selection of effective slicing criteria. In our system, the slicing criteria are inferred using the context structure model of programs. Programs are regarded as natural language texts in the model and analyzed using a similar thinking in context structure analyses of natural language texts. The model is based on a classification of assignment statements using dependence analysis of programs. Furthermore, COSMO obtains networks with information on top-down decomposition of problems as a result of inferring programmers' intention. Therefore, COSMO is useful for understanding programs without presupposed knowledge.
Hiroyuki YAMAZAKI Keishi SAKANUSHI Shigetoshi NAKATAKE Yoji KAJITANI
The three dimensional (3D) packing problem is to arrange given rectangular boxes in a rectangular box of the minimum volume without overlapping each other. As an approach, this paper introduces the system of three sequences of the box labels, the sequence-triple, to encode the topology of the 3D-packing. The topology is the system of relative relations in pairs of boxes such as right-of, above, front-of, etc. It will be proved that the sequence-triple represents the topology of the tractable 3D-packings which is a 3D-packing such that there is an order of the boxes along which all the boxes are extracted one by one in a certain fixed direction without disturbing other remaining boxes. The idea is extended to the system of five ordered sequences, the sequence-quintuple. A decoding rule is given by which any 3D-packing is represented. These coding systems are applied to design heuristic algorithms by simulated annealing which search the codes for better 3D-packings. Experimental results were very convincing its usefulness as automated packing algorithms.
Hideki TODE Hiroki YAMAUCHI Hiromasa IKEDA
An efficient scheme for establishing the multicast-path on ATM network is to configure the tree-shaped path via several intermediate copy nodes. This scheme needs the multicast routing control. Thus, restricting the number of copy nodes was proposed since it make this control fast and simple. However, if restricted number of copy nodes is fixed in the network design, multicast traffic will concentrate around copy nodes, and as a result, the possibility of occurring congestion will be higher. In our research, we permit restricted number of nodes as intermediate nodes which branch the tree-shaped path at routing, and name this permission "copy-token. " Namely, the node which has "copy-token" is defined as the copy node. Our research purpose is to distribute the multicast traffic by adaptively allocating "copy-token" to nodes which satisfy the conditions of both the priority for multicasting such as lower offered load and the geographical distribution at the same time. Finally, we evaluate the performance of our proposed routing scheme on the blocking probability through computer simulations.
Cheng-Chung HSU Wu-Shiung FENG
In this letter, a novel built-in self-test (BIST) structure based on operational transconductance amplifiers and grounded capacitors (OTA-Cs) for the fault diagnosis of analog circuits is proposed. The proposed analog BIST structure, namely ABIST, can be used to increase the number of test points, sampling and controlling of all test points with voltage data, and making less time for test signal observable. Experimental measurements have been made to verify that the proposed ABIST structure is effective.
This paper focuses on introducing a highly efficient data structure that effectively captures the multipath phenomenon needed for accurate propagation modeling and fast propagation prediction. We propose a new object representation procedure called circular representation (CR) of microwave masking objects such as buildings, to improve over the conventional vector representation (VR) form in fast ray tracing. The proposed CR encapsulates a building with a circle represented by a center point and radius. In this configuration, the CR essentially functions as the basic building block for higher geometric structures, enhancing the efficiency more than when VR is used alone. Only one CR is needed to represent one building while several wall vectors are required in VR. As a result, a significant computational reduction can be achieved in ray tracing by the proposed method. Our aim is to show CR as a solution to achieving efficiency in data structuring for effective propagation prediction modeling. We show that the computational load is reduced by the proposed method. Further reduction is shown attainable using the hierarchical structure of CR in a deterministic propagation model, undergoing ray tracing. The simulation results indicate that the proposed CR scheme reduces the computational load proportionally to the number of potential scattering objects while its hierarchical structure achieves about 50% of computational load reduction in the hierarchical octree structure.
A min-wise independent permutation family is known to be an efficient tool to estimate similarity of documents. Toward good understanding of min-wise independence, we present a characterization of exactly min-wise independent permutation families by size uniformity, which represents certain symmetry of the string representation of a family. Also, we present a general construction strategy which produce any exactly min-wise independent permutation family using this characterization.
Takaaki MIZUKI Zhi-Bo SUI Hiroki SHIZUYA Takao NISHIZEKI
Designing a protocol to exchange a secret key is one of the most fundamental subjects in cryptography. Using a random deal of cards, pairs of card players (agents) can share secret keys that are information-theoretically secure against an eavesdropper. A key set protocol, which uses a random deal of cards, can perform an Eulerian secret key exchange, in which the pairs of players sharing secret keys form an Eulerian circuit passing through all players. Along the Eulerian circuit any designated player can send a message to the rest of players and the message can be finally sent back to the sender. Checking the returned message with the original one, the sender can know whether the message circulation has not been influenced by a possible single transmission error or false alteration. It has been known that any Eulerian circuit formed by the protocol has length at most 3/2k, where k is the number of players. Note that the length corresponds to the time required to send the message to all players and acknowledge the secure receipt. In this paper, we show that the average length of Eulerian circuits is approximately k+ln k.
Kyung-Ah AHN Hoon CHOI Won-Ok KIM
We present an architecture of a VOD system employing proxy servers. The proposed VOD system provides efficient and reliable VOD services and solves the problems caused by traditional VOD systems of centralized, hierarchical or distributed architecture. The proxy servers are placed between video servers and user systems. The proxy server is a small size video server that has not only caching function but also intelligence such as VCR-like video stream control or navigation of other proxy/video servers to search for a selected video program. Using a VOD system of the proposed architecture, the VOD services can be provided to more users because it reduces the workload of video servers and network traffic. We provide the performance model of the system. Service availability is also analyzed. The proposed architecture shows better performance and availability than the traditional VOD architectures.
In-Ho LIN Bih-Hwang LEE Chwan-Chia WU
This paper presents an object-oriented model to handle the temporal relationship for all of the multimedia objects at the presentation platform. Synchronization of the composite media objects is achieved by ensuring that all objects presented in the upcoming "manageable" period must be ready for execution. To this end, the nature of overlays is first investigated for various types of objects. Critical overlaps which are crucial in synchronization are also defined. The objective of synchronization is to ensure that the media objects can be initiated precisely at the critical point of the corresponding critical overlap. The concept of manageable presentation interval is introduced and the irreducible media group is defined. The resource scheduling of each presentation group for media object pre-fetch time versus buffer occupancy is also examined. Accordingly, a new model called group cascade object composition Petri-net (GCOCPN) is proposed and an algorithm to implement this temporal synchronization scheme is presented.
A reallocation problem is defined as determining whether blocks can be moved from their current boxes to their destination boxes in the number of moves less than or equal to a given positive integer. This problem is defined simply and has many practical applications. We previously proved the following results: The reallocation problem such that the block volume is restricted to one volume unit for all blocks can be solved in linear time. But the reallocation problem such that the block volume is not restricted is NP-complete, even if no blocks have bypass boxes. But the computational complexity of the reallocation problems such that the range of the block volume is restricted has not yet been known. We prove that the reallocation problem is NP-complete even if the block volume is restricted to one or two volume units for all blocks and no blocks have bypass boxes. Furthermore, we prove that the reallocation problem is NP-complete, even if there are only two blocks such that each block has the volume units of fixed positive integer greater or equal than two, the volume of the other blocks is restricted to one volume unit, and no blocks have bypass boxes. Next, we consider such a block that must stays in a same box both in the initial state and in the final state but can be moved to another box for making room for other blocks. We prove that the reallocation problem such that an instance has such blocks is also NP-complete even if the block volume is restricted to one volume unit for all blocks.
Kenichi ONO Masaaki KATAYAMA Takaya YAMAZATO Akira OGAWA
In this paper, we analytically study the effects of overlap and overlay structure on the quality of service (QoS) of Low Earth-Orbital Satellite (LEOS) communication systems. We consider two-layered overlay of cells and intentional overlap of neighboring small cells. In order to measure the QoS, the probabilities of rejection of a newly arrived call (blocking) and forced termination due to failure of a handover (call dropping) are derived. In addition to these measures, the largest traffic intensity which guarantees the required blocking and dropping probabilities is also used.
Kazunari IRIE Yoshiyuki MONMA Norihisa OHTA
We have already proposed a regional PC communication network system that provides a LAN environment and group communication services to the customers. A Low-end Card (LECard) is set up in the subscriber's household and provides the popular Ethernet interface (10Base-T). A multiplex-port brouter (MBR) was developed to accommodate a lot of customers in a cost-effective manner. Ethernet packets are transferred through each subscriber channel between the LECard and the MBR using the HDLC protocol. The LECard and the MBR are controlled by the group management server (GMS) to realize the group communication system. The performance of an experimental system in ordinary use must be evaluated before bringing the system into practical use. However, it is difficult to prepare a number of PCs and to use them at the same time to evaluate the performance degradation seen in multiple-access. This paper presents a newly developed multiple-access simulator for evaluating MBR performance. The simulator connects to the MBR under test through a multiplexed signal interface. It simulates the conditions in which many LECards and PCs are connected to an MBR and they access the network at the same time. The basic function of the LECard, passing the MAC addresses of subordinate PCs to GMS, and the packet generating function of the PCs are implemented in the simulator. Ethernet packets are transmitted to all ports of the multiplexed interface. MBR throughput in the experimental system was evaluated by transmitting Ethernet packets from/to the simulator. The results show that the MBR package has a processing speed of about 4000 PPS. They also show that the degradation in user port performance is slight up to approximately 20% of the active ratio, i. e. 20% of the users access at the same time.
Sureerat SAEEIAB Motoshi SAEKI
Formal description techniques (FDTs) such as VDM, Z, LOTOS, etc are powerful to develop safety-critical systems since they have strict semantics and mathematical reasoning basis. However, they have no methods or guides how to construct specifications unlike specification and design methods such as Object-Oriented Modeling and Technique (OMT), and that makes it difficult for practitioners to compose formal specifications. One of the solutions is to connect formal description techniques with some existing methods. This paper discusses a technique how to integrate FDTs with specification and design methods such as OMT so that we can have new methods to support writing formal specifications. The integration mechanism is based on transformation rules of specification documents produced following methods into the descriptions written in formal description techniques. The transformation rules specify the correspondences on two meta models; of methods and of formal description techniques, and are described as graph rewriting rules. As an example, we pick up OMT as a method and LOTOS as a FDT and define the transformation rule on their meta models.
David AVIS Antoine DEZA Shmuel ONN
The classical game of peg solitaire has uncertain origins, but was certainly popular by the time of Louis XIV, and was described by Leibniz in 1710. One of the classical problems concerning peg solitaire is the feasibility issue. An early tool used to show the infeasibility of various peg games is the rule-of-three [Suremain de Missery 1841]. In the 1960s the description of the solitaire cone [Boardman and Conway] provides necessary conditions: valid inequalities over this cone, known as pagoda functions, were used to show the infeasibility of various peg games. In this paper, we recall these necessary conditions and present new developments: the lattice criterion, which generalizes the rule-of-three; and results on the strongest pagoda functions, the facets of the solitaire cone.
Wen-Tsuen CHEN Wen-Tsung LIN Che-Ming LU
This work presents a scalable and high performance prediction protocol for optical networks. In the proposed protocol, we develop a mathematical model to maintain the stability of a network system by prediction based on the traffic temporal locality property. All the critical factors, including transceiver tuning time, propagation delay, and processing time for dealing with control packets, are considered in the proposed prediction protocol. Furthermore, our protocol can resolve the bottlenecks attributed to control signaling and electronics processing. The performance evaluation reveals that the proposed scheme can yield the higher bandwidth efficiency and incur a lower packet delay than those of the TDM and conventional reservation schemes. Also, the proposed protocol can flexibly support any scaled network system such as MANs or LANs.
Kazumasa HIRAMATSU Atsushi MOTOGAITO Hideto MIYAKE Yoshiaki HONDA Yasushi IYECHIKA Takayoshi MAEDA Frank BERTRAM Juergen CHRISTEN Axel HOFFMANN
The epitaxial lateral overgrowth (ELO) of GaN with a stripe tungsten (W) mask pattern is performed by hydride vapor phase epitaxy (HVPE) and the crystalline and optical properties are investigated compared with ELO GaN using SiO2 mask by characterizations of X-ray rocking curve (XRC), transmission electron microscopy (TEM) and low temperature cathodoluminescence (CL). A buried ELO structure of the W mask with a smooth surface is successfully obtained. The tilt of c-axis on the W mask in the ELO GaN is not observed, but in the case of the SiO2 mask, c-axis tilts on the mask region at 1 to 10 together with small angle grain boundaries. Half the way from the ELO interface to the surface, the luminescence becomes excitonic over the whole lateral extension region, which indicates the optically high crystalline quality of the material. On the other hand, different kinds of luminescence are observed depending on the position. The difference of these luminescence is caused by the defects and/or impurity incorporation on the mask region due to the tilting of c-axis.
Osamu ODA Takayuki INOUE Yoji SEKI Akihiro WAKAHARA Akira YOSHIDA Satoshi KURAI Yoichi YAMADA Tsunemasa TAGUCHI
In this paper, the recent development of GaN bulk substrates is reviewed. Among various works on HVPE thick epitaxial growth, the largest free-standing GaN substrates upto 34 cm2 has been first obtained by the HVPE method using NGO substrates, whose lattice constant has a good matching with that of GaN. For developing larger GaN substrates with lower production cost, the ultra-high pressure solution growth method is being developed not only in Poland but also in Japan under "The Light for the 21st Century" national project.
Bit error rates (BER) for playback of (1,7) code employed in optical disc recording were simulated using an ideal (Gaussian) playback waveform, with playback being performed by PRML (Partial Response Maximum-Likelihood) combining a partial response equalizer and a double clock weighted Viterbi decoder. It was found that best BER occurs for PR(2,3,3,2) +7/10 level Viterbi decoding at a weighted value of w = 0.5 for data consisting of 107 symbols. For a minimum bit length of 0.28 µm, BER of 10-4 and less than 10-6 was obtained for SN ratios of 15.6 dB and 17.7 dB, respectively. And for a minimum bit length of 0.26 µm, BER of 10-4 and less than 10-6 was obtained for SN ratios of 16.7 dB and 18.8 dB, respectively. These results demonstrate the feasibility of a minimum bit length of 0.26 µm in current optical disc recorders.
Kozo TAGUCHI Kentaro ATSUTA Takeshi NAKATA Masahiro IKEDA
Biological object could be trapped by a single laser beam from an optical fiber end inserted at an angle to a sample chamber. Separation/coupling of an individual biological cell was easily achieved using plural optical fibers. From these experimental results, we verify that fiber optic trapping technology can provide new and novel tools for the manipulation of microorganisms and cells without physical contact.
Carla Denise CASTANHO Wei CHEN Koichi WADA
Let S be a set of n points in the plane and CH(S) be the convex hull of S. We consider the problem of constructing an approximate convex hull which contains CH(S) with strong convexity. An ε-convex δ-superhull of S is a convex polygon P satisfying the following conditions: (1) P has at most O(n) vertices, (2) P contains S, (3) no vertex of P lies farther than δ outside CH(S), and (4) P remains convex even if its vertices are perturbed by as much as ε. The parameters ε and δ represent the strength of convexity of P and the degree of approximation of P to CH(S), respectively. This paper presents the first parallel method for the problem. We show that an ε-convex (8+42)ε-superhull of S can be constructed in O(log n) time using O(n) processors, or in O(log n) time using O(n/log n) processors if S is sorted, in the EREW-PRAM model. We implement the algorithm and find that the average performance is even much better: the results are more strongly convex and much more approximate to CH(S) than the theoretical analysis shows.