We propose a learning algorithm for simple deterministic languages from queries and a priori knowledge. To the learner, a special finite subset of the target language, called a representative sample, is provided at the beginning and two types of queries, equivalence queries and membership queries, are available. This learning algorithm constructs nonterminals of a hypothesis grammar based on Ishizaka(1990)'s idea. In Ishizaka(1990)'s algorithm, the learner makes rules as many as possible from positive counterexamples, and diagnoses wrong rules from negative counterexamples. In contrast, our algorithm guesses a simple deterministic grammar and diagnoses them using positive and negative counterexamples based on Angluin(1987)'s algorithm.

The quality of an architectural design of a software system has a great influence on achieving non-functional requirements to the system, so formal evaluation and validation techniques to designed architectures are necessary in the early phase of development processes. In this paper, we present a technique for describing software architectures formally based on Coloured Petri Nets (CPNs) and a technique for reusing architectural constituents. Architectural descriptions are essentially written with a CPN language, so that the evaluation and analysis on the architectural descriptions can be made in architectural design phrase. We extract reusable architectural parts from standard architecture styles and architectural patterns so that a designer can construct an architecture by only retrieving the parts and combine them. We also designed the language for describing the combination of the architectural parts. To show the effectiveness of our techniques, we illustrate how a blackboard architecture can be composed of reusable parts and be simulated on a CPN tool (Design/CPN).

This paper proposes a reference model of CAD system generation, and describes its prototype implementation. The problems encountered in using CAD systems in industry involve complicated data handling and unsatisfied demands for domain knowledge because of the lack of a way of extracting and adopting it in the system. In the example domain of architecture, the authors have already defined domain-specific BDL (Building Design Language) for architecture experts to describe modelers of architectural structure in CAD systems by themselves. Moreover, the authors have developed a CAD system generator based on BDL descriptions. However, the different domain-specific languages required for individual domains create difficulty in developing various CAD system generators. The proposed reference model solves this problem by applying a common intermediate language based on the object model. Moreover, the model allows the creation of an integrated CAD system which contains multiple domains required by a field of industry. Its prototype implementation demonstrates its feasibility.

In order to investigate the possibility of avatar communication using sign-language, in this paper, we develop a sign-language chatting system on the Internet using CG aniamtion techniques between Korea and Japan. We construct the system in server-client architecture, where images of Korean or Japanese sign-language are analyzed into a series of parameters for sign-language animation by server. We transmit the parameters, which are text data instead of images or their compression, to clients and regenerate the corresponding CG animation using the received data. The chatting system is implemented with Visual C++ 5.0 on Windows platforms. Experimental results show that the sign-language could be used as a communication means between avatars of different languages.

In the hardware synthesis methods with high level languages such as C language, optimization quality of the compilers has a great influence on the area and speed of the synthesized circuits. Among hardware-oriented optimization methods required in such compilers, minimization of the bit length of the data-paths is one of the most important issues. In this paper, we propose an estimation algorithm of the necessary bit length of variables for this aim. The algorithm analyzes the control/data-flow graph translated from C programs and decides the bit length of each variable. On several experiments, the bit length of variables can be reduced by half with respect to the declared length. This method is effective not only for reducing the circuit area but also for reducing the delay of the operation units such as adders.

We present a symbolic language emptiness check algorithm based on forward state traversal. A verification property is given by a set of error traces written in ω-regular expression and is manipulated explicitly as a non-deterministic state transition graph. State space of the design model is implicitly traversed along the explicit graph. This method has a large amount of flexibility for controlling state traversal on the property space. It should become a good framework of incremental or approximate verification of ω-regular properties.

We have developed an active Q adaptor (AQA) to achieve integration of multiple management protocols and dynamic modification of managed object (MO) definitions. To achieve dynamic modification, we introduce a new MO framework, called dynamic-MO, which has the ability of modifying its own definition. A dynamic-MO is composed of meta-data and some behavior programs. Meta-data lists attributes of a dynamic-MO in a text format and a behavior program describes actions of a dynamic-MO in scripting language such as Java, Tcl, etc. In our AQA architecture, modules which manage individual components of a dynamic-MO communicate among themselves via an object request broker (ORB) in order to achieve system scalability with high performance. To realize the functionality of a dynamic-MO, we propose interfaces among these modules that are independent of dynamic-MO definitions and an update mechanism of behavior programs. We define the interfaces based on the common management information protocol (CMIP) operations to avoid re-defining the interfaces when dynamic-MO definitions are modified. Furthermore, to execute modified behavior programs without any negative influence on the workings of the other behavior programs, we employ a Java class-loader which has its own specific naming-space on a Java virtual machine (Java VM). With all of these features, our AQA is extremely promising for developing programmable network management systems for end-to-end management of heterogeneous telecommunication networks.

