TR95-0001
A learning mechanism of logic programs by dynamically sharing substructures
Masayuki Numao,
Shigekazu Morita,
and Kenichi Karaki
Contact person
write to Masayuki Numao
(numao@cs.titech.ac.jp)
Abstract
We propose a reasoning method by graph reduction, which proves a
predicate logic formula by reducing its graph representation. Since
the method directly reduces a logic formula represented by a graph, it
{\em self-optimize\/}s a graph representation, i.e., it automatically
transforms logic formulas into an efficient form, which is equivalent
to one acquired by Explanation-Based Learning. In this mechanism, by
sharing an original subgraphs between learned formulas, reasoning
efficiency does not deteriorate even after learning a number of
examples, and therefore it overcomes the utility problem. We
demonstrate the above properties in some simple list manipulation
problems and geometric theorem proving.
TR95-0002
Automatic thesaurus construction based on grammatical relations
Takenobu Tokunaga,
Makoto Iwayama,
and Hozumi Tanaka
Contact person
write to Takenobu Tokunaga
(take@cs.titech.ac.jp)
Abstract
A method to construct thesauri from grammatical relations is proposed.
The proposed method constructs thesauri by using hierarchical
clustering algorithm. The emphasis is put on creating a thesaurus for
each grammatical relation (surface case). We refer to the thesauri as
``case-based thesauri (CBT).'' In the experiment, four CBTs of
Japanese nouns were constructed from 26,023 verb-noun co-occurrence
data of Japanese, and they were evaluated by objective criteria. The
experiment has shown the CBTs has better properties for selectional
restriction of case frames.
TR95-0003
Circuit complexity
of an explicity defined first slice function
Tatsuie Tsukiji
Contact person
write to Tatsuie Tsukiji
(tsukiji@cs.titech.ac.jp)
Abstract
We construct
a family of subset $D_1,\ldots,D_n$ of $\{1,...,n\}$ such that
a first slice funciton defined by these $D_1,\ldots,D_n$
has superlinear lower bounds
under some topological restrictions.
TR95-0004
Inducing complex recursive programs from small number of sparse
examples
Chowdhury Rahman Mofizur
and Masayuki Numao
Contact person
write to Chowdhury Rahman Mofizur
(rahman@cs.titech.ac.jp)
Abstract
Generalization under theta-subsumption is able to induce recursive
definition if and only if basic representative set (BRS) is included in the
training set. To provide this set, information is required about the
target recursive theory which is yet to be learnt . Recently
generalization under
inverse implication has been attempted to
eliminate the necessity of the BRS, but either requires a weaker prior
knowledge about the target theory or is limited to
learning very simple recursive scheme. This paper proposes a method capable of
learning more complex recursive theories from a small
number of examples all lying in non-intersecting resolution path and
involving different constants. In effect, we introduce a new top-down ILP
system
SMART which incorporates a novel technique to learn part of the theory
(base clause) and
the learnt theory replaces the requirement of the BRS
to learn the rest of the theory (recursive clause).
TR95-0005
A construction method for fault-tolerant CAM
Tsuyoshi Tanaka
and Eiji Fujiwara
Contact person
write to Eiji Fujiwara
(fujiwara@cs.titech.ac.jp)
Abstract
This paper proposes novel fault-tolerant techniques for CAMs (content
addressable memories) which consist of the following four techniques:
the horizontal-vertical parity coding technique which detects and corrects
single errors implemented by taking odd parity horizontally and even parity
vertically in each CAM cell array block, the faulty-hit checking technique
which checks faulty-hit errors by taking EXOR sum operation of the odd parity
codewords in CAM cell arrays, the write-data checking technique which checks
whether or not correct data can be written in CAM cells by performing search
operation with using written data, the mask checking technique which checks
faulty-miss errors by searching CAM cell arrays with using all masked data.
The proposed fault-tolerant CAM can be constructed with 2.43 times transistor
augmentation, which equals 70.5 \ of that of the existing technique,
compared to the non-fault-tolerant CAM and can detect 90.9 \ single
transistor faults and 97.2 \ line faults.
TR95-0006
A class of optimal fixed-byte error protection codes for computer systems
Eiji Fujiwara
and Masato Kitakami
Contact person
write to Eiji Fujiwara
(fujiwara@cs.titech.ac.jp)
Abstract
Error control codes are now successfully applied to computer systems,
especially to memory systems. This paper proposes a new class of error control
codes to protect the fixed-byte in computer words from errors. The fixed-byte
stores valuable and important information such as control and address
information in communication messages or pointer information in database words.
Here, fixed-byte means the clustered information digits in the word whose
position is determined in advance.
As a simple class of these unequal error protection codes, this paper
proposes two types of optimal fixed-byte error protection codes: single-bit
error correction and fixed b-bit byte error correction (SEC-FbEC) codes and
single-bit error correction, double-bit error detection, and fixed b-bit byte
error detection (SEC-DED-FbED) codes. The obtained optimal SEC-FbEC codes
where byte length b=7 bits and information length k=64 bits, for example,
require check-bit length of only 8 bits which is the same as that of the
conventional SEC-DED codes with k=64 bits.
TR95-0007
Gracefully degrading systems using the bulk-synchronous parallel model
with randomised shared memory
Andreas Savva
and Takashi Nanya
Contact person
write to Takashi Nanya
(nanya@cs.titech.ac.jp)
Abstract
The Bulk-Synchronous Parallel Model, BSPM, was proposed as a bridging model
for parallel computation by Valiant. By using Randomised Shared Memory, RSM,
this model offers an asymptotically optimal emulation of the
PRAM.
By using the BSPM with RSM, we show how a gracefully degrading massively
parallel system can be obtained through: memory duplication to ensure global
memory integrity, and to speed up the reconfiguration; a global
reconfiguration method that restores the logical properties of the system,
after a fault occurs. We assume fail-stop processors, single faults, no
spare processors, and no significant loss of network throughput as a result
of faults.
Work done during reconfiguration is shared equally among the live
processors, with minimal coordination. The overhead of the scheme and the
graceful degradation achieved depend on the program being executed.
We evaluate the reconfiguration, overhead, and graceful degradation of the
system experimentally.
TR95-0008
Towards totally self-checking delay-insensitive systems
Stanislaw J. Piestrak
and Takashi Nanya
Contact person
write to Takashi Nanya
(nanya@cs.titech.ac.jp)
Abstract
This paper considers designing quasi-delay-insensitive (QDI) combinational
circuits (CC's), a class of self-timed (asynchronous) circuits. The
necessity of encoding both inputs and outputs of any QDI CC by using
unordered codes naturally leads to inverter-free (IF) realization. The
analysis of behavior of a QDI CC with input errors leads to the observation
that it is impossible to avoid the so called late detection problem. The
new set of correct definitions of code-disjoint QDI CC is introduced. The
detailed analysis of the behavior of a faulty QDI system with internal
permanent faults shows that: 1) late detection, 2) possibility of
occurrence of invalid transitions,
and 3) premature completion, seem to be the inherent properties of any QDI
CC, which preclude its fault-secure (hence TSC) implementation for some
single stuck-at faults. The first ever self-testing code-disjoint
completion checker is proposed. Finally, an extensive study of designing
self-testing code-disjoint QDI CC's is presented.
TR95-0009
On transient fault masking for asynchronous systems
B.Ravi Kishore
and Takashi Nanya
Contact person
write to Takashi Nanya
(nanya@cs.titech.ac.jp)
Abstract
Protection of asynchronous systems aginst the transient faults is important
due to reactive nature of such systems. This paper presents a new
methodology for the protection of Quasi-Delay-Insensitive (QDI) circuits
for transient faults. The main contributions of this paper are (1) design
of a fault masking mechanism for the transient faults occuring in the
environment and (2) proposal for a fail-stop design aginst excessively
large delays in the environment occuring due to the performance
degradation. The proposed methodology is demonstrated on a QDI
microprocessor, TITAC. The methodology is aimed at attaining a trade off
between the reliability and the performance of the processor. The decision
about the timing parameters for fault masking and fail-stop mechanism is
made based on the local control and data-path conditions. The proposed
mechanism is integrated with the system for which it is intended. This
results in an implementation with transient fault protection, yet
preserving the performance. This methodology provides a systematic frame
work for exploring different implementations of self-checking /
fault-tolerant QDI systems.
TR95-0010
Automatic synthesis of speed-independent circuits from signal transition
graph specifications
Sung-Bum Park
and Takashi Nanya
Contact person
write to Takashi Nanya
(nanya@cs.titech.ac.jp)
Abstract
We propose a verification method of the complete state coding property for
signal transition graph specifications having single cycle signals. We
also propose a logic synthesis and optimization method for generating
asynchronous circuits from the specifications without using state graph
representations. The resulting logic circuit is mainly composed of
C-elements and AND-gates, and is hazard-free. It can be optimized under
certain constraints.
TR95-0011
On Boolean Shifting Networks
Tatsuie Tsukiji
Contact person
write to Tatsuie Tsukiji
(tsukiji@cs.titech.ac.jp)
Abstract
In this paper,
we prove that a Boolean $k$-depth shifter requires
$\Omega(n^{1+1/k})$ size complexity,
which is close to $\Omega(kn^{1+1/k})$
in communication complexity.
We also propose a restriction
which distinguishes addition and multiplication
in circuit complexity.
TR95-0012
Randomized approximation of constraint satisfaction and stable cut
Hoong Chuin Lau
Contact person
write to Hoong Chuin Lau
(hclau@cs.titech.ac.jp)
Abstract
We consider the
Weighted Constraint Satisfaction Problem (W-CSP) in artificial intelligence.
W-CSP is defined by a set of variables, their domains and a set
of binary relations (constraints) between variables.
The objective is to obtain
an assignment of domain values to the variables such that
the weighted sum of satisfied constraints is maximized.
In this paper, we investigate the approximation of W-CSP in terms
of two parameters, the largest domain size $k$ and the
strength of the constraints $s$.
The basic algorithmic tool we employ is
the randomized rounding technique of Raghavan and Thompson.
First, by a greedy method based on the method of conditional
probabilities, we obtain an approximation ratio of $s$.
Next, we represent W-CSP as a linear integer program and
apply randomized rounding to its linear programming relaxation.
We show that the worst-case performance can be arbitrarily bad.
However, by simple modifications to the randomized rounding procedure,
we obtain a ratio of $\frac{1}{2k}+\frac{s}{4}$, which can be improved
to $\frac{1}{k}$ if the instances are satisfiable.
Finally, we represent W-CSP as a quadratic integer program and
apply randomized rounding to its semidefinite relaxation.
Inspired by the recent work of Goemans and Williamson,
we show that W-CSP
can be approximated within a constant ratio of 0.408....
As a corollary to our results,
we consider a generalization of the MAX $k$-CUT problem
and give, to our knowledge, the first known approximation ratios.
TR95-0013
Optimal byte error protection codes with SEC-DED capabilities
Masato Kitakami,
Masayuki Shimizu,
Tepparit Ritthongpitak ,
and Eiji Fujiwara
Contact person
write to Eiji Fujiwara
(fujiwara@cs.titech.ac.jp)
Abstract
In many computer words, there exist a part which includes pointer information,
address information, or control information. We call this part as a
fixed-byte, which can be regarded as more important than the other in the
word. This is because errors in this part cause serious damage to the
subsequent processes. This paper proposes two types of fixed-byte error
protection codes, i.e., the codes with the function of fixed-byte error
correction and SEC-DED, or SEC-DED-FbEC codes, and the codes with the function
of simultaneous correction of single-bit errors and fixed-byte errors, or
(S+Fb)EC codes. This clarifies the bounds on code length, the code
construction of the optimal codes, and the decoding methods for both types of
codes. Computer simulation says that the proposed codes protect the fixed-byte
strongly for the errors which are beyond the original error
correction/detection capabilities of the codes.
TR95-0014
Eliminating selectors from term rewriting systems (part2)
Yutaka Kikuchi
Contact person
write to Yutaka Kikuchi
(kikuchi@cs.titech.ac.jp)
Abstract
Function symbols of term rewriting systems (TRSs) can be
classified into three categories,
namely, constructors, selectors, and defined operators
in terms of functional programming.
The selectors are for convenience of programming
and efficient execution of programs,
so the constructors and the defined operators are sufficient to construct
data structures and to manipulate them.
We give a transformation method to eliminate selectors from a TRS.
We also introduce a new model of TRSs
from the viewpoint of functional programming,
and show that an original TRS and the transformed TRS
have the almost same model except trivial differences.
The transformation method preserves strong termination property.
Although the methods do not preserve weak terminating and confluency,
we turn out sufficient conditions to keep those properties.
The paper is written in Japanese.
TR95-0015
Hierarchical bayesian clustering for automatic text classification
Makoto Iwayama
and Takenobu Tokunaga
Contact person
write to Takenobu Tokunaga
(take@cs.titech.ac.jp)
Abstract
Text classification, the grouping of texts into several clusters, has
been used as a means of improving both the efficiency and the
effectiveness of text retrieval/categorization. In this paper we
propose a hierarchical clustering algorithm that constructs a set of
clusters having the maximum Bayesian posterior probability, the
probability that the given texts are classified into clusters. We call
the algorithm Hierarchical Bayesian Clustering (HBC). The advantages
of HBC are experimentally verified from several viewpoints. (1) HBC
can re-construct the original clusters more accurately than do other
non probabilistic algorithms. (2) When a probabilistic text
categorization is extended to a cluster-based one, the use of HBC
offers better performance than does the use of non probabilistic
algorithms.
TR95-0016
Cluster-based text categorization:
A comparison of category search strategies
Makoto Iwayama
and Takenobu Tokunaga
Contact person
write to Takenobu Tokunaga
(take@cs.titech.ac.jp)
Abstract
Text categorization can be viewed as a process of category search, in
which one or more categories for a test document are searched for by
using given training documents with known categories. In this paper a
cluster-based search with a probabilistic clustering algorithm is
proposed and evaluated on two data sets. The efficiency,
effectiveness, and noise tolerance of this search strategy were
confirmed to be better than those of a full search, a category-based
search, and a cluster-based search with nonprobabilistic clustering.
TR95-0017
Application of distributed system-level diagnosis for SNMP-based internet
fault management
Elias Procopio Duarte Jr.
and Takashi Nanya
Contact person
write to Takashi Nanya
(nanya@cs.titech.ac.jp)
Abstract
Fault Management is a key functional area of Network Management Systems,
but current SNMP-based applications often implement rudimentary diagnosis
mechanisms. Although the field of Distributed System-Level Fault Diagnosis
has been flourishing for years, and a large number of mostly theoretical
results have been devised, these results are not yet widely applied to
network
management systems.
In this paper we describe a new approach for heterogeneous internet
management diagnosis based on distributed diagnosis. This approach
recognizes both the advantages of distributed diagnosis and that its basic
goal differs from the network management goal of centralized reliable
diagnosis at the Network Management Station (NMS), which does not tolerate
large diagnosis delays. The network is divided in clusters, each of which
executing a modified implementation of the Adaptive Distributed
System-level Diagnosis (Adaptive-DSD) algorithm within an SNMP-based
Network Management System. All clusters intersect at one or more nodes
which may be deployed as NMS. Moreover, the algorithm provides NMS
fault-tolerance, through which the nodes automatically elect a new NMS if
the current one fails or gets unreachable. The impact of the diagnosis
messages on the performance of the network is presented in terms of the
overhead imposed by diagnosis messages, and it is shown hat for popular LAN
data transfer rates, diagnosis demands less than 1 of the available
bandwidth. A prototype was implemented, and results of the experimentation
are presented, including the diagnosis MIB for SNMP.
TR95-0018
Some lower bounds
for Boolean shifting networks
Tatsuie Tsukiji
Contact person
write to Tatsuie Tsukiji
(tsukiji@cs.titech.ac.jp)
Abstract
Considering some restrictions on underlying graphs of Boolean
circuits, we show that the difference between addition and
multiplication complexities; that is, we show that addition is
computed by a liner size and logarithmic depth Boolean circuit,
whereas multiplication circuits must have nonlinear size. The results
are obtained by showing lower bounds on Boolean shifting networks.
TR95-0019
Randomized approximation of constraint satisfaction and stable cut
(improved version)
Hoong Chuin Lau
and Osamu Watanabe
Contact person
write to Hoong Chuin Lau
(hclau@cs.titech.ac.jp)
Abstract
We consider the
Weighted Constraint Satisfaction Problem (W-CSP)
which is a central problem in Artificial Intelligence.
A W-CSP instance is defined by a set of variables, their domains
and a set of constraints between variables.
The objective is to obtain
an assignment of the variables to domain values such that
the weighted sum of satisfied constraints is maximized.
W-CSP is a generalization of MAX CUT and MAX SAT.
In this paper, we show that W-CSP cannot be approximated within
a constant factor unless {\rm EXP=NEXP}.
We then give improved approximations of W-CSP
via randomized rounding of
linear programming and semidefinite programming relaxations.
Our algorithms are simple and efficient in practice.
As a corollary, we establish approximation for
the Stable Max-Cut, which is
a generalization of the MAX CUT problem.
TR95-0020
On formalization of object oriented attribute grammars OOAG
and higher order attribute grammars using record calculus
Katsuhiko Gondow
and Takuya Katayama
Contact person
write to Katsuhiko Gondow
(gondow @cs.titech.ac.jp)
Abstract
The purpose of this paper is twofold. First we present a
denotational semantics of attribute grammars(AGs) by using Cardelli's
record calculus. The denotational semantics is simple and natural.
In our semantics, an attributed tree is represented by nested records
to preserve the structural information of the attributed tree, while
in traditional denotational semantics AGs are formalized by either
valuation mapping from attributes (often in the root) to their values
or mapping from inherited attributes to synthesized attributes in the
root. It is a positive characteristic of our semantics to deal with
attributed tree as AG's semantics rather than attribute valuation.
For the purpose of describing structure-oriented software development
environments, many computational models based on AGs have already been
proposed. These computational models are usually extended so as to
deal with tree transformation. We believe that our semantics can be a
good formal basis to define these computational models.
To show this, we formalize OOAG(Object-Oriented AGs) and higher order
AGs(HAGs) by extending our denotational semantics of AGs. This is the
second purpose of this paper. Both of them are computational models
to deal with tree transformation depending upon attribute values. As
the result of these formalizations, we can formally discuss the
differences between OOAG and HAGs. For example, we show that tree
transformation in OOAG is modeled as a function to determine the next
state, while that in HAGs is just a static tree construction.
This paper is the revised English version of "Attribute Grammars as
Record Calculus" (Technical Report No.93TR-0047), which is written
in Japanese.
TR95-0021
Exact learning of subclasses of cdnf formulas with membership queries
Carlos Domingo
Contact person
write to Carlos Domingo
(carlos@cs.titech.ac.jp)
Abstract
We consider the exact learnability of subclasses of Boolean
formulas from membership queries alone. We show how to combine known learning
algorithms that use membership and equivalence queries to obtain new learning
results only with memberships. In particular we show the exact learnability of
read-$k$ monotone formulas, decision trees and ${\cal O}(\sqrt{\log
n})\mbox{-term DNF} \cap {\cal O}(\sqrt{ \log n})\mbox{-clause CNF}$ from
membership queries only. One of our results uses a new characterization of
self-dual formulas in terms of its Fourier spectrum. This
result may be of independent interest due to the importance of the duality
problem.
TR95-0022
Efficient multiple predicate learner
based on fast failure mechanism
Xiaolong Zhang
and Masayuki Numao
Contact person
write to Xiaolong Zhang
(zxl@cs.titech.ac.jp)
Abstract
We propose a multiple predicate learner (MPL-Core) which can efficiently
induce some Horn clauses from example sets of multiple predicates and
relative background knowledge. Our system is based on Core, a single
predicate learning (SPL) module with complete
refinement operators and efficient failure-recovery ability. Core
selects refinement operators based on the learning task. With
complete refinement operators, Core learns some predicates which are
not learned by previous system such as CHAM.
By means of a pruning method, GPC, our
system can effectively prune unpromising branches in search tree,
making the search space a rational volume. Some relevant factors
which do not appear to be so important in SPL (mode declaration of
targets, the method to add background
knowledge and the learning order etc) are taken into account in
MPL. Combining the intensional and extensional learning styles,
our system induces correct results from multiple learning task in
which the constants of examples in different target predicates may
come from different value ranges.