Setsuo Arikawa

TCS Journal 2003 Journal Article

A practical algorithm to find the best subsequence patterns

• Masahiro Hirao
• Hiromasa Hoshino
• Ayumi Shinohara
• Masayuki Takeda
• Setsuo Arikawa

Given two sets of strings, consider the problem to find a subsequence that is common to one set but never appears in the other set. We regard it to find a subsequence pattern which separates these two sets. The problem is known to be NP-complete. We naturally generalize it to an optimization problem, where we try to find a subsequence pattern which maximally separates these two sets. We provide a practical algorithm to solve it exactly. Our algorithm uses two pruning heuristics based on the properties of subsequence languages, and utilizes the data structure called subsequence automata. We report some experimental results, which show these heuristics and the data structure contribute to reduce the search time.

TCS Journal 2003 Journal Article

Collage system: a unifying framework for compressed pattern matching

• Takuya Kida
• Tetsuya Matsumoto
• Yusuke Shibata
• Masayuki Takeda
• Ayumi Shinohara
• Setsuo Arikawa

We introduce a general framework which is suitable to capture the essence of compressed pattern matching according to various dictionary-based compressions. It is a formal system to represent a string by a pair of dictionary D and sequence S of phrases in D. The basic operations are concatenation, truncation, and repetition. We also propose a compressed pattern matching algorithm for the framework. The goal is to find all occurrences of a pattern in a text without decompression, which is one of the most active topics in string matching. Our framework includes such compression methods as Lempel–Ziv family (LZ77, LZSS, LZ78, LZW), RE-PAIR, SEQUITUR, and the static dictionary-based method. The proposed algorithm runs in O((||D||+|S|)·height(D)+m2+r) time with O(||D||+m2) space, where ||D|| is the size of D, |S| is the number of tokens in S, height(D) is the maximum dependency of tokens in D, m is the pattern length, and r is the number of pattern occurrences. For a subclass of the framework that contains no truncation, the time complexity is O(||D||+|S|+m2+r).

MFCS Conference 2002 Conference Paper

Space-Economical Construction of Index Structures for All Suffixes of a String

• Shunsuke Inenaga
• Ayumi Shinohara
• Masayuki Takeda
• Hideo Bannai
• Setsuo Arikawa

Abstract The minimum all-suffixes directed acyclic word graph (MASDAWG) of a string w has | w | + 1 initial nodes, where the dag induced by all reachable nodes from the k -th initial node conforms with the DAWG of the k -th suffix of w. A new space-economical algorithm for the construction of MASDAWG(w) is presented. The algorithm reads a given string w from right to left, and constructs MASDAWG(w) without suffix links. It performs in time linear in the output size. Furthermore, we introduce the minimum all-suffixes compact DAWG (MASCDAWG). CDAWGts are known to be more space-economical than DAWGs, and thus MASCDAWG(w) requires smaller space than MASDAWG(w). We present an on-line (right-to-left) algorithm to build MASCDAWG(w) without suffix links, whose running time is also linear in its size.

TCS Journal 2001 Journal Article

A comparison of identification criteria for inductive inference of recursive real-valued functions

• Eiju Hirowatari
• Setsuo Arikawa

In this paper we investigate the inductive inference of recursive real-valued functions from data. A recursive real-valued function is regarded as a computable interval mapping. The learning model we consider in this paper is an extension of Gold's inductive inference. We first introduce some criteria for successful inductive inference of recursive real-valued functions. Then we show a recursively enumerable class of recursive real-valued functions which is not inferable in the limit. This should be an interesting contrast to the result by Wiehagen (1976, Elektronische Informationsverarbeitung und Kybernetik, Vol. 12, pp. 93–99) that every recursively enumerable subset of recursive functions from N to N is consistently inferable in the limit. We also show that every recursively enumerable class of recursive real-valued functions on a fixed rational interval is consistently inferable in the limit. Furthermore, we show that our consistent inductive inference coincides with the ordinary inductive inference, when we deal with recursive real-valued functions on a fixed closed rational interval.

TCS Journal 1999 Journal Article

On the inductive inference of recursive real-valued functions

• Kalvis Apsītis
• Setsuo Arikawa
• Rũsiņš Freivalds
• Eiju Hirowatari
• Carl H. Smith

We combine traditional studies of inductive inference and classical continuous mathematics to produce a study of learning real-valued functions. We consider two possible ways to model the learning by example of functions with domain and range the real numbers. The first approach considers functions as represented by computable analytic functions. The second considers arbitrary computable functions of recursive real numbers. In each case we find natural examples of learnable classes of functions and unlearnable classes of functions.

TCS Journal 1995 Journal Article

Towards a mathematical theory of machine discovery from facts

• Yasuhito Mukouchi
• Setsuo Arikawa

This paper intends to give a theoretical foundation of machine discovery from facts. We point out that the essence of a computational logic of scientific discovery or a logic of machine discovery is the refutability of the entire spaces of hypotheses. We discuss this issue in the framework of inductive inference of length-bounded elementary formal systems (EFSs), which are a kind of logic programs over strings of characters and correspond to context-sensitive grammars in Chomsky hierarchy. First we present some characterization theorems on inductive inference machines that can refute hypothesis spaces. Then we show differences between our inductive inference and some other related inferences such as in the criteria of reliable identification, finite identification and identification in the limit. Finally we show that for any n, the class, i. e. hypothesis space, of length-bounded EFSs with at most n axioms is inferable in our sense, that is, the class is refutable by a consistently working inductive inference machine. This means that sufficiently large hypothesis spaces are identifiable and refutable.

TCS Journal 1992 Journal Article

Learning elementary formal system

• Setsuo Arikawa
• Takeshi Shinohara
• Akihiro Yamamoto

The elementary formal systems (EFS for short) Smullyan invented to develop his recursive function theory, are proved suitable to generate languages. In this paper we first point out that EFS can also work as a logic programming language, and the resolution procedure for EFS can be used to accept languages. We give a theoretical foundation to EFS from the viewpoint of semantics of logic programs. Hence, Shapiro's theory of model inference can naturally be applied to our language learning by EFS. We introduce some subclasses of EFS's with correspond to Chomsky hierarchy and other important classes of languages. We discuss computations of unifiers between two terms. Then we give inductive inference algorithms including refinement operators for these subclasses and show their completeness.

TCS Journal 1990 Journal Article

Preface

• Koichi Furukawa
• Setsuo Arikawa