TR93-0001
Theory refinement based on the
minimum description length principle
Somkiat Tangkitvanich and Masamichi Shimura
Contact person
Somkiat Tangkitvanich
(sia@cs.titech.ac.jp)
Abstract
We present an approach to a new learning problem, the problem
of learning from an approximate theory and a set of noisy examples.
This problem requires a new learning approach since it cannot be
satisfactorily solved by either inductive, or explanation-based learning
algorithms or their existing combinations. Our approach can be viewed
as an extension of the minimum description length (MDL) principle, and
is unique in that it is based on the encoding of the refinement
required to transform the given theory into a better theory rather
than on the encoding of the resultant theory as in traditional MDL.
Experimental results show that, based on our approach, the theory
learned from an approximate theory and a set of noisy examples is more
accurate than either the approximate theory itself or a theory
learned from the examples alone. This suggests that our approach can
combine useful information from both the theory and the training set
even though both of them are only partially correct.
TR93-0002
On Closure Properties of GapP
Thomas Thierauf, Seinosuke Toda and Osamu Watanabe
Contact person
Osamu Watanabe
(watanabe@cs.titech.ac.jp)
Abstract
\def\GapPplus{{\rm GapP}_+}
We study the closure properties of the function classes GapP and $\GapPplus$.
We characterize
the property of $\GapPplus$ being closed under
decrement and of GapP being closed
under maximum, minimum, median, or division
by seemingly implausible collapses among complexity classes;
thereby giving evidence that
these function classes don't have these closure properties.
We show a similar result concerning operations
we call {\em bit cancellation\/} and {\em bit insertion}:
Given a function $f \in \GapPplus$ and
a polynomial-time computable function~$\kappa$.
Then we ask whether the function~$f^*(x)$
that is obtained from $f(x)$
by canceling the $\kappa(x)$-th bit in the binary representation of $f(x)$,
or whether the function~$f^{\scriptscriptstyle +}(x)$
that is obtained from $f(x)$
by inserting a bit at position $\kappa(x)$ in the binary representation of $f(x)$,
is also in $\GapPplus$.
We give necessary conditions and a sufficient conditions
for $\GapPplus$ being closed under bit cancellation and bit insertion, respectively.
TR93-0003
Current trends on parsing - a survey
Hozumi Tanaka
Contact person
Hozumi Tanaka
(tanaka@cs.titech.ac.jp)
Abstract
The history of parsing natural languages began with the formal
linguistic theory developed by N.Chomsky who classified languages into
four classes, unrestricted languages, context-sensitive languages,
context-free languages and regular languages. These languages are
produced by applying rewriting rules, or otherwise called production
rule, in the form of $\alpha \rightarrow \beta$ in which a string
$\alpha$ is rewritten as another string $\beta$. Chomsky pointed out
that only context-free grammar is not enough to specify a natural
language, and he insisted on the necessity of context sensitiveness.
However from the point of practical parsing, it is very difficult to
device a parsing algorithm for context-sensitive grammar. Recently,
Gazdar et.al., advocate the power of context-free grammar in covering
broad range of natural languages [Gazdar, 85]. As many efficient
parsing algorithms have been developed for context-free grammars, most
natural language processing systems make use of context-free grammars.
In this paper we survey some of the important parsing algorithms and
present our conclusion and discussion.
TR93-0004
Discourse analysis of scientific textbooks in Japanese : a
tool for producing automatic summaries
Nadine Lucas, Nishina Kikuko, Akiba Tomoyoshi and Suresh K.G
Contact person
Suresh, K.G
(suresh@cs.titech.ac.jp)
Abstract
3 text-books for undergraduate students on scientific domains are
analysed from the lexical and structural point of view. The
statistical lexical approach is conducted automatically with respect
to the distribution and progression of lexical entries (key-words as
given in the index). The structural analysis is a new procedure. It is
based on surface markers and relies on linguistic primitive relations.
Formalism is expressed in terms of block and clip. Relations are
recognised first at each level (paragraph, section, chapter, part,
book), then the inclusion pattern of levels is calculated to find the
overall structure of the text. Combination of the two methods allows
to assess the relative importance of each chapter inside the book with
reference to key-words or to give special weight to a key-word used in
core position. This method conveys enough information to provide a
frame for text compression and production of summaries.
TR93-0005
On symmetry of information and polynomial time invertibility
Luc Longpr\'{e} and Osamu Watanabe
Contact person
Osamu Watanabe
(watanabe@cs.titech.ac.jp)
Abstract
Symmetry of information states that
for two strings $x$ and $y$,
${\rm K}(xy)={\rm K}(x)+{\rm K}(y|x)\pm O(\log |xy|)$.
We consider
whether symmetry of information holds
in a polynomial time bounded environment.
Intuitively,
this problem is related to
the complexity of inverting a polynomial time computable function.
We give some evidence supporting this intuition,
by proving the following relations:
\begin{enumerate}
\item
If polynomial time symmetry of information holds,
then for any polynomial $p$,
there is a polynomial time algorithm
that computes the shortest $p$-time description of a string
for ``almost all'' strings.
\item
If polynomial time symmetry of information holds,
then every polynomial time computable function is
probabilistic polynomial time invertible
for ``almost all'' strings in its domain.
\item
If ${\rm P}={\rm NP}$
(i.e.,
every polynomial time computable function is
polynomial time invertible),
then polynomial time symmetry of information holds.
\end{enumerate}
TR93-0006
Efficient verification of parallel real-time systems
Tomohiro Yoneda, Atsufumi Shibayama, Yoshihiro Tohma, Holger Schlingloff and Edmund M. Clarke
Contact person
Tomohiro Yoneda
(yoneda@cs.titech.ac.jp)
Abstract
This paper presents an efficient model checking algorithm for
one-safe time Petri nets and a new timed temporal logic.
TR93-0007
A theory of extended pseudo-biorthogonal bases
Nasr-Eddine Berrached and Hidemitsu Ogawa
Contact person
Yukihiko Yamashita
(yamasita@cs.titech.ac.jp)
Abstract
This paper introduces the concept of an
"extended pseudo-biorthogonal basis" (EPBOB),
which is a generalization of the concepts of an orthonormal (OB),
a biorthonormal (BOB), a pseudo-orthogonal (POB),
and a pseudo-biorthogonal (PBOB) bases.
For a better understanding and a wide application of EPBOB,
this paper provides their characterization
and shows how they preserve the formalism of BOB.
It also shows how to construct them.
TR93-0008
Extended pseudo-biorthgonal bases of type O and type L
Nasr-Eddine Berrached and Hidemitsu Ogawa
Contact person
Yukihiko Yamashita
(yamasita@cs.titech.ac.jp)
Abstract
As a generalization of the concept of pseudo-biorthogonal bases (PBOB),
we already presented the theory of
the so-called extended pseudo-biorthogonal bases (EPBOB).
We introduce in this paper two special types of EPBOB
called EPBOB's of type O and of type L.
This paper discusses characterizations, construction methods,
inherent properties, and mutual relations of these types of EPBOB.
TR93-0009
General sampling theory as an extended pseudo-biorthgonal expansion
Nasr-Eddine Berrached and Hidemitsu Ogawa
Contact person
Yukihiko Yamashita
(yamasita@cs.titech.ac.jp)
Abstract
We propose in this paper a general sampling theorem with real pulse in
the reproducing kernel Hilbert space by using the theory of extended
pseudo-biorthogonal bases.
The theorem holds even when the reconstruction functions
do not belong to the subspace of signals to be reconstructed.
The theorem includes the sampling theorem with ideal pulse,
with non-uniform samples, for general integral transforms,
for over-sampling and for under-sampling as its special cases.
For under-sampling, the theorem provides the best approximation
to the individual original signal.
TR93-0010
Relative Karhunen-Lo\`eve operator
Y. Yamashita and H. Ogawa
Contact person
Yukihiko Yamashita
(yamasita@cs.titech.ac.jp)
Abstract
The Karhunen-Lo\`eve (K--L) subspace is a subspace
which provides the best approximation for a stochastic signal
under the condition that its dimension is fixed.
The K--L subspace has been successfully used in
the data compression in communication and
the subspace method in pattern recognition.
The K--L subspace, however, does not consider a noise in communication
and a noise and other patterns in pattern recognition.
Therefore, its noise suppression is not sufficient in communication
and it gives a wrong recognition result for patterns which are
similar to each other.
In order to solve this problem,
we propose a concept of the relative K--L operator.
The relative K--L operator minimizes
the sum of the mean square error
between the original signal and the approximated signal
and the mean square error caused by noise
under the condition that the dimension of its range is fixed.
We provide the conditions under which
the relative K--L operator exists.
We also provide its general form.
TR93-0011
Recognition of handwritten characters in the presence of noise
D. Liu, Y. Yamashita and H. Ogawa
Contact person
Yukihiko Yamashita
(yamasita@cs.titech.ac.jp)
Abstract
Recognition of handwritten characters
was and still remains a difficult
problem due to the large degree of variability that the data exhibit.
The CLAFIC (CLAss-Featuring Information Compression) method performs
very well in the recognition of handwritten characters.
But the noise may be introduced during the observation process.
To increase the recognition accuracy rate in the presence
of noise is an important problem for character recognition.
But the original K--L subspace which is used in CLAFIC
only considers signals without noise.
In this paper, we present a new method for the
recognition of Japanese handwritten characters using the relative
K--L operator which is an operator such that it minimizes the sum of
the mean square error of signals and the mean square error caused by noises.
The experimental results demonstrate that the performance of the method is
superior to that of CLAFIC.
TR93-0012
Improving a fault-tolerant clock synchronization algorithm
by overcorrection
Toru Egashira, Tomohiro Yoneda and Yoshihiro Tohma
Contact person
Tomohiro Yoneda
(yoneda@cs.titech.ac.jp)
Abstract
We have proposed a new fault-tolerant clock synchronization algorithm
by applying the overcorrection technique to LM-CNV algorithm. This
algorithm with almost the same computational complexity as LM-CNV
algorithm has higher worst-case synchronization accuracy than LM-CNV
algorithm, and behaves as well as LM-CNV algorithm in a realistic
situation.
TR93-0013
On sets bounded truth-table reducible to P-selective sets
Thomas Thierauf, Seinosuke Toda and Osamu Watanabe
Contact person
Osamu Watanabe
(watanabe@cs.titech.ac.jp)
Abstract
We show that
if every NP set is $\le^{\rm P}_{\rm btt}$-reducible to
some P-selective set,
then NP is included in ${\rm DTIME}(2^{n^{O(1/\sqrt{\log n})}})$.
The result is extended
for some unbounded reducibilities
such as $\le^{\rm P}_{(\log n)^{O(1)}\mbox{-}{\rm tt}}$-reducibility.
TR93-0014
Methods of Convex Projections with Optimum Condition
Yukihiko Yamashita
Contact person
Yukihiko Yamashita
(yamasita@cs.titech.ac.jp)
Abstract
The method of convex projections is a
well-known image restoration technique.
By the weak convergence of
alternating convex projections onto closed convex sets
in which the original image is assumed to be included,
the method of convex projections
provides an element in the intersection of these convex sets.
However, there exists the case that their intersection is empty
because of improper convex sets.
The original theorem mentioned nothing for the case.
We propose a new theorem which guarantees
that the series of alternating convex projections shall converge weakly
to a fixed point of the alternating convex projection operator
under some condition even when their intersection includes no element.
We can examine whether those convex sets are proper or not by its limit.
Furthermore, in order to improve its ability for image restoration
we propose a new methods to obtain an element
which satisfies a quadratic optimum condition
among fixed points of the alternating convex projection operator.
We also propose a new method with a linear optimum condition.
TR93-0015
A new Algorithm for Linear Programming by Methods of Convex Projections
Yukihiko Yamashita
Contact person
Yukihiko Yamashita
(yamasita@cs.titech.ac.jp)
Abstract
We propose new algorithms for linear programming.
These algorithms are
very simple and can be implemented very easily.
The basis of these algorithms is
the method of convex projections for image restoration.
In order to improve the convergence speed,
we apply the steepest descent method and the conjugate gradient
method to it.
Those algorithms have advantage for speed, storage size,
and accuracy.
We apply these algorithms to a small size of linear
programming problem as a demonstration.
Finally we show a method to implement these algorithms
in neural networks.
TR93-0016
A new scheme of non-interactive ID-based key sharing
with explosively high degree of separability
S. Tujii, K. Araki and T. Sekine
Contact person
Shigeo Tsujii
(fax:+81-3-3729-0685)
Abstract
We consider the structure of NIKS
and propose a new scheme based on the concept
of the degree of separability and the powerful method
of interactive cancellation of random numbers.
The newly introduced concept called
the degree of separability
in both the key generating process and
the form of shared key seems to play a vital role
to clarify collusion threshold explicitly.
TR93-0017
Training the gradient field
of a dynamic Hopfield (recurrent) network for classification
Craig Hicks and Hidemitsu Ogawa
Contact person
Yukihiko Yamashita
(yamasita@cs.titech.ac.jp)
Abstract
A new algorithm for training a continuous recurrent network for pattern
recognition is given. The fixed points of the network and their basins of
attraction are shaped by specifying desired gradient vectors over sets of
points in the network state vector space, and training the weights
accordingly.
TR93-0018
The recurrent gradient network (RGN):
A recurrent network for categorization
Craig Hicks and Hidemitsu Ogawa
Contact person
Yukihiko Yamashita
(yamasita@cs.titech.ac.jp)
Abstract
A new form for a continuous recurrent neural network which we call the
Recurrent Gradient Network (RGN) is proposed which is especially
suitable for pattern recognition or associative memory. Like a dynamic
Hopfield network the dynamics are described by a set of simultaneous
differential equations, but a hidden layer of distance measure units is also
included. Other nonlinear hidden layers may also be included in the general
model. The result is greater power of the net to express an arbitrary
gradient field, so that memory capacity is increased.
In addition, the choice
of hidden layer activation functions ensures convergence in finite time
in the general case. The
gradient based training (GBT) algorithm introduced by these authors in
previous work may be used to train this network over a set of noisy training
data.
TR93-0019
The recurrent gradient network (RGN):
A network for pattern recognition
Craig Hicks and Hidemitsu Ogawa
Contact person
Yukihiko Yamashita
(yamasita@cs.titech.ac.jp)
Abstract
The high memory capacity Recurrent Gradient Network (RGN) is introduced. It's
dynamics are described by simultaneous differential equations. A hidden layer
of distance measure units is also included. The choosen activation functions
ensure finite time convergence to fixed points. Initializing the net provides
instant training as shown in simulation.
TR93-0020
A new scheme of non interactive ID-based key sharing
with explosively high degree of separability
(second version)
Shigeo Tujii, Kiyomichi Araki and Takashi Sekine
Contact person
Shigeo Tsujii
(fax:+81-3-3729-0685)
Abstract
We consider the structure of NIKS
and propose a new scheme based on the concept
of the degree of separability and the powerful method
of interactive cancellation of random numbers.
The newly introduced concept called
the degree of separability
in both the key generating process and
the form of shared key seems to play a vital role
to clarify collusion threshold explicitly.
TR93-0021
A defect-tolerant WSI file memory system
using address permutation scheme for spare allocation
Eiji Fujiwara and Masaharu Tanaka
Contact person
Eiji Fujiwara
(fujiwara@cs.titech.ac.jp)
Abstract
This paper proposes a large capacity high-speed file memory system
implemented with wafer scale RAM which adopts novel defect-tolerant
technique. The defective
memory blocks in the wafer are repaired by switching with the spare ones
based on set-associative mapping. In order to repair the clustered defective
blocks, these are permuted logically with other blocks by adding some constant
value to the input block address. The defective blocks remained even after
applying the above two methods are repaired by using error correcting codes
which also correct soft errors induced by alpha particles in an on-line
operation.
With using the proposed technique, this paper demonstrates a large capacity
high-speed WSI file memory system implemented with high fabrication yield
and low redundancy rate.
TR93-0022
A probabilistic measurement for totally self-checking circuits
Jien-Chung Lo and Eiji Fujiwara
Contact person
Eiji Fujiwara
(fujiwara@cs.titech.ac.jp)
Abstract
In this papaer we propose a probabilistic measurement for totally self-checking
(TSC) circuits. This measurement is analogous to reliability of fault-tolerant
systems and is defined as the Probability of Achieving TSC Goal (PATG).
PATG surpasses the TSC definitions in determining the applicability of a
circuit in an given application environment. For example, we show that an
embedded TSC two-rail checker with two out of its four code word inputs
unavailable gains a higher PATG than that in the ideal case. We also
demonstrate the extension of PATG concept to strongly fault-secure (SFS)
circuits and strongly code disjoint (SCD) checkers. The PATG can be used in
product specification, analogous to reliability, and can give precise
behavioral description on fault/error handling performance of TSC circuits.
This is a crucical step toward the practical applications of TSC or CED
circuits.
TR93-0023
Fault-tolerant associative memories
Eiji Fujiwara and Tsuyoshi Tanaka
Contact person
Eiji Fujiwara
(fujiwara@cs.titech.ac.jp)
Abstract
This paper proposes novel fault-tolerant techniques for associative memories,
especially for translation lookaside buffer (TLB). They consists of the
following four techniques: (1) distance separable technique which masks faults
in associative memory cells, (2) coding technique which checks one to one
correspondence between the contents of the associative memory part and those in
SRAM part and also corrects errors in SRAM, (3) simplified 1-out-of-n check
which checks multiple association errors in the associative memory part, and
(4) graceful degradation technique which prohibit using defective memory parts.
The proposed fault-tolerant TLB having 128 entries and 32 address bits can be
obtained with 28% area augmentation and around 99% single fault detection
capability.
TR93-0024
Approximate solvability
of NP-like problems
(Survey,
in Japanese)
Osamu Watanabe
Contact person
Osamu Watanabe
(watanabe@cs.titech.ac.jp)
Abstract
It has been widely believed that
some NP-like problems
(i.e., NP problems, NP optimization problems)
are not polynomial-time solvable.
But it may be possible to
solve their approximation problems
or to develop pseudo polynomail-time algorithms solving them,
and considerable efforts have been made
towards such approximation approach.
This paper surveys general results concerning
the possibility of the following approximation approaches:
approximation of NP decision problems (P-closeness),
approximation of NP optimization problems,
randomized algorithm,
polynomial-size cirucuits,
neural network (analog compuation),
and average-case analysis.
TR93-0025
The use of higher functionality of units to enhance fault tolerance of
neural networks
Yoshihiro Tohma and Takuya Iwata
Contact person
Yoshihiro Tohma
(tohma@cs.titech.ac.jp)
Abstract
If a higher functionality of each unit, instead of the
sigmoid function of simple sum of the inputs, can be used,
we can design neural networks which tolerate the mixture
of stuck-at-1 and stuck-at-0 faults without relying on the
triplication.
TR93-0026
Integration of Morphological and Syntactic Analysis based on LR
Parsing Algorithm
Hozumi Tanaka, Takenobu Tokunaga and Michio Aizawa
Contact person
Takenobu Tokunaga
(take@cs.titech.ac.jp)
Abstract
Morphological analysis of Japanese is very different from that of
English, because no spaces are placed between words. The analysis
includes segmentation of words. However, ambiguities in segmentation is
not always resolved only with morphological information. This paper
proposes a method to integrate the morphological and syntactic
analysis based on LR parsing algorithm. An LR table derived from
grammar rules is modified on the basis of connectabilities between two
adjacent words. The modified LR table reflects both the morphological
and syntactic constraints. Using the LR table, efficient
morphological and syntactic analysis is available.
TR93-0027
Dependency-directed Unification of Functional Unification Grammar in
Text Generation
Kentaro Inui, Takenobu Tokunaga and Hozumi Tanaka
Contact person
Takenobu Tokunaga
(take@cs.titech.ac.jp)
Abstract
In text generation, various kinds of choices need to be decided.
In the conventional framework, which can be called ``one-path
generation framework,'' these choices are decided in an order designed
carefully in advance. However, many researchers have pointed out that
the choices, generally, depend on one another and the one-path
generation framework cannot handle these interdependencies
sufficiently. Our previous paper proposed introducing a revision
process into text generation for solving this problem. In our
framework, the overall generation process consists of the initial
generation process, followed by the revision process. The revision
process gives us opportunities to change choices that have already
been made. In general, a change in a choice point may cause changes in
other choice points, and such dependencies can be managed by Truth
Maintenance System (TMS). However, it is well known that dependency
network management in TMS requires some computational overhead in
general. We need an efficient implementation of network management to
make our framework feasible. In this paper, we propose an efficient
implementation of dependency network management in Prolog. In our
implementation, arcs between dependent nodes are represented by
bindings of logical variables, and efficient state propagation is
realized by destructive argument substitutions.
TR93-0028
Natural Language Analysis and Generation Techniques
Hozumi Tanaka, Takenobu Tokunaga, K.\ G.\ Suresh and Kentaro Inui
Contact person
Takenobu Tokunaga
(take@cs.titech.ac.jp)
Abstract
Analysis and generation are the two main aspects in the natural
language processing. In this paper we survey some of the progress made
towards natural language analysis (parsing) and generation.
Particularly, we consider syntactic analysis and present two frequently
used parsing algorithms, namely Chart and GLR parsing algorithms. Then
we go on to tell the importance of context sensitiveness in syntactic
analysis by surveying probabilistic parsing methods, which are some of
the recent developments made in this direction. In the second part of
this paper we first give a brief survey on natural generation
researches and discuss the future research direction.
TR93-0029
Design of a quasi-delay-insensitive microprocessor
Takashi Nanya, Yoichiro Ueno, Hiroto Kagotani, Masashi Kuwako and Akihiro Takamura
Contact person
Takashi Nanya
(nanya@cs.titech.ac.jp)
Abstract
This paper describes the design and implementation of an asynchronous
general-purpose microprocessor based on the delay-insensitive model with
isochronic forks. The authors also discuss major technical challenges
toward the realization of dependable and high-performance asynchronous VLSI
systems.
TR93-0030
A review of fault-tolerant computing for
safety critical applications in Japan
Yoshihiro Tohma
Contact person
Yoshihiro Tohma
(tohma@cs.titech.ac.jp)
Abstract
This paper reviews techniques of fault-tolerant computing which were
contributed substantially by Japanese industries and academia, covering
not only the development of fault-tolerant computers but also topics of
basic researches.
TR93-0031
An optimal parallel algorithm for learning DFA
Jose Balc\'{a}zar, Josep D\'\i\/az, Ricard Gavald\`{a} and Osamu Watanabe
Contact person
Osamu Watanabe
(watanabe@cs.titech.ac.jp)
Abstract
In 1987,
D.~Angluin presented an algorithm that exactly
learns regular languages represented by deterministic finite
automata (dfa) from Membership and Equivalence queries.
Furthermore, the algorithm is feasible in the sense that
it takes time $O(n^2m^2)$, where $n$ is the number of states of the
automaton and $m$ is the length of the longest counterexample
to an Equivalence query. This paper studies whether parallelism
can lead to substantially more efficient algorithms for the problem.
We show that no CRCW PRAM machine using a number of processors
polynomial in $n$ and $m$ can identify dfa in $o(n/\log n)$ time.
Furthermore, this lower bound is tight:
we develop a CRCW PRAM learning algorithm
that uses polynomially many processors and exactly learns dfa
in $O(n/\log n)$ time.
TR93-0032
Test instance generation for promised NP search problems
Osamu Watanabe
Contact person
Osamu Watanabe
(watanabe@cs.titech.ac.jp)
Abstract
In this paper,
we discuss
the problem of generating test instances for promised NP search problems.
A technical framework is proposed for studying this problem,
and it is shown that
all known distNP-hard search problems are ``complete''
for test instance generation problems.
TR93-0033
An evaluation method of an attribute grammar based language
by extended term rewriting systems
Yutaka Kikuchi
Contact person
Yutaka Kikuchi
(kikuchi@cs.titech.ac.jp)
Abstract
I propose new rewriting systems
and an evaluation method of the language AG on them.
The rewriting systems are extended from regular term rewriting systems,
that permit multi-valued function symbols and sharing computation trees.
The language AG is a functional programming language
based on attribute grammars,
whose naive evaluator tends to make redundant copies of same attributes
and evaluates only eagerly.
An evaluator using the rewriting systems prevents needless copies
and can work as lazy evaluation.
TR93-0034
An attribute grammar modelling of
interactive figures
Takehiro Tokuda and Yoshimichi Watanabe
Contact person
Yoshimichi Watanabe
(nabe@cs.titech.ac.jp)
Abstract
Interactive figures are figures which we can interact with, and we can
perform semantic computations on the structure. This paper presents a
new modelling of interactive figures based on the concept of attribute
grammars. Traditional methodologies such as that of C++, HyperTalk,
and Lingo cannot define semantic computations on figures in a clear
way. Our model can define semantic computations inductively on the
structure of the figure.
TR93-0035
An efficient semantic evaluator
for warped LC(1) attributed grammars
Takehiro Tokuda and Yoshimichi Watanabe
Contact person
Yoshimichi Watanabe
(nabe@cs.titech.ac.jp)
Abstract
We present an efficient construction method for a new class of one-pass
evaluatable attribute grammars called warped LC(1) attributed grammars.
Unlike top-down parsing based LL-attributed grammars and bottom-up parsing
based LR-attributed grammars, we use the left corner parsing (LC(k) parsing)
method which is a combination of bottom-up parsing and top-down parsing. As a
very wide class of LC(1) parsing based attribute grammars, there exists a
class called LC-attributed grammars. LC-attributed grammars require a
substantial precomputation for constructing an evaluator from a parser. Our
warped LC(1) attributed grammars allow us to execute an evaluator
simultaneously with an LC(1) parser without requiring any precomputation.
TR93-0036
An attribute evaluation of
context-free languages
Takehiro Tokuda and Yoshimichi Watanabe
Contact person
Yoshimichi Watanabe
(nabe@cs.titech.ac.jp)
Abstract
We present a method of evaluating attributes of input strings defined by
attribute grammars having general context-free underlying grammars and
naturally restricted semantic rules. Our attribute evaluation method is based
on Earley's parsing method. Hence we can evaluate attributes without building
corresponding derivation trees or attribute dependency graphs. Also we can
compute all the possible attribute values for unambiguous or ambiguous
context-free underlying grammars. Our method serves as a solution to the local
constant inherited attribute problem.
TR93-0037
LR-attributed grammar evaluators can
solve local constant problems
Takehiro Tokuda
Contact person
Yoshimichi Watanabe
(nabe@cs.titech.ac.jp)
Abstract
We present a completely new approach to the construction of a parser/evaluator
for LR(k) parsing based one-pass attribute grammars. Traditional methods
cannot handle local constant inherited attributes of left-recursive
left-corner nonterminals. Our method can handle non-traditional cases
including local constant problems as well as cases handled by traditional
methods.
TR93-0038
A class of error control codes for byte organized memory systems
----- S$b$\/EC-(S$b$+S)ED Codes -----
Mitsuru Hamada and Eiji Fujiwara
Contact person
Eiji Fujiwara
(fujiwara@cs.titech.ac.jp)
Abstract
This paper proposes a new class of error control codes, called single $b$-bit
byte error correcting and single $b$-bit byte plus single bit error detecting
codes, or S$b$\/EC-(S$b$+S)ED codes.
Here, ``byte'' denotes a cluster of $b$ bits, where $b \geq 2$.
The codes are suitable for semiconductor memory systems organized in a
$b$-bit-per-chip manner, since they can
both correct all single byte hard errors due to chip failures and
detect any single bit error, induced by
an $\alpha$ particle or a cell failure, lined up in a
codeword with another existing single byte hard error. This paper presents
bounds on check bit length, three construction methods and a general
decoding scheme for S$b$\/EC-(S$b$+S)ED codes.
The construction methods, one of which uses the nature of
minimum polynomials over finite fields, provide codes
of arbitrary byte length and code length.
Some of the proposed codes meet lower bounds on check bit length.
TR93-0039
A class of error locating codes
-- $SEC-S_{e/b}EL$ Codes --
Masato Kitakami and Eiji Fujiwara
Contact person
Eiji Fujiwara
(fujiwara@cs.titech.ac.jp)
Abstract
This paper proposes a new class of error locating codes, i.e., $SEC-S_{e/b}EL$
codes.
This corrects single-bit errors and indicates location of erroneous memory
chip if the error is $e$ or fewer bits involved in a byte.
While the $SEC-S_{b/i \cdot b}EL$ codes indicate an erroneous memory card,
the $SEC-S_{e/b}EL$ codes indicate an erroneous memory chip.
The predominant errors even in the byte-organized memory chips are soft errors
induced by alpha particles, which are apt to manifest themselves as single
bit errors.
This paper clarifies the bounds of the $SEC-S_{e/b}EL$ codes.
>From this,
the $SEC-S_{e/b}EL$ codes constructed from tensor product of the $S_bEC$ codes
and the $SEC-eED$ codes have been proved to be very efficient
under some conditions of the code parameters.
TR93-0040
Karhunen-Loeve subspace
Hidemitsu Ogawa
Contact person
Yukihiko Yamashita
(yamasita@cs.titech.ac.jp)
Abstract
The Karhunen-Loeve expansion is a well-known technique in the
pattern recognition field. Surprisingly, however,
there is no exact proof of the K-L
expansion in the context of approximation to a set of patterns.
This paper provides an exact proof of the following well-known
theorem : "An N-dimensional subspace provides the best approximation to
a set of patterns if and
only if it is spanned by the first N-number of eigenelements of the
covariance operator of the pattern set."
TR93-0041
Neural network learning, generalization and over--learning
Hidemitsu Ogawa
Contact person
Yukihiko Yamashita
(yamasita@cs.titech.ac.jp)
Abstract
A framework for discussing the learning problem for multi-layer
feedforward neural networks is introduced from the point of the view of
inverse problem. It naturally leads us to the concept of optimal
generalization and methods for choosing training data and optimal number of
hidden units and for constructing optimally generalizing neural
networks. It also leads us to the concept of J-over-learning and
methods for choosing training data for preventing over-learning.
TR93-0042
A theory of over-learning
Hidemitsu Ogawa and Kazutaka Yamasaki
Contact person
Yukihiko Yamashita
(yamasita@cs.titech.ac.jp)
Abstract
This paper discusses the over-learning problem for multilayer perceptrons(MLP).
The concept of over-learning is mathematically defined under the framework
of the inverse problem and the conditions giving rise to over-learning
are clarified.
An example is examined and it is shown how to design a set of training
data to prevent over-learning.
TR93-0043
A theory of over-learning in the presence of noise
Kazutaka Yamasaki and Hidemitsu Ogawa
Contact person
Yukihiko Yamashita
(yamasita@cs.titech.ac.jp)
Abstract
We discuss the over-learning problem for multilayer
feedforward neural networks.
A framework was proposed by the present authors for the over-learning
problem with noise free training data.
In this paper, first we show that the framework is still valid in the case of
noisy training data.
It is applied to the case where the rote memorization criterion is used
as a substitute for the Wiener criterion.
Necessary and sufficient conditions for two kinds of admissibility
of the rote memorization criterion by the Wiener criterion are obtained.
These conditions lead us to a method for choosing a training set which prevents
Wiener-over-learning.
TR93-0044
Manpower shift assignment: algorithms and complexity (part I)
Hoong Chuin Lau
Contact person
Hoong Chuin Lau
(hclau@cs.titech.ac.jp)
Abstract
We consider the problem of shift assignment in manpower scheduling. We
enumerate 8 variants of the problem: the schedule may be normal or cyclic, the
shift change constraint may be monotonic or unrestricted, and the demands may
be exact or slack. We show the NP-completeness of four of them, and present
polynomial algorithms to solve two others. The complexity of two other
variants remains open. Our work formally defines the computational
intractibility of manpower shift scheduling and thus justifies existing works
in developing manpower scheduling systems using combinatorial and heuristic
techniques.
TR93-0045
Acquisition of knowledge for natural language processing
(in Japanese)
Yosiyuki Kobayasi
Contact person
Takenobu Tokunaga
(take@cs.titech.ac.jp)
Abstract
This paper surveys the methods to extract useful knowledge for
natural language processing from the various kinds of machine readable
language resources, such as dictionaries, corpora and so on.
TR93-0046
A study on continuous speech recognition system
(in Japanese)
Katunobu Itou
Contact person
Takenobu Tokunaga
(take@cs.titech.ac.jp)
Abstract
This paper describes how to construct a continuous speech recognition
system. For large vocabulary applications, current continuous speech
recognition systems have the following two points are left as
problems. First, the computation grows exponentially with the size of
vocabulary. Second, they cannot deal with words out of vocabulary. To
solve these problems, I propose a new technique to construct a speech
recognition systems to utilize multi-level knowledge sources. To
avoid the extra computation, the system keeps the hypothesis of the
each level in each level. To avoid growing the computation in
proportion to the size of the vocabulary, I propose new DP matching
control method. In the traditional DP matching method, the system does
matching by controlling by automata directly. However, in the proposed
method, the system does matching by controlling by automata indirectly
with an approximate method. To process unknown words, knowledge
sources are integrated as the heterarchy model. The heterarchy model
enables to utilize the multiple constraint to the same level. In this
system, two types of processing, one with stochastic language models
without any other linguistic knowledge and the other with a
dictionary, are used to construct word level hypotheses. The system
can detect and transcribe the unknown words automatically. I tested
the system using a task with bunsetu perplexity 650. It produced
bunsetu accuracy of 73.9% for the open speakers and open sentences.
Furthermore, to construct a real speech dialogue system using the
proposed method, I describe design issues of a speech dialogue system,
the evaluation of the system, and the data collection of spontaneous
speech in a transportation guidance domain.
TR93-0047
Attribute grammars as record calculus
Katsuhiko Gondow and Takuya Katayama
Contact person
Katsuhiko Gondow
(gondow@cs.titech.ac.jp)
Abstract
We present a new denotational semantics of attribute grammars that
are based on Cardelli's record and lambda calculus. Our goal is to
define, using the semantics, computational models based on attribute
grammars for describing structure-oriented software development
environments.
As the first step toward the end, we present as extensions of the
semantics formal definitions of OOAG (object oriented attribute
grammars) and higher order attribute grammars. They have the
capability to transform structures of attributed trees depending on
their attribute values.
The rest of this paper is written in Japanese.