There are two approaches for formal verification of sequential designs or finite state machines: language containment checking and symbolic model checking. To verify designs of practical size, in these two approaches, designs are represented symbolically, in practice, by ordered binary decision diagrams. In the conventional algorithm for language containment checking, finite automata given as specifications are also represented symbolically. This paper proposes a new method, called partially explicit method for checking language containment. By representing states of finite automata given as specifications explicitly, this method can remove redundant computations, and as a result, provide better performance than the conventional method which uses the product machines of designs and specifications. The experimental results show that this approach is effective in checking language containment symbolically.

A software system has dynamic adaptability if it can adapt itself to dynamically changing runtime environments. As open-ended distributed systems and mobile computing systems have spread widely, the need for software systems with dynamic adaptability increases. We propose a software model with dynamic adaptability called DAS and its description language LEAD++. The basic mechanism for dynamic adaptability is called adaptable procedure. An adaptable procedure is a special kind of generic procedures (functions) whose methods are selected based upon the state of its runtime environment. Furthermore, control mechanisms of adaptable procedures -- including method selection strategies -- are realized using generic procedures. This sort of reflective architecture enables us to write a dynamically adaptable software system in highly flexible, extensible, readable and maintainable way. LEAD++ is an object-oriented reflective language that provides adaptable procedures and their control mechanisms as its basic language functionalities. We are currently implementing a prototype of LEAD++ as a pre-processor of Java. Using LEAD++, we can systematically describe dynamically adaptable applets, mobile objects, etc.

The intermediate language (IL) modularizes a compiler into target processor independent and dependent parts, called the front-end and the back-end. By adding a new back-end, it is possible to port existing software from one processor to another. This paper presents a new efficient approach to achieve multiple targeting to quite different architectures using different processors as well, by translating from one IL into other existing ILs. This approach makes it possible to reuse existing back-ends. It has been successfully applied to a commercial-scale project for porting public switching system software. Since the target ILs were not predictable in advance, we provided an abstract syntax tree (AST) with attributes accessible by abstract data type (ADT) interface to convey the source language information from our front-end to back-ends. It was translated into several ILs that were developed independently. These translations made the compiler available in a very short time for different cross-target platforms and on several workstations we needed. The structure of this AST and the mapping to these ILs are presented, and retargeting cost is evaluated.

This paper proposes the UGLR parser as an extension of the GLR parser. A UGLR parser is powerful enough to parse deterministically any phrase structure language if it is in the class of recursive languages and can parse any context free language as fast as the conventional GLR parser. Natural language processing often requires a parser for languages belonging to classes larger than that of context free languages, and the proposed parser is useful for this purpose.

This paper presents an algorithm for viewpoint-based similarity discernment of linguistic concepts on Semantic Network Array Processor (SNAP). The viewpoint-based similarity discernment plays a key role in retrieving similar propositions. This is useful for advanced knowledge processing areas such as analogical reasoning and case-based reasoning. The algorithm assumes that a knowledge base is constructed for SNAP, based on information acquired from the WordNet linguistic database. The algorithm identifies paths on the knowledge base between each given concept and a given viewpoint concept, then computes a similarity degree between the two concepts based on the number of nodes shared by the paths. A small scale knowledge base was constructed and an experiment was conducted on a SNAP simulator that demonstrated the feasibility of this algorithm. Because of SNAP's scalability, the algorithm is expected to work similarly on a large scale knowledge base.

To provide users with database-like query interfaces on HTML data, several systems have been developed to extract structures from HTML pages. Among them, tree-like structures and path expressions are the most popular modeling and navigating tools, respectively. Although path expressions are straightforward in representing top-down search patterns, they provide very limited help in representing bottom-up and in-breadth search patterns. In this paper, a lattice model is proposed to store Web data. The model provides an integrated mechanism to store text, linking information, HTML hierarchy, and sequence order of HTML data. By incorporating lattice operators with comprehension syntax, we show that the query language can represent top-down, bottom-up, and in-breadth searching patterns with uniform operators. It will be also shown that lattice comprehensions can represent all operators of path expressions, except Kleen closure.

