TR92-0001
Design of fully exercised SFS/SCD logic networks
Takashi Nanya, Shin'ichi Hatakenaka and Ryuichi Onoo
Contact person Takashi Nanya (nanya@cs.titech.ac.jp)
Abstract
A key assumption which most self-checking circuit designs are based
on is that all the codeword inputs are applied to the circuit, i.e. the
input of the circuit is fully exercised, in normal operation. This
assumption may, however, be invalidated for circuits embedded in a large
logic network. This paper contributes two important design techniques to
the realization of a large logic network that effectively achieves the
totally self-checking goal. First, a systematic design method is
presented for strongly fault-secure (SFS) and strongly code-disjoint (SCD)
sequential circuits which can be used as embedded circuits with the inputs
having no need to be monitored by any checker. Second, a remapping
technique is presented for embedded logic functions of combinational and
sequential circuits interconnected in cascade. The technique allows the
embedded input interface of each component circuit to be fully exercised in
normal operation so that the entire logic network proves to be SFS and SCD.
TR92-0002
Predicate invention based on discrimination
Boonserm Kijsirikul, Masayuki Numao and Masamichi Shimura
Contact person Masayuki Numao (numao@cs.titech.ac.jp)
Abstract
TR92-0003
A framework for polynomial time query learnability
Osamu Watanabe
Contact person Osamu Watanabe (watanabe@cs.titech.ac.jp)
Abstract
TR92-0004
Structural analysis of polynomial time query learnability
Osamu Watanabe and Richard Gavald\`{a}
Contact person Osamu Watanabe (watanabe@cs.titech.ac.jp)
Abstract
TR92-0005
Computational and statistical indistinguishabilities
Kaoru Kurosawa and Osamu Watanabe
Contact person Osamu Watanabe (watanabe@cs.titech.ac.jp)
Abstract
TR92-0006
Challenges to dependable asynchronous processor design
Takashi Nanya
Contact person Takashi Nanya (nanya@cs.titech.ac.jp)
Abstract
TR92-0007
Fault injection for the experimental validation of fault-tolerant systems
Jean Arlat
Contact person Takashi Nanya (nanya@cs.titech.ac.jp)
Abstract
TR92-0008
On signal transition causality for self-timed implementation of
Boolean functions
Takashi Nanya and Masashi Kuwako
Contact person Takashi Nanya (nanya@cs.titech.ac.jp)
Abstract
we discuss on the 2-rail 2-phase self-timed implementation of Boolean
functions which interacts with its environment on the
delay-insensitive model with the isochronic-forks assumption. We
first define the transition causality of a self-timed implementation
as a set of causal relations that hold among signal transitions on the
primary input, primary output and the internal gates. We observe that
the transition causalities for most self-timed implementations so far
proposed are more than what is truly required. Then, based on the
observation, we present a new self-timed implementation of Boolean
functions. The resulting circuit achieves a maximum parallelism, and
consequently, has a potential of operating at a highest possible
average speed on the delay-insensitive circuit-environment model.
TR92-0009
A note on the query complexity of learnig DFA
Jos\'{e} L.\ Balcaz\'{a}r, Josep D{\'\i}az, Ricard Gavald\`{a} and
Osamu Watanabe
Contact person Osamu Watanabe (watanabe@cs.titech.ac.jp)
Abstract
TR92-0010
The determination of parameters of hyper-geometric distribution model
for debugging process
Yoshihiro Tohma, Soichiro Tajima and Yukichi Matsunaga
Contact person Yoshihiro Tohma (tohma@cs.titech.ac.jp)
Abstract
TR92-0011
Text revision: A model and its implementation
Kentaro Inui, Takenobu Tokunaga and Hozumi Tanaka
Contact person Takenobu Tokunaga (take@cs.titech.ac.jp)
Abstract
To generate good text, many kinds of decisions should be made. Many
researchers have spent much time searching for the architecture that
would determine a proper order for these decisions. However, even if
such an architecture is found, there are still certain kinds of
problems that are difficult to consider during the generation process.
Those problems can be more easily detected and solved by introducing a
revision process after generation. In this paper, we argue the
importance of text revision with respect to natural language
generation, and propose a computational model of text revision. We
also discuss its implementation issues and describe an experimental
Japanese text generation system, weiveR.
TR92-0012
Implementation and evaluation of yet another generalized LR parsing
algorithm
K.G. Suresh and Hozumi Tanaka
Contact person Hozumi Tanaka (tanaka@cs.titech.ac.jp)
Abstract
We present an implementation and evaluation of our new generalized LR
parsing algorithm called Yet Another Generalized LR parsing algorithm
(YAGLR). In our implementation we used tree-structured stack and the
logic programming language Prolog. The merge operation of stacks in
our algorithm advances inner to the top nodes effectively and
efficiently. Hence the parsing time and the reduction in memory space
are remarkable. Due to effective merge operations and due to the
shared-structure machanism of Prolog, even when using treee-structured
stack, we retain packed nature of GSS. We introduce an item called dot
reverse items, which are created during the parsing and represents
partially parsed results. These dot reverse items are symmetrically
different from Earley's item and the advantages in creating them
during parsing are realized and proved. Through our implementation, we
practically prove that for a context-free grammar with reasonable size
and complexity, YAGLR's parsing time is in the order of $n^{3}$, where
$n$ is the length of an input sentence. We conclude that YAGLR has the
advantages of both Earley's and Tomita's algorithm.
TR92-0013
A design method for cost-effective self-testing checker for
optimal d-unidirectional error detecting codes
Eiji Fujiwara and Masakatsu Yoshikawa
Contact person Eiji Fujiwara (fujiwara@cs.titech.ac.jp)
Abstract
TR92-0014
Single b-bit byte error correcting and double bit error detecting
codes for high-speed memory systems
Eiji Fujiwara and Mitsuru Hamada
Contact person Eiji Fujiwara (fujiwara@cs.titech.ac.jp)
Abstract
TR92-0015
Single byte unidirectional error locating codes
Eiji Fujiwara and Shuxin Jiang
Contact person Eiji Fujiwara (fujiwara@cs.titech.ac.jp)
Abstract
TR92-0016
A class of byte error control codes for memory systems
-- SbEC-(Sb+S)ED codes --
Mitsuru Hamada and Eiji Fujiwara
Contact person Eiji Fujiwara (fujiwara@cs.titech.ac.jp)
Abstract
TR92-0017
A generalized marching test for detecting pattern sensitive faults
in RAMs
Masahiro Hashimoto and Eiji Fujiwara
Contact person Eiji Fujiwara(fujiwara@cs.titech.ac.jp)
Abstract
TR92-0018
Complicated paradigm of responsive systems
Yoshihiro Tohma
Contact person Yoshihiro Tohma (tohma@cs.titech.ac.jp)
Abstract
Questions related to responsive systems will be argued. This argument
hopefully help us deepen the insight where problems reside and how
these are difficult.
TR92-0019
A Family of generalized lr parsing algorithms using ancestors table
Hozumi Tanaka, K.G. Suresh and Koiti Yamada
Contact person Hozumi Tanaka (tanaka@cs.titech.ac.jp)
Abstract
A family of new generalized LR parsing algorithms are proposed which
make use of a set of ancestors tables introduced by Kipps [5]. As
Kipps's algorithm does not give us a method to extract any parsing
results, his algorithm is not considered as a practical parsing
algorithm but as a recognition algorithm [8]. In this paper, we will
propose a few of methods to extract all parsing trees from a set of
ancestors tables in the top vertices of a graph-structured stack. For
an input sentence of length n, while the time complexity of Tomita's
parsing algorithm can exceed O(n$^{3}$) for some context-free grammars
(CFGs), the time complexity of our parsing algorithm is in the order
of n$^{3}$ for any CFGs, since our algorithm is based on the Kipps's
recognition algorithm. In order to extract a parsing tree from a set
of ancestors tables, it takes time in the order of n$^{2}$. However,
by making small modifications in the ancestors table, it is possible
to extract a parsing tree in the order of n. A preliminary experiment
suggests our parsing algorithm seems to be very promising.
TR92-0020
Byte error locating codes
Eiji Fujiwara
Contact person Eiji Fujiwara (fujiwara@cs.titech.ac.jp)
Abstract
TR92-0021
Necessary and sufficient conditions for byte unidirectional error
locating codes
Shuxin Jiang and Eiji Fujiwara
Contact person Eiji Fujiwara (fujiwara@cs.titech.ac.jp)
Abstract
TR92-0022
On closure properties of #P in the context of PF o #P
Mistunori Ogiwara, Thomas Thierauf, Seinosuke Toda and Osamu Watanabe
Contact person Osamu Watanabe (watanabe@cs.titech.ac.jp)
Abstract
TR92-0023
A class of error locating codes for byte-organized memory systems
Eiji Fujiwara and Masato Kitakami
Contact person Eiji Fujiwara (fujiwara@cs.titech.ac.jp)
Abstract