We propose a programming language, Flage, for building software systems which dynamically adapt to changing local situations. In our language, we construct applications by agents; concurrent mobile objects with the metalevel architecture. Metalevel programming facilities realize a self-control of an agent's actions and an autonomous adaptation to changes. We also introduce another kind of program element called field. A field represents a local situation around agents. For example, one field represents a virtual place to get local information in a network environment and another represents a virtual place where agents do cooperative works. If an agent enters a field, it gets programs and shared information in the field. By moving field to field, an agent can change its program composition by itself and it adapts to changing local situations. In this paper, we describe the language specification of Flage, the implementation of the platform for Flage programming and show some program examples.

Providing various assistances for design modifications on HDL source codes is important for design reuse and quick design cycle in VLSI CAD. Program slicing is a software-engineering technique for analyzing, abstracting, and transforming programs. We show algorithms for extracting/removing behaviors of specified signals in VHDL descriptions. We also describe a VHDL slicing system and show experimental results of efficiently extracting components from VHDL descriptions.

Due to a rather low phoneme recognition rate for noisy telephone speech, there may arise large differences between N-gram built upon recognized phoneme labels and those built upon original attached phoneme labels, which in turn would affect the performances of N-gram based language identification methods. Use of N-gram built upon recognized phoneme labels from the training data was evaluated and was shown to be more effective for the language identification. The performance of mixed phoneme recognizer, in which both language-dependent and language-independent phonemes were included, was also evaluated. Results showed that the performance was better than that using parallel language-dependent phoneme recognizers in which bias existed due to different numbers of phonemes among languages.

Array redistribution is required very often in programs on distributed memory parallel computers. It is essential to use efficient algorithms for redistribution, otherwise the performance of programs may degrade considerably. In this paper, we focus on automatic generation of communication routines for multi-dimensional redistribution. The principal advantage of this work is to gain the ability to handle redistribution between arbitrary source and destination processor sets and between arbitrary source and destination distribution schemes. We have implemented these algorithms using Parallelware communication library. Some experimental results show the efficiency and flexibility of our techniques compared to the other redistribution works.

This paper presents a type inference algorithm for a logic language, HS. The algorithm uses a program transformation, SPS, to given programs as a type inference. This method is theoretically clear, because applying it to given programs is equal to executing it partially. No other additional framework is needed for our approach. In contrast, many studies on type inference for logic languages are based on Mycroft and O'Keefe's famous algorithm, which was initially developed for functional languages. Therefore, the meanings of the algorithms are theoretically unclear in the domain of logic languages. Our type inference is flexible. Users of the type inference system can specify the types of objects abstractly (weakly) if the types are not exactly known, or they can specify them particularly (strongly) if the types are exactly known. Both kinds of programs are inferred for types. In contrast, many type inference systems accept purely untyped programs. Thus, with these two features, our method is simple and flexible.

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 + .

Exception handling is not only useful for increasing program readability, but also provides an effective means to check and locate errors, so it increases productivity in large-scale program development. Some typical and frequent program errors, such as out-of-range indexing, null dereferencing, and narrowing violations, cause exceptions that are otherwise unlikely to be caught. Moreover, the absence of a catcher for exceptions thrown by API procedures also causes uncaught exceptions. This paper discusses how the exception handling mechanism should be supported by the compiler together with the operating system and debugging facilities. This mechanism is implemented in the compiler by inserting inline check code and accompanying propagation code. One drawback to this approach is the runtime overhead imposed by the inline check code, which should therefore be optimized. However, there has been little discussion of appropriate optimization techniques and efficiency in the literature. Therefore, a new solution is proposed that formulates the optimization problem as a common assertion elimination (CAE). Assertions consist of check code and useful branch conditions. The latter are effective to remove redundant check code. The redundancy can be checked and removed precisely with a forward iterative data flow analysis. Even in performance-sensitive applications such as telecommunications software, figures obtained by a CHILL optimizing compiler indicate that CAE optimizes the code well enough to be competitive with check suppressed code.