TOHOKU UNIVERSITY Researchers

Details of the Researcher

Home

日本語 English

Ayumi Shinohara

Section

Graduate School of Information Sciences

Job title

Professor

Degree

博士（理学）九州大学

researchmap

https://researchmap.jp/read0121310

J-GLOBAL ID

200901055094177640

Research History 5

2005/03 - Present

Graduate School of Information Sciences, Tohoku University　教授
2000/04 - 2005/02

Graduate School of Information Science and Electrical Engineering, Kyushu Univeristy　助教授
1996/04 - 2000/03

Graduate School of Information Science and Electrical Engineering, Kyushu University　助教授
1994/10 - 1996/03

Faculty of Science, Kyushu University　助教授
1990/04 - 1994/09

Faculty of Science, Kyushu University　助手

Education 2

Kyushu University　Graduate School, Division of Integrated Science and Engineering　Information System

1988/04 - 1990/03
Kyushu University　Faculty of Science　Department of Mathematics

1984/04 - 1988/03

Committee Memberships 34

Member of Program Commitee of CPM2017　Program Commitee

2017/01 - 2017/07
国際会議CPM2017 プログラム委員　プログラム委員

2017/01 - 2017/07
Member of Program Commitee of LATA2015　Program Commitee

2014/10 - 2015/03
国際会議LATA2015 プログラム委員　プログラム委員

2014/10 - 2015/03
Member of Program Commitee of LATA2011　Program Commitee

2010/10 - 2011/03
国際会議LATA2011 プログラム委員　プログラム委員

2010/10 - 2011/03
電子情報通信学会コンピュテーション研究専門委員会　委員

2003/04 - 2009/05
電子情報通信学会コンピュテーション研究専門委員会　委員

2003/04 - 2009/05
The 10th International Conference on Discovery Science　Conference Chair

2006/11 - 2007/10
The 10th International Conference on Discovery Science　Conference Chair

2006/11 - 2007/10
Member of Program Commitee of CPM2006　プログラム委員

2006/01 - 2006/07
国際会議CPM2006 プログラム委員　プログラム委員

2006/01 - 2006/07
Member of Program Commitee of SPIRE2005　プログラム委員

2005/04 - 2005/10
国際会議SPIRE2005 プログラム委員　プログラム委員

2005/04 - 2005/10
Member of Program Commitee of ALT2004　プログラム委員

2004/04 - 2004/11
国際会議ALT2004 プログラム委員　プログラム委員

2004/04 - 2004/11
Member of Program Commitee of SPIRE2004　プログラム委員

2004/04 - 2004/10
国際会議SPIRE2004 プログラム委員　プログラム委員

2004/04 - 2004/10
Member of Program Commitee of SPIRE2003　プログラム委員

2003/04 - 2003/10
国際会議SPIRE2003 プログラム委員　プログラム委員

2003/04 - 2003/10
Member of Program Commitee of CPM2003　プログラム委員

2003/01 - 2003/07
国際会議CPM2003 プログラム委員　プログラム委員

2003/01 - 2003/07
Member of Program Commitee of DS2002　プログラム委員

2002/04 - 2002/11
国際会議DS2002 プログラム委員　プログラム委員

2002/04 - 2002/11
Member of Program Commitee of SPIRE2002　プログラム委員

2002/04 - 2002/10
国際会議SPIRE2002 プログラム委員　プログラム委員

2002/04 - 2002/10
Co-chair of Program Commitee of DS2001　プログラム委員

2001/04 - 2001/11
国際会議DS2001 プログラム副委員長　プログラム委員

2001/04 - 2001/11
Member of Program Commitee of DS2000　プログラム委員

2000/04 - 2000/11
国際会議DS2000 プログラム委員　プログラム委員

2000/04 - 2000/11
Member of Program Commitee of ALT'99　プログラム委員

1999/04 - 1999/11
国際会議ALT'99 プログラム委員　プログラム委員

1999/04 - 1999/11
Member of Program Commitee of ALT'97　プログラム委員

1997/04 - 1997/11
国際会議ALT'97 プログラム委員　プログラム委員

1997/04 - 1997/11

Show all ︎Show first 5

Professional Memberships 3

日本ソフトウエア科学会
Tha Japanese Society for Artificial Intelligence
Information Processing Society of Japan

Research Interests 3

artificial intelligence
machine learning
string processing algorithms

Research Areas 2

Informatics / Intelligent informatics /
Informatics / Information theory /

Awards 3

2006年度ロボカップ研究賞

2007/03/31　日本ロボカップ委員会
日本ロボット学会最優秀賞

2004/05　日本ロボット学会　ロボカップジャパンオープン2004 大阪４足ロボットリーグ
情報処理学会創立４０周年記念論文賞

2001/10　情報処理学会

Papers 244

Query Learning of Context-Deterministic and Congruential Context-Free Languages over Infinite Alphabets.

Yutaro Numaya, Yoshito Kawasaki, Ryo Yoshinaka, Ayumi Shinohara

SOFSEM (2)　211-224　2025

DOI： 10.1007/978-3-031-82697-9_16 　
Serial and parallel algorithms for order-preserving pattern matching based on the duel-and-sweep paradigm

Davaajav Jargalsaikhan, Diptarama Hendrian, Yohei Ueki, Ryo Yoshinaka, Ayumi Shinohara

Acta Informatica　2024/08/31
Publisher: Springer Science and Business Media LLC
DOI： 10.1007/s00236-024-00464-w 　

ISSN： 0001-5903

eISSN： 1432-0525
Breaking a Barrier in Constructing Compact Indexes for Parameterized Pattern Matching Peer-reviewed

Kento Iseri, Tomohiro I, Diptarama Hendrian, Dominik Köppl, Ryo Yoshinaka, Ayumi Shinohara

Proceedings of the 51st International Colloquium on Automata, Languages and Programming (ICALP 2024)　89:1-89:19　2024/07

DOI： 10.4230/LIPIcs.ICALP.2024.89 　
Algorithms for Galois Words: Detection, Factorization, and Rotation Peer-reviewed

Diptarama Hendrian, Dominik Köppl, Ryo Yoshinaka, Ayumi Shinohara

Proceedings of the 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024)　18:1-18:16　2024/06

DOI： 10.4230/LIPIcs.CPM.2024.18 　
Query Learning of Minimal Deterministic Symbolic Finite Automata Separating Regular Languages

Yoshito Kawasaki, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

Lecture Notes in Computer Science　340-354　2024/02/07
Publisher: Springer Nature Switzerland
DOI： 10.1007/978-3-031-52113-3_24 　

ISSN： 0302-9743

eISSN： 1611-3349
Efficient Parameterized Pattern Matching in Sublinear Space

Haruki Ideguchi, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

String Processing and Information Retrieval　271-283　2023/09/20
Publisher: Springer Nature Switzerland
DOI： 10.1007/978-3-031-43980-3_22 　

ISSN： 0302-9743

eISSN： 1611-3349
Inferring Strings from Position Heaps in Linear Time

Koshiro Kumagai, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

WALCOM: Algorithms and Computation　115-126　2023/03/13
Publisher: Springer Nature Switzerland
DOI： 10.1007/978-3-031-27051-2_11 　

ISSN： 0302-9743

eISSN： 1611-3349
Identification of Substitutable Context-Free Languages over Infinite Alphabets from Positive Data.

Yutaro Numaya, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

International Conference on Grammatical Inference(ICGI)　23-34　2023
Publisher: PMLR
Parameterized DAWGs: Efficient constructions and bidirectional pattern searches

Katsuhito Nakashima, Noriki Fujisato, Diptarama Hendrian, Yuto Nakashima, Ryo Yoshinaka, Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, Masayuki Takeda

Theoretical Computer Science　933　21-42　2022/10
Publisher: Elsevier BV
DOI： 10.1016/j.tcs.2022.09.008 　

ISSN： 0304-3975
Parallel Algorithm for Pattern Matching Problems Under Substring Consistent Equivalence Relations Peer-reviewed

Davaajav Jargalsaikhan, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

Proceedings of the 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)　28:1-28:21　2022/06

DOI： 10.4230/LIPIcs.CPM.2022.28 　
Computing the Parameterized Burrows–Wheeler Transform Online

Daiki Hashimoto, Diptarama Hendrian, Dominik Köppl, Ryo Yoshinaka, Ayumi Shinohara

String Processing and Information Retrieval　70-85　2022
Publisher: Springer International Publishing
DOI： 10.1007/978-3-031-20643-6_6 　

ISSN： 0302-9743

eISSN： 1611-3349
Inside-Outside Algorithm for Macro Grammars.

Ryuta Kambe, Naoki Kobayashi 0001, Ryosuke Sato 0001, Ayumi Shinohara, Ryo Yoshinaka

Proceedings of the 15th International Conference on Grammatical Inference(ICGI)　32-46　2021
Publisher: PMLR
Fast and Linear-Time String Matching Algorithms Based on the Distances of q-Gram Occurrences

Satoshi Kobayashi, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

Leibniz International Proceedings in Informatics, LIPIcs　160　2020/06/01
Publisher: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
DOI： 10.4230/LIPIcs.SEA.2020.13 　

ISSN： 1868-8969
Linear-Time Online Algorithm for Inferring the Shortest Path Graph from a Walk Peer-reviewed

Shintaro Narisada, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

Theoretical Computer Science　812　187-202　2020/04

DOI： 10.1016/j.tcs.2019.10.029 　
Grammar compression with probabilistic context-free grammar

Hiroaki Naganuma, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara, Naoki Kobayashi

Data Compression Conference Proceedings　2020-　386　2020/03/01
Publisher: Institute of Electrical and Electronics Engineers Inc.
DOI： 10.1109/DCC47342.2020.00093 　

ISSN： 1068-0314
AOBA: An Online Benchmark tool for Algorithms in stringology

Ryu Wakimoto, Satoshi Kobayashi, Yuki Igarashi, Davaajav Jargalsaikhan, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

CEUR Workshop Proceedings　2568　1-12　2020
Publisher: CEUR-WS
ISSN： 1613-0073
An extension of linear-size suffix tries for parameterized strings

Katsuhito Nakashima, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

CEUR Workshop Proceedings　2568　97-108　2020
Publisher: CEUR-WS
ISSN： 1613-0073
Parallel duel-and-sweep algorithm for the order-preserving pattern matching Peer-reviewed

Davaajav Jargalsaikhan, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

The 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2020)　211-222　2020/01

DOI： 10.1007/978-3-030-38919-2_18 　
DAWGs for Parameterized Matching: Online Construction and Related Indexing Structures.

Katsuhito Nakashima, Noriki Fujisato, Diptarama Hendrian, Yuto Nakashima, Ryo Yoshinaka, Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, Masayuki Takeda

31st Annual Symposium on Combinatorial Pattern Matching(CPM)　26-14　2020
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
DOI： 10.4230/LIPIcs.CPM.2020.26 　
Detecting k-(Sub-)Cadences and Equidistant Subsequence Occurrences.

Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Ayumi Shinohara

31st Annual Symposium on Combinatorial Pattern Matching(CPM)　12-11　2020
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
DOI： 10.4230/LIPIcs.CPM.2020.12 　
Efficient computation of longest single-arm-gapped palindromes in a string.

Shintaro Narisada, Diptarama Hendrian, Kazuyuki Narisawa, Shunsuke Inenaga, Ayumi Shinohara

Theor. Comput. Sci.　812　160-173　2020

DOI： 10.1016/j.tcs.2019.10.025 　
In-Place Bijective Burrows-Wheeler Transforms.

Dominik Köppl, Daiki Hashimoto, Diptarama Hendrian, Ayumi Shinohara

31st Annual Symposium on Combinatorial Pattern Matching(CPM)　21-15　2020
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
DOI： 10.4230/LIPIcs.CPM.2020.21 　
Computing Covers Under Substring Consistent Equivalence Relations

Natsumi Kikuchi, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

String Processing and Information Retrieval　131-146　2020
Publisher: Springer International Publishing
DOI： 10.1007/978-3-030-59212-7_10 　

ISSN： 0302-9743

eISSN： 1611-3349
Query Learning Algorithm for Residual Symbolic Finite Automata Peer-reviewed

Kaizaburo Chubachi, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

The Tenth International Symposium on Games, Automata, Logics, and Formal Verification, GandALF 2019　140-153　2019/09

DOI： 10.4204/EPTCS.305.10 　
Development of a Lightweight Cyber-enhanced Rescue Canine Suit with Heat Protection and Anti-slip Countermeasures

Hiroyuki Nishinoma, Beokhaimook Chayapol, Kazunori Ohno, Ayumi Shinohara, Satoshi Tadokoro

2019 IEEE International Symposium on Safety, Security, and Rescue Robotics, SSRR 2019　74-80　2019/09

DOI： 10.1109/SSRR.2019.8848938 　
An improvement of the franek-jennings-smyth pattern matching algorithm

Satoshi Kobayashi, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

Proceedings of the Prague Stringology Conference, PSC 2019　56-68　2019/08/26
Publisher: Prague Stringology Club
Permuted Pattern Matching Algorithms on Multi-Track Strings. Peer-reviewed

Diptarama Hendrian, Yohei Ueki, Kazuyuki Narisawa, Ryo Yoshinaka, Ayumi Shinohara

Algorithms　12　(4)　73:1-73:20　2019/04

DOI： 10.3390/a12040073 　
Cyber-enhanced rescue canine

Kazunori Ohno, Ryunosuke Hamada, Tatsuya Hoshi, Hiroyuki Nishinoma, Shumpei Yamaguchi, Solvi Arnold, Kimitoshi Yamazaki, Takefumi Kikusui, Satoko Matsubara, Miho Nagasawa, Takatomi Kubo, Eri Nakahara, Yuki Maruno, Kazushi Ikeda, Toshitaka Yamakawa, Takeshi Tokuyama, Ayumi Shinohara, Ryo Yoshinaka, Diptarama Hendrian, Kaizaburo Chubachi, Satoshi Kobayashi, Katsuhito Nakashima, Hiroaki Naganuma, Ryu Wakimoto, Shu Ishikawa, Tatsuki Miura, Satoshi Tadokoro

Springer Tracts in Advanced Robotics　128　143-193　2019

DOI： 10.1007/978-3-030-05321-5_4 　

ISSN： 1610-7438

eISSN： 1610-742X
Efficient dynamic dictionary matching with DAWGs and AC-automata Peer-reviewed

Diptarama Hendrian, Shunsuke Inenaga, Ryo Yoshinaka, Ayumi Shinohara

Theoretical Computer Science　2018
Publisher: Elsevier B.V.
DOI： 10.1016/j.tcs.2018.04.016 　

ISSN： 0304-3975
Linear-Time Online Algorithm Inferring the Shortest Path from a Walk. Peer-reviewed

Shintaro Narisada, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Lima, Peru, October 9-11, 2018, Proceedings　311-324　2018
Publisher: Springer
DOI： 10.1007/978-3-030-00479-8_25 　
Enumeration of Cryptarithms Using Deterministic Finite Automata. Peer-reviewed

Yuki Nozaki, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

Implementation and Application of Automata - 23rd International Conference, CIAA 2018, Charlottetown, PE, Canada, July 30 - August 2, 2018, Proceedings　286-298　2018
Publisher: Springer
DOI： 10.1007/978-3-319-94812-6_24 　
Duel and sweep algorithm for order-preserving pattern matching Peer-reviewed

Davaajav Jargalsaikhan, Diptarama, Yohei Ueki, Ryo Yoshinaka, Ayumi Shinohara

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　10706　624-635　2018
Publisher: Springer Verlag
DOI： 10.1007/978-3-319-73117-9_44 　

ISSN： 1611-3349 0302-9743
New variants of pattern matching with constants and variables Peer-reviewed

Yuki Igarashi, Diptarama, Ryo Yoshinaka, Ayumi Shinohara

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　10706　611-623　2018
Publisher: Springer Verlag
DOI： 10.1007/978-3-319-73117-9_43 　

ISSN： 1611-3349 0302-9743
Renewal of the Major Fields from New Generation Computing Vol. 36 (2018). Peer-reviewed

Masayuki Numao, Yutaka Matsuo, Ayumi Shinohara, Masaki Suwa

New Generation Comput.　36　(2)　91-93　2018

DOI： 10.1007/s00354-018-0032-8 　
Computing Longest Single-arm-gapped Palindromes in a String Peer-reviewed

Shintaro Narisada, Diptarama, Kazuyuki Narisawa, Shunsuke Inenaga, Ayumi Shinohara

SOFSEM 2017: THEORY AND PRACTICE OF COMPUTER SCIENCE　10139　375-386　2017

DOI： 10.1007/978-3-319-51963-0_29 　

ISSN： 0302-9743

eISSN： 1611-3349
Longest Common Subsequence in at Least k Length Order-Isomorphic Substrings Peer-reviewed

Yohei Ueki, Diptarama, Masatoshi Kurihara, Yoshiaki Matsuoka, Kazuyuki Narisawa, Ryo Yoshinaka, Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara

SOFSEM 2017: THEORY AND PRACTICE OF COMPUTER SCIENCE　10139　363-374　2017

DOI： 10.1007/978-3-319-51963-0_28 　

ISSN： 0302-9743

eISSN： 1611-3349
Position Heaps for Parameterized Strings. Peer-reviewed

Diptarama, Takashi Katsura, Yuhei Otomo, Kazuyuki Narisawa, Ayumi Shinohara

28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017, July 4-6, 2017, Warsaw, Poland　8:1-8:13　2017
Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
An efficient query learning algorithm for zero-suppressed binary decision diagrams. Peer-reviewed

Hayato Mizumoto, Shota Todoroki, Diptarama, Ryo Yoshinaka, Ayumi Shinohara

International Conference on Algorithmic Learning Theory, ALT 2017, 15-17 October 2017, Kyoto University, Kyoto, Japan　360-371　2017
Publisher: PMLR
Compact Bit Encoding Schemes for Simply-Typed Lambda-Terms Peer-reviewed

Kotaro Takeda, Naoki Kobayashi, Kazuya Yaguchi, Ayumi Shinohara

ACM SIGPLAN NOTICES　51　(9)　146-157　2016/09

DOI： 10.1145/2951913.2951918 　

ISSN： 0362-1340

eISSN： 1558-1160
Drawing Strategies for Generalized Tic-Tac-Toe (p, q) Peer-reviewed

Diptarama, Kazuyuki Narisawa, Ayumi Shinohara

PROGRESS IN APPLIED MATHEMATICS IN SCIENCE AND ENGINEERING PROCEEDINGS　1705　(020021)　2016

DOI： 10.1063/1.4940269 　

ISSN： 0094-243X
Generalization of Efficient Implementation of Compression by Substring Enumeration Peer-reviewed

Shumpei Sakuma, Kazuyuki Narisawa, Ayumi Shinohara

2016 DATA COMPRESSION CONFERENCE (DCC)　630-630　2016

DOI： 10.1109/DCC.2016.86 　

ISSN： 1068-0314
Visualization and analysis of electrical energy consumption in laboratories Peer-reviewed

Ichinari Sato, Diptarama, Ayumi Shinohara

PROCEEDINGS 2016 5TH IIAI INTERNATIONAL CONGRESS ON ADVANCED APPLIED INFORMATICS IIAI-AAI 2016　509-512　2016

DOI： 10.1109/IIAI-AAI.2016.194 　
AC-Automaton Update Algorithm for Semi-dynamic Dictionary Matching Peer-reviewed

Diptarama, Ryo Yoshinaka, Ayumi Shinohara

STRING PROCESSING AND INFORMATION RETRIEVAL, SPIRE 2016　9954　110-121　2016

DOI： 10.1007/978-3-319-46049-9_11 　

ISSN： 0302-9743
Pattern Matching on Compressed Text. Peer-reviewed

Masayuki Takeda, Ayumi Shinohara

Encyclopedia of Algorithms 2016　1538-1542　2016

DOI： 10.1007/978-1-4939-2864-4_81 　
Fast Full Permuted Pattern Matching Algorithms on Multi-track Strings Peer-reviewed

Diptarama, Ryo Yoshinaka, Ayumi Shinohara

PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2016　7-21　2016
AC-Automaton Update Algorithm for Semi-dynamic Dictionary Matching Peer-reviewed

Diptarama, Ryo Yoshinaka, Ayumi Shinohara

STRING PROCESSING AND INFORMATION RETRIEVAL, SPIRE 2016　9954　110-121　2016

DOI： 10.1007/978-3-319-46049-9_11 　

ISSN： 0302-9743
A Fast Order-Preserving Matching with q-neighborhood Filtration Using SIMD Instructions. Peer-reviewed

Yohei Ueki, Kazuyuki Narisawa, Ayumi Shinohara

Proceedings of Student Research Forum Papers and Posters at SOFSEM 2016 co-located with 42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2016), Harrachov, Czech Republic, January 23-28, 2016.　108-115　2016
Publisher: CEUR-WS.org
KMP Based Pattern Matching Algorithms for Multi-Track Strings. Peer-reviewed

Diptarama, Yohei Ueki, Kazuyuki Narisawa, Ayumi Shinohara

Proceedings of Student Research Forum Papers and Posters at SOFSEM 2016 co-located with 42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2016), Harrachov, Czech Republic, January 23-28, 2016.　100-107　2016
Publisher: CEUR-WS.org
QBF Encoding of Generalized Tic-Tac-Toe. Peer-reviewed

Diptarama,Ryo Yoshinaka, Ayumi Shinohara

Proceedings of the 4th International Workshop on Quantified Boolean Formulas (QBF 2016) co-located with 19th International Conference on Theory and Applications of Satisfiability Testing (SAT 2016), Bordeaux, France, July 4, 2016.　14-26　2016
Publisher: CEUR-WS.org
Visualization and analysis of electrical energy consumption in laboratories Peer-reviewed

Ichinari Sato, Diptarama, Ayumi Shinohara

PROCEEDINGS 2016 5TH IIAI INTERNATIONAL CONGRESS ON ADVANCED APPLIED INFORMATICS IIAI-AAI 2016　509-512　2016

DOI： 10.1109/IIAI-AAI.2016.194 　
Generalization of Efficient Implementation of Compression by Substring Enumeration Peer-reviewed

Shumpei Sakuma, Kazuyuki Narisawa, Ayumi Shinohara

2016 DATA COMPRESSION CONFERENCE (DCC)　630-630　2016

DOI： 10.1109/DCC.2016.86 　

ISSN： 1068-0314
Filtering Multi-set Tree: Data Structure for Flexible Matching Using Multi-track Data Peer-reviewed

Kazuyuki Narisawa, Takashi Katsura, Hiroyuki Ota, Ayumi Shinohara

Interdisciplinary Information Sciences　21　(1)　37-47　2015/03
Publisher: Tohoku University
DOI： 10.4036/iis.2015.37 　

ISSN： 1340-9050

More details Close

Multi-track data are multi-set sequences that are suitable for representing time series data, such as multi-sensor data, polyphonic music data and traffic data. The permuted pattern matching problem aims to determine the occurrences of multi-track patterns in multi-track text by allowing the order of the pattern tracks to be permuted. In this study, we address permuted pattern matching by proposing a new data structure called a filtering multi-set tree (FILM tree). The FILM tree is a complete binary tree based on a spectral Bloom filter (SBF) with hash functions. This data structure is very simple but powerful, and it can be applied to both exact and approximate matching problems. We present experimental results that demonstrate the efficiency of our FILM tree-based approach.
Detecting regularities on grammar-compressed strings Peer-reviewed

Tomohiro, I, Wataru Matsubara, Kouji Shimohira, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Kazuyuki Narisawa, Ayumi Shinohara

INFORMATION AND COMPUTATION　240　74-89　2015/02

DOI： 10.1016/j.ic.2014.09.009 　

ISSN： 0890-5401

eISSN： 1090-2651
Detecting regularities on grammar-compressed strings Peer-reviewed

Tomohiro, I, Wataru Matsubara, Kouji Shimohira, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Kazuyuki Narisawa, Ayumi Shinohara

INFORMATION AND COMPUTATION　240　74-89　2015/02

DOI： 10.1016/j.ic.2014.09.009 　

ISSN： 0890-5401

eISSN： 1090-2651
Position Heaps for Permuted Pattern Matching on Multi-Track String Peer-reviewed

Takashi Katsura, Yuhei Otomo, Kazuyuki Narisawa, Ayumi Shinohara

Proceedings of Student Research Forum Papers and Posters at SOFSEM 2015, the 41st International Conference on Current Trends in Theory and Practice of Computer Science　41-53　2015/01/26
Position Heaps for Permuted Pattern Matching on Multi-Track String. Peer-reviewed

Takashi Katsura, Yuhei Otomo, Kazuyuki Narisawa, Ayumi Shinohara

Proceedings of Student Research Forum Papers and Posters at SOFSEM 2015, the 41st International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2015) , Pec pod Snezkou, Czech Republic, January 24-29, 2015.　41-53　2015
Publisher: CEUR-WS.org
一般化三並べの拡張：目標動物の組合せ Peer-reviewed

本田耕一, 八鍬友貴, 成澤和志, 篠原歩

情報処理学会論文誌　55　(11)　2336-2343　2014/11
Publisher: Information Processing Society of Japan (IPSJ)
ISSN： 1882-7764

More details Close

Frank Harary introduced achievement games for polyominoes as generalized Tic-Tac-Toe. Two players alternately mark cells on a board, and the player who first achieves a given polyomino wins. In this paper, we propose four new games: Game OR, Game nCellsOR, Game AND and Game NOTAND. The target of each game is a combination of polyominoes. We analyze the proposed games, and decide whether polyominoes are winners or losers.
一般化三並べの拡張：一手p石 Peer-reviewed

ディプタラマ, 成澤和志, 篠原歩

情報処理学会論文誌　55　(11)　2344-2352　2014/11
A Simple Classification Method for Class Imbalanced Data using the Kernel Mean Peer-reviewed

Yusuke Sato, Kazuyuki Narisawa, Ayumi Shinohara

Proceedings of the 6th International Conference on Knowledge Discovery and Information Retrieval (KDIR 2014)　327-334　2014/10/21

DOI： 10.5220/0005130103270334 　
Reducing Sample Complexity in Reinforcement Learning by Transferring Transition and Reward Probabilities Peer-reviewed

Kouta Oguni, Kazuyuki Narisawa, Ayumi Shinohara

Proceedings of the 6th International Conference on Agents and Artificial Intelligence (ICAART 2014)　632-638　2014/03/07

DOI： 10.5220/0004915606320638 　
Bounded Occurrence Edit Distance: A New Metric for String Similarity Joins with Edit Distance Constraints Peer-reviewed

Tomoki Komatsu, Ryosuke Okuta, Kazuyuki Narisawa, Ayumi Shinohara

SOFSEM 2014: THEORY AND PRACTICE OF COMPUTER SCIENCE　8327　(Springer-Verlag)　363-374　2014

DOI： 10.1007/978-3-319-04298-5_32 　

ISSN： 0302-9743
Efficient algorithm and coding for higher-order compression Peer-reviewed

Kazuya Yaguchi, Naoki Kobayashi, Ayumi Shinohara

Data Compression Conference Proceedings　434-434　2014
Publisher: Institute of Electrical and Electronics Engineers Inc.
DOI： 10.1109/DCC.2014.63 　

ISSN： 1068-0314
Bounded Occurrence Edit Distance: A New Metric for String Similarity Joins with Edit Distance Constraints Peer-reviewed

Tomoki Komatsu, Ryosuke Okuta, Kazuyuki Narisawa, Ayumi Shinohara

SOFSEM 2014: THEORY AND PRACTICE OF COMPUTER SCIENCE　8327　363-374　2014

DOI： 10.1007/978-3-319-04298-5_32 　

ISSN： 0302-9743
Reducing Sample Complexity in Reinforcement Learning by Transferring Transition and Reward Probabilities. Peer-reviewed

Kouta Oguni, Kazuyuki Narisawa, Ayumi Shinohara

ICAART 2014 - Proceedings of the 6th International Conference on Agents and Artificial Intelligence, Volume 1, ESEO, Angers, Loire Valley, France, 6-8 March, 2014　632-638　2014
Publisher: SciTePress
DOI： 10.5220/0004915606320638 　
A Simple Classification Method for Class Imbalanced Data using the Kernel Mean. Peer-reviewed

Yusuke Sato, Kazuyuki Narisawa, Ayumi Shinohara

KDIR 2014 - Proceedings of the International Conference on Knowledge Discovery and Information Retrieval, Rome, Italy, 21 - 24 October, 2014　327-334　2014
Publisher: SciTePress
DOI： 10.5220/0005130103270334 　
Efficient algorithm and coding for higher-order compression Peer-reviewed

Kazuya Yaguchi, Naoki Kobayashi, Ayumi Shinohara

Data Compression Conference Proceedings　434　2014
Publisher: Institute of Electrical and Electronics Engineers Inc.
DOI： 10.1109/DCC.2014.63 　

ISSN： 1068-0314
Average number of occurrences of repetitions in a necklace Peer-reviewed

Kazuhiko Kusano, Ayumi Shinohara

DISCRETE APPLIED MATHEMATICS　163　334-342　2014/01

DOI： 10.1016/j.dam.2013.05.019 　

ISSN： 0166-218X

eISSN： 1872-6771
On Morphisms Generating Run-Rich Strings Peer-reviewed

Kazuhiko Kusano, Kazuyuki Narisawa, Ayumi Shinohara

Proc. The Prague Stringology Conference 2013 (PSC2013)　35-47　2013/09/03
On the hardness of approximating the minimum consistent DFA from prefix samples Peer-reviewed

Kaori Ueno, Shinichi Shimozono, Kazuyuki Narisawa, Ayumi Shinohara

ICALP 2013 Satellite Workshop on Learning Theory and ComplexityLearning Theory and Complexity (LTC 2013), (post-proceedings will be published later)　2013/07/07
Permuted pattern matching on multi-track strings Peer-reviewed

Takashi Katsura, Kazuyuki Narisawa, Ayumi Shinohara, Hideo Bannai, Shunsuke Inenaga

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　7741　(Springer-Verlag)　280-291　2013

DOI： 10.1007/978-3-642-35843-2_25 　

ISSN： 0302-9743 1611-3349
Detecting Regularities on Grammar-Compressed Strings Peer-reviewed

Tomohiro, I, Wataru Matsubara, Kouji Shimohira, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Kazuyuki Narisawa, Ayumi Shinohara

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2013　8087　(Springer-Verlag)　571-582　2013

DOI： 10.1007/978-3-642-40313-2_51 　

ISSN： 0302-9743
On Morphisms Generating Run-Rich Strings. Peer-reviewed

Kazuhiko Kusano, Kazuyuki Narisawa, Ayumi Shinohara

Proceedings of the Prague Stringology Conference 2013, Prague, Czech Republic, September 2-4, 2013　35-47　2013
Publisher: Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague
Permuted pattern matching on multi-track strings Peer-reviewed

Takashi Katsura, Kazuyuki Narisawa, Ayumi Shinohara, Hideo Bannai, Shunsuke Inenaga

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　7741　280-291　2013
Publisher: Springer
DOI： 10.1007/978-3-642-35843-2_25 　

ISSN： 0302-9743 1611-3349
Detecting Regularities on Grammar-Compressed Strings Peer-reviewed

Tomohiro, I, Wataru Matsubara, Kouji Shimohira, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Kazuyuki Narisawa, Ayumi Shinohara

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2013　8087　571-582　2013

DOI： 10.1007/978-3-642-40313-2_51 　

ISSN： 0302-9743
Functional programs as compressed data Peer-reviewed

Naoki Kobayashi, Kazutaka Matsuda, Ayumi Shinohara, Kazuya Yaguchi

Higher-Order and Symbolic Computation　25　(1)　39-84　2012/03/01
Publisher: Kluwer Academic Publishers
DOI： 10.1007/s10990-013-9093-z 　

ISSN： 1388-3690
Functional programs as compressed data Peer-reviewed

Naoki Kobayashi, Kazutaka Matsuda, Ayumi Shinohara, Kazuya Yaguchi

Higher-Order and Symbolic Computation　25　(1)　39-84　2012/03/01
Publisher: Kluwer Academic Publishers
DOI： 10.1007/s10990-013-9093-z 　

ISSN： 1388-3690
Functional programs as compressed data Peer-reviewed

Naoki Kobayashi, Kazutaka Matsuda, Ayumi Shinohara, Kazuya Yaguchi

ACM SIGPLAN 2012 Workshop on Partial Evaluation and Program Manipulation (PEPM 2012)　121-130　2012/02/01

DOI： 10.1145/2103746.2103770 　
PREDICTION FOR CONTROL DELAY ON REINFORCEMENT LEARING Peer-reviewed

Junya Saito, Kazuyuki Narisawa, Ayumi Shinohara

ICAART: PROCEEDINGS OF THE 4TH INTERNATIONAL CONFERENCE ON AGENTS AND ARTIFICIAL INTELLIGENCE, VOL 1　579-586　2012

DOI： 10.5220/0003888405790586 　
Computing Maximum Number of Runs in Strings Peer-reviewed

Kazuhiko Kusano, Kazuyuki Narisawa, Ayumi Shinohara

STRING PROCESSING AND INFORMATION RETRIEVAL　7608　(Springer-Verlag)　318-329　2012

DOI： 10.1007/978-3-642-34109-0_33 　

ISSN： 0302-9743
Computing Maximum Number of Runs in Strings Peer-reviewed

Kazuhiko Kusano, Kazuyuki Narisawa, Ayumi Shinohara

STRING PROCESSING AND INFORMATION RETRIEVAL　7608　318-329　2012

DOI： 10.1007/978-3-642-34109-0_33 　

ISSN： 0302-9743
Functional programs as compressed data. Peer-reviewed

Naoki Kobayashi, Kazutaka Matsuda, Ayumi Shinohara

Proceedings of the ACM SIGPLAN 2012 Workshop on Partial Evaluation and Program Manipulation, PEPM 2012, Philadelphia, Pennsylvania, USA, January 23-24, 2012　121-130　2012
Publisher: ACM
PREDICTION FOR CONTROL DELAY ON REINFORCEMENT LEARING Peer-reviewed

Junya Saito, Kazuyuki Narisawa, Ayumi Shinohara

ICAART: PROCEEDINGS OF THE 4TH INTERNATIONAL CONFERENCE ON AGENTS AND ARTIFICIAL INTELLIGENCE, VOL 1　579-586　2012

DOI： 10.5220/0003888405790586 　
Similarity Measure using Lossy Compression and its Application to Image Retrieval Peer-reviewed

Kosuke Bannai, Kazuyuki Narisawa, Ayumi Shinohara

The GSTF International Journal on Computing (JoC)　1　(3)　45-50　2011/08/01
Similarity Measure using Lossy Compression and its Application to Image Retrieval Peer-reviewed

Kosuke Bannai, Kazuyuki Narisawa, Ayumi Shinohara

Annual International Conference on Information Theory and Application (ITA 2011)　14　(19)　2011/02/01
A hypothesis verification method using regression tree for semiconductor yield analysis Peer-reviewed

Hidetaka Tsuda, Hidehiro Shirai, Masahiro Terabe, Kazuo Hashimoto, Ayumi Shinohara

IEEJ Transactions on Industry Applications　131　(10)　1232-1239　2011

DOI： 10.1541/ieejias.131.1232 　

ISSN： 0913-6339 1348-8163
An Efficient Algorithm to Test Square-Freeness of Strings Compressed by Balanced Straight Line Programs Peer-reviewed

Wataru Matsubara, Shunsuke Inenaga, Ayumi Shinohara

Chicago Journal of Theoretical Computer Science　Article 7　1-20　2010/06/22

DOI： 10.4086/cjtcs.2010.007 　
Inferring Strings from Runs Peer-reviewed

Wataru Matsubara, Akira Ishino, Ayumi Shinohara

PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2010　150-160　2010
The Number of Runs in a Ternary Word Peer-reviewed

Hideo Bannai, Mathieu Giraud, Kazuhiko Kusano, Wataru Matsubara, Ayumi Shinohara, Jamie Simpson

PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2010　178-181　2010
The Number of Runs in a Ternary Word Peer-reviewed

Hideo Bannai, Mathieu Giraud, Kazuhiko Kusano, Wataru Matsubara, Ayumi Shinohara, Jamie Simpson

PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2010　178-181　2010
Average Number of Runs and Squares in Necklace Peer-reviewed

Kazuhiko Kusano, Ayumi Shinohara

PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2010　167-177　2010
Inferring Strings from Runs Peer-reviewed

Wataru Matsubara, Akira Ishino, Ayumi Shinohara

PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2010　150-160　2010
Multi-target adaptive A*. Peer-reviewed

Kengo Matsuta, Hayato Kobayashi, Ayumi Shinohara

9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010), Toronto, Canada, May 10-14, 2010, Volume 1-3　1065-1072　2010
Publisher: IFAAMAS
An Efficient Algorithm to Test Square-Freeness of Strings Compressed by Balanced Straight Line Programs. Peer-reviewed

Wataru Matsubara, Shunsuke Inenaga, Ayumi Shinohara

Chicago J. Theor. Comput. Sci.　2010　2010
The Size of Message Set Needed for the Optimal Communication Policy Peer-reviewed

Tatsuya Kasai, Hayato Kobayashi, Ayumi Shinohara

Proceedings of the 7th European Workshop on Multi-Agent Systems　S40　2009/12/18
Linear-Time text compression by longest-first substitution Peer-reviewed

Ryosuke Nakamura, Shunsuke Inenaga, Hideo Bannai, Takashi Funamoto, Masayuki Takeda, Ayumi Shinohara

Algorithms　2　(4)　1429-1448　2009/12

DOI： 10.3390/a2041429 　

ISSN： 1999-4893
AVERAGE VALUE OF SUM OF EXPONENTS OF RUNS IN A STRING Peer-reviewed

Kazuhiko Kusano, Wataru Matsubara, Akira Ishino, Ayumi Shinohara

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE　20　(6)　1135-1146　2009/12

DOI： 10.1142/S0129054109007078 　

ISSN： 0129-0541
AVERAGE VALUE OF SUM OF EXPONENTS OF RUNS IN A STRING Peer-reviewed

Kazuhiko Kusano, Wataru Matsubara, Akira Ishino, Ayumi Shinohara

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE　20　(6)　1135-1146　2009/12

DOI： 10.1142/S0129054109007078 　

ISSN： 0129-0541
Linear-Time text compression by longest-first substitution Peer-reviewed

Ryosuke Nakamura, Shunsuke Inenaga, Hideo Bannai, Takashi Funamoto, Masayuki Takeda, Ayumi Shinohara

Algorithms　2　(4)　1429-1448　2009/12

DOI： 10.3390/a2041429 　

ISSN： 1999-4893
Development of an Interactive Augmented Environment and Its Application to Autonomous Learning for Quadruped Robots Peer-reviewed

Hayato Kobayashi, Tsugutoyo Osaki, Tetsuro Okuyama, Joshua Gramm, Akira Ishino, Ayumi Shinohara

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS　E92D　(9)　1752-1761　2009/09

DOI： 10.1587/transinf.E92.D.1752 　

ISSN： 0916-8532
Complexity of Teaching by a Restricted Number of Examples Peer-reviewed

Hayato Kobayashi, Ayumi Shinohara

The 22nd Conference on Learning Theory　2009/06/18
Improvement of the performance using received message on learning of communication codes Peer-reviewed

Tatsuya Kasai, Hayato Kobayashi, Ayumi Shinohara

8th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2009)　2　2009/05/10
Efficient algorithms to compute compressed longest common substrings and compressed palindromes Peer-reviewed

Wataru Matsubara, Shunsuke Inenaga, Akira Ishino, Ayumi Shinohara, Tomoyuki Nakamura, Kazuo Hashimoto

THEORETICAL COMPUTER SCIENCE　410　(8-10)　900-913　2009/03

DOI： 10.1016/j.tcs.2008.12.016 　

ISSN： 0304-3975
Efficient algorithms to compute compressed longest common substrings and compressed palindromes Peer-reviewed

Wataru Matsubara, Shunsuke Inenaga, Akira Ishino, Ayumi Shinohara, Tomoyuki Nakamura, Kazuo Hashimoto

THEORETICAL COMPUTER SCIENCE　410　(8-10)　900-913　2009/03

DOI： 10.1016/j.tcs.2008.12.016 　

ISSN： 0304-3975
Testing Square-Freeness of Strings Compressed by Balanced Straight Line Program Peer-reviewed

Wataru Matsubara, Shunsuke Inenaga, Ayumi Shinohara

Proc. 15th Computing: The Australasian Theory Symposium　94　21-30　2009/01/20
Development of an Augmented Environment and Autonomous Learning for Quadruped Robots Peer-reviewed

Hayato Kobayashi, Tsugutoyo Osaki, Tetsuro Okuyama, Akira Ishino, Ayumi Shinohara

ROBOCUP 2008: ROBOT SOCCER WORLD CUP XII　5399　109-120　2009

DOI： 10.1007/978-3-642-02921-9_10 　

ISSN： 0302-9743
Thinning-out: A method to reduce trials in skill discovery of a robot Peer-reviewed

Hayato Kobayashi, Kohei Hatano, Akira Ishino, Ayumi Shinohara

Transactions of the Japanese Society for Artificial Intelligence　24　(1)　191-202　2009
Publisher: Japanese Society for Artificial Intelligence
DOI： 10.1527/tjsai.24.191 　

ISSN： 1346-8030 1346-0714
A Series of Run-Rich Strings Peer-reviewed

Wataru Matsubara, Kazuhiko Kusano, Hideo Bannai, Ayumi Shinohara

LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS　5457　578-+　2009

DOI： 10.1007/978-3-642-00982-2_49 　

ISSN： 0302-9743
Analysis methodology for semiconductor yield by data mining Peer-reviewed

Tsuda Hidetaka, Hidehiro Shirai, Masahiro Terabe, Kazuo Hashimoto, Ayumi Shinohara

IEEJ Transactions on Industry Applications　129　(12)　9-1211　2009

DOI： 10.1541/ieejias.129.1201 　

ISSN： 0913-6339 1348-8163
Development of an Augmented Environment and Autonomous Learning for Quadruped Robots Peer-reviewed

Hayato Kobayashi, Tsugutoyo Osaki, Tetsuro Okuyama, Akira Ishino, Ayumi Shinohara

ROBOCUP 2008: ROBOT SOCCER WORLD CUP XII　5399　109-120　2009

DOI： 10.1007/978-3-642-02921-9_10 　

ISSN： 0302-9743
Bit-parallel algorithms for computing all the runs in a string Peer-reviewed

Kazunori Hirashima, Hideo Bannai, Wataru Matsubara, Akira Ishino, Ayumi Shinohara

PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2009　203-213　2009
A Series of Run-Rich Strings Peer-reviewed

Wataru Matsubara, Kazuhiko Kusano, Hideo Bannai, Ayumi Shinohara

LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS　5457　578-+　2009

DOI： 10.1007/978-3-642-00982-2_49 　

ISSN： 0302-9743
Complexity of Teaching by a Restricted Number of Examples. Peer-reviewed

Hayato Kobayashi, Ayumi Shinohara

COLT 2009 - The 22nd Conference on Learning Theory, Montreal, Quebec, Canada, June 18-21, 2009　2009
Testing Square-Freeness of Strings Compressed by Balanced Straight Line Program. Peer-reviewed

Wataru Matsubara, Shunsuke Inenaga, Ayumi Shinohara

Theory of Computing 2009, Fifteenth Computing: The Australasian Theory Symposium, CATS 2009, Wellington, New Zealand, January 2009　19-28　2009
Publisher: Australian Computer Society
Improvement of the performance using received message on learning of communication codes. Peer-reviewed

Tatsuya Kasai, Hayato Kobayashi, Ayumi Shinohara

8th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2009), Budapest, Hungary, May 10-15, 2009, Volume 2　1229-1230　2009
Publisher: IFAAMAS
A trend mining method for yield improvement based on trend in time series

Hidetaka Tsuda, Hidehiro Shirai, Masahiro Terabe, Kazuo Hashimoto, Ayumi Shinohara

IEEE International Symposium on Semiconductor Manufacturing Conference Proceedings　247-250　2008

ISSN： 1523-553X
Computing longest common substring and all palindromes from compressed strings Peer-reviewed

Wataru Matsubara, Shunsuke Inenaga, Akira Ishino, Ayumi Shinohara, Tomoyuki Nakamura, Kazuo Hashimoto

SOFSEM 2008: THEORY AND PRACTICE OF COMPUTER SCIENCE　4910　364-+　2008

DOI： 10.1007/978-3-540-77566-9_31 　

ISSN： 0302-9743
Autonomous Learning of Ball Passing by Four-legged Robots and Trial Reduction by Thinning-out and Surrogate Functions Peer-reviewed

Hayato Kobayashi, Kohei Hatano, Akira Ishino, Ayumi Shinohara

IAS-10: INTELLIGENT AUTONOMOUS SYSTEMS 10　145-154　2008

DOI： 10.3233/978-1-58603-887-8-145 　
New Lower Bounds for the Maximum Number of Runs in a String Peer-reviewed

Wataru Matsubara, Kazuhiko Kusano, Akira Ishino, Hideo Bannai, Ayumi Shinohara

PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2008　140-145　2008
Average Value of Sum of Exponents of Runs in Strings Peer-reviewed

Kazuhiko Kusano, Wataru Matsubara, Akira Ishino, Ayumi Shinohara

PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2008　185-192　2008
New Lower Bounds for the Maximum Number of Runs in a String Peer-reviewed

Wataru Matsubara, Kazuhiko Kusano, Akira Ishino, Hideo Bannai, Ayumi Shinohara

PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2008　abs/0804.1214　140-145　2008
An Efficient Algorithm to Test Square-Freeness of Strings Compressed by Balanced Straight Line Program. Peer-reviewed

Wataru Matsubara, Shunsuke Inenaga, Ayumi Shinohara

Structure-Based Compression of Complex Massive Data, 22.06. - 27.06.2008　2008
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany
Average Value of Sum of Exponents of Runs in Strings Peer-reviewed

Kazuhiko Kusano, Wataru Matsubara, Akira Ishino, Ayumi Shinohara

PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2008　185-192　2008
New Lower Bounds for the Maximum Number of Runs in a String Peer-reviewed

Wataru Matsubara, Kazuhiko Kusano, Akira Ishino, Hideo Bannai, Ayumi Shinohara

PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2008　140-145　2008
Computing longest common substring and all palindromes from compressed strings Peer-reviewed

Wataru Matsubara, Shunsuke Inenaga, Akira Ishino, Ayumi Shinohara, Tomoyuki Nakamura, Kazuo Hashimoto

SOFSEM 2008: THEORY AND PRACTICE OF COMPUTER SCIENCE　4910　364-+　2008

DOI： 10.1007/978-3-540-77566-9_31 　

ISSN： 0302-9743
Autonomous learning of ball trapping in the four-legged robot league Peer-reviewed

Hayato Kobayashi, Tsugutoyo Osaki, Eric Williams, Akira Ishino, Ayumi Shinohara

ROBOCUP 2006: ROBOT SOCCER WORLD CUP X　4434　86-+　2007

DOI： 10.1007/978-3-540-74024-7_8 　

ISSN： 0302-9743
Reducing trials by thinning-out in skill discovery Peer-reviewed

Hayato Kobayashi, Kohei Hatano, Akira Ishino, Ayumi Shinohara

DISCOVERY SCIENCE, PROCEEDINGS　4755　127-+　2007

DOI： 10.1007/978-3-540-75488-6_13 　

ISSN： 0302-9743
Autonomous learning of ball trapping in the four-legged robot league Peer-reviewed

Hayato Kobayashi, Tsugutoyo Osaki, Eric Williams, Akira Ishino, Ayumi Shinohara

ROBOCUP 2006: ROBOT SOCCER WORLD CUP X　4434　86-+　2007

DOI： 10.1007/978-3-540-74024-7_8 　

ISSN： 0302-9743
Reducing trials by thinning-out in skill discovery Peer-reviewed

Hayato Kobayashi, Kohei Hatano, Akira Ishino, Ayumi Shinohara

DISCOVERY SCIENCE, PROCEEDINGS　4755　127-+　2007

DOI： 10.1007/978-3-540-75488-6_13 　

ISSN： 0302-9743
A Framework for Advanced Robot Programming in the RoboCup Domain - Using Plug-in System and Scripting Language Peer-reviewed

Hayato Kobayashi, Akira Ishino, Ayumi Shinohara

INTELLIGENT AUTONOMOUS SYSTEMS 9　660-+　2006
Ball tracking with velocity based on Monte-Carlo localization Peer-reviewed

Jun Inoue, Akira Ishino, Ayumi Shinohara

INTELLIGENT AUTONOMOUS SYSTEMS 9　686-+　2006
Ball tracking with velocity based on Monte-Carlo localization Peer-reviewed

Jun Inoue, Akira Ishino, Ayumi Shinohara

INTELLIGENT AUTONOMOUS SYSTEMS 9　686-+　2006
A Framework for Advanced Robot Programming in the RoboCup Domain - Using Plug-in System and Scripting Language Peer-reviewed

Hayato Kobayashi, Akira Ishino, Ayumi Shinohara

INTELLIGENT AUTONOMOUS SYSTEMS 9　660-+　2006
A fully compressed pattern matching algorithm for simple collage systems Peer-reviewed

S Inenaga, A Shinohara, M Takeda

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE　16　(6)　1155-1166　2005/12

DOI： 10.1142/S0129054105003728 　

ISSN： 0129-0541

eISSN： 1793-6373
The size of subsequence automaton Peer-reviewed

Z Tronicek, A Shinohara

THEORETICAL COMPUTER SCIENCE　341　(1-3)　379-384　2005/09

DOI： 10.1016/j.tcs.2005.03.027 　

ISSN： 0304-3975
The size of subsequence automaton Peer-reviewed

Z Tronicek, A Shinohara

THEORETICAL COMPUTER SCIENCE　341　(1-3)　379-384　2005/09

DOI： 10.1016/j.tcs.2005.03.027 　

ISSN： 0304-3975
On-line construction of compact directed acyclic word graphs Peer-reviewed

Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa, Giancarlo Mauri, Giulio Pavesi

Discrete Applied Mathematics　146　(2)　156-179　2005/03/01

DOI： 10.1016/j.dam.2004.04.012 　

ISSN： 0166-218X
On-line construction of compact directed acyclic word graphs Peer-reviewed

S Inenaga, H Hoshino, A Shinohara, M Takeda, S Arikawa, G Mauri, G Pavesi

DISCRETE APPLIED MATHEMATICS　146　(2)　156-179　2005/03

DOI： 10.1016/dam.2004.04.012 　

ISSN： 0166-218X
On bit-parallel processing of multi-byte text Peer-reviewed

H Hyyro, J Takaba, A Shinohara, M Takeda

INFORMATION RETRIEVAL TECHNOLOGY　3411　289-300　2005

ISSN： 0302-9743
Fast bit-vector algorithms for approximate string matching under indel distance Peer-reviewed

H Hyyro, Y Pinzon, A Shinohara

SOFSEM 2005:THEORY AND PRACTICE OF COMPUTER SCIENCE　3381　380-384　2005

DOI： 10.1007/b105088 　

ISSN： 0302-9743
New bit-parallel Indel-distance algorithm Peer-reviewed

H Hyyro, Y Pinzon, A Shinohara

EXPERIMENTAL AND EFFICIENT ALGORITHMS, PROCEEDINGS　3503　380-390　2005

DOI： 10.1007/11427186_33 　

ISSN： 0302-9743
Fully incremental LCS computation Peer-reviewed

Y Ishida, S Inenaga, A Shinohara, M Takeda

FUNDAMENTALS OF COMPUTATIONAL THEORY, PROCEEDINGS　3623　563-574　2005

DOI： 10.1007/11537311_49 　

ISSN： 0302-9743
On bit-parallel processing of multi-byte text Peer-reviewed

H Hyyro, J Takaba, A Shinohara, M Takeda

INFORMATION RETRIEVAL TECHNOLOGY　3411　289-300　2005

DOI： 10.1007/978-3-540-31871-2_25 　

ISSN： 0302-9743
New bit-parallel Indel-distance algorithm Peer-reviewed

H Hyyro, Y Pinzon, A Shinohara

EXPERIMENTAL AND EFFICIENT ALGORITHMS, PROCEEDINGS　3503　380-390　2005

DOI： 10.1007/11427186_33 　

ISSN： 0302-9743
Fast bit-vector algorithms for approximate string matching under indel distance Peer-reviewed

H Hyyro, Y Pinzon, A Shinohara

SOFSEM 2005:THEORY AND PRACTICE OF COMPUTER SCIENCE　3381　380-384　2005

DOI： 10.1007/978-3-540-30577-4_44 　

ISSN： 0302-9743
Fully incremental LCS computation Peer-reviewed

Y Ishida, S Inenaga, A Shinohara, M Takeda

FUNDAMENTALS OF COMPUTATIONAL THEORY, PROCEEDINGS　3623　563-574　2005

DOI： 10.1007/11537311_49 　

ISSN： 0302-9743
Ternary directed acyclic word graphs Peer-reviewed

S Miyamoto, S Inenaga, M Takeda, A Shinohara

THEORETICAL COMPUTER SCIENCE　328　(1-2)　97-111　2004/11

DOI： 10.1016/j.tcs.2004.07.008 　

ISSN： 0304-3975
Ternary directed acyclic word graphs Peer-reviewed

S Miyamoto, S Inenaga, M Takeda, A Shinohara

THEORETICAL COMPUTER SCIENCE　328　(1-2)　97-111　2004/11

DOI： 10.1016/j.tcs.2004.07.008 　

ISSN： 0304-3975
An O(N-2) algorithm for discovering optimal boolean pattern pairs Peer-reviewed

H Bannai, H Hyyro, A Shinohara, M Takeda, K Nakai, S Miyano

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS　1　(4)　159-170　2004/10

DOI： 10.1109/TCBB.2004.36 　

ISSN： 1545-5963
An O(N-2) algorithm for discovering optimal boolean pattern pairs Peer-reviewed

H Bannai, H Hyyro, A Shinohara, M Takeda, K Nakai, S Miyano

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS　1　(4)　159-170　2004/10

DOI： 10.1109/TCBB.2004.36 　

ISSN： 1545-5963
Expression profiling of gene with upstream AML I recognition sequence in hematopoietic stem cell-like fractions from individuals with the M2 subtype of human acute myeloid leukemia Peer-reviewed

Y Oshima, Y Ishida, A Shinohara, H Mano, A Fujimura

EXPERIMENTAL HEMATOLOGY　32　(7)　34-34　2004/07

ISSN： 0301-472X
Efficiently finding regulatory elements using correlation with gene expression Peer-reviewed

Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Satoru Miyano

Journal of Bioinformatics and Computational Biology　2　(2)　273-288　2004/06

DOI： 10.1142/S0219720004000612 　

ISSN： 0219-7200
Efficiently finding regulatory elements using correlation with gene expression Peer-reviewed

Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Satoru Miyano

Journal of Bioinformatics and Computational Biology　2　(2)　273-288　2004/06

DOI： 10.1142/S0219720004000612 　

ISSN： 0219-7200
Compact directed acyclic word graphs for a sliding window Peer-reviewed

Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa

Journal of Discrete Algorithms　2　(1)　33-51　2004/03

DOI： 10.1016/S1570-8667(03)00064-9 　

ISSN： 1570-8667
Compact directed acyclic word graphs for a sliding window Peer-reviewed

Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa

Journal of Discrete Algorithms　2　(1)　33-51　2004/03

DOI： 10.1016/S1570-8667(03)00064-9 　

ISSN： 1570-8667
An efficient pattern matching algorithm on a subclass of context free grammars Peer-reviewed

S Inenaga, A Shinohara, M Takeda

DEVELOPMENTS IN LANGUAGE THEORY, PROCEEDINGS　3340　225-236　2004

DOI： 10.1007/b103739 　

ISSN： 0302-9743
Finding optimal pairs of patterns Peer-reviewed

H Bannai, H Hyyro, A Shinohara, M Takeda, K Nakai, S Miyano

ALGORITHMS IN BIOINFORMATICS, PROCEEDINGS　3240　450-462　2004

DOI： 10.1007/978-3-540-30219-3_38 　

ISSN： 0302-9743
A Fully Compressed Pattern Matching Algorithm for Simple Collage Systems. Peer-reviewed

Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda

Proceedings of the Prague Stringology Conference 2004, Prague, Czech Republic, August 30 - September 1, 2004　98-113　2004
Publisher: Department of Computer Science and Engineering, Faculty of Electrical Engineering, Czech Technical University
An efficient pattern matching algorithm on a subclass of context free grammars Peer-reviewed

S Inenaga, A Shinohara, M Takeda

DEVELOPMENTS IN LANGUAGE THEORY, PROCEEDINGS　3340　225-236　2004

DOI： 10.1007/978-3-540-30550-7_19 　

ISSN： 0302-9743
Finding optimal pairs of cooperative and competing patterns with bounded distance Peer-reviewed

S Inenaga, H Bannai, H Hyyro, A Shinohara, M Takeda, K Nakai, S Miyano

DISCOVERY SCIENCE, PROCEEDINGS　3245　32-46　2004

DOI： 10.1007/978-3-540-30214-8_3 　

ISSN： 0302-9743
String pattern discovery Peer-reviewed

A Shinohara

ALGORITHMIC LEARNING THEORY, PROCEEDINGS　3244　1-13　2004

DOI： 10.1007/978-3-540-30215-5_1 　

ISSN： 0302-9743
A Note on Randomized Algorithm for String Matching with Mismatches Peer-reviewed

Kensuke Baba, Ayumi Shinohara, Masayuki Takeda, Shunsuke Inenaga, Setsuo Arikawa

Nordic Journal of Computing　10　(1)　2-12　2003/04
Collage system: a unifying framework for compressed pattern matching Peer-reviewed

T Kida, T Matsumoto, Y Shibata, M Takeda, A Shinohara, S Arikawa

THEORETICAL COMPUTER SCIENCE　298　(1)　253-272　2003/04

DOI： 10.1016/S0304-3975(02)00426-7 　

ISSN： 0304-3975

eISSN： 1879-2294
Collage system: a unifying framework for compressed pattern matching Peer-reviewed

T Kida, T Matsumoto, Y Shibata, M Takeda, A Shinohara, S Arikawa

THEORETICAL COMPUTER SCIENCE　298　(1)　253-272　2003/04

DOI： 10.1016/S0304-3975(02)00426-7 　

ISSN： 0304-3975

eISSN： 1879-2294
A generalization of FFT algorithms for string matching Peer-reviewed

Baba Kensuke, Tanaka Yoshihito, Nakatoh Tetsuya, Shinohara Ayumi, 馬場謙介, 田中義人, 中藤哲也, 篠原歩

Proceedings of the International Symposium on Information Science and Electrical Engineering　2003　191　2003
Uniform characterizations of polynomial-query learnabilities Peer-reviewed

Y Hayashi, S Matsumoto, A Shinohara, M Takeda

THEORETICAL COMPUTER SCIENCE　292　(2)　377-385　2003/01

DOI： 10.1016/S0304-3975(02)00177-9 　

ISSN： 0304-3975

eISSN： 1879-2294
A practical algorithm to find the best subsequence patterns Peer-reviewed

M Hirao, H Hoshino, A Shinohara, M Takeda, S Arikawa

THEORETICAL COMPUTER SCIENCE　292　(2)　465-479　2003/01

DOI： 10.1016/S0304-3975(02)00182-2 　

ISSN： 0304-3975

eISSN： 1879-2294
Ternary directed acyclic word graphs Peer-reviewed

S Miyamoto, S Inenaga, M Takeda, A Shinohara

IMPLEMENTATION AND APPLICATION OF AUTOMATA, PROCEEDINGS　2759　120-130　2003

DOI： 10.1007/3-540-45089-0_12 　

ISSN： 0302-9743
The size of subsequence automaton Peer-reviewed

Z Tronicek, A Shinohara

STRING PROCESSING AND INFORMATION RETRIEVAL, PROCEEDINGS　2857　304-310　2003

DOI： 10.1007/978-3-540-39984-1_23 　

ISSN： 0302-9743
Linear-time off-line text compression by longest-first substitution Peer-reviewed

S Inenaga, T Funamoto, M Takeda, A Shinohara

STRING PROCESSING AND INFORMATION RETRIEVAL, PROCEEDINGS　2857　137-152　2003

DOI： 10.1007/978-3-540-39984-1_11 　

ISSN： 0302-9743
Inferring strings from graphs and arrays Peer-reviewed

H Bannai, S Inenaga, A Shinohara, M Takeda

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2003, PROCEEDINGS　2747　208-217　2003

DOI： 10.1007/978-3-540-45138-9_15 　

ISSN： 0302-9743
On the length of the minimum solution of word equations in one variable Peer-reviewed

K Baba, S Tsuruta, A Shinohara, M Takeda

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2003, PROCEEDINGS　2747　189-197　2003

DOI： 10.1007/978-3-540-45138-9_13 　

ISSN： 0302-9743
Discovering most classificatory patterns for very expressive pattern classes Peer-reviewed

M Takeda, S Inenaga, H Bannai, A Shinohara, S Arikawa

DISCOVERY SCIENCE, PROCEEDINGS　2843　486-493　2003

DOI： 10.1007/978-3-540-39644-4_50 　

ISSN： 0302-9743
A practical algorithm to find the best subsequence patterns Peer-reviewed

M Hirao, H Hoshino, A Shinohara, M Takeda, S Arikawa

THEORETICAL COMPUTER SCIENCE　292　(2)　465-479　2003/01

DOI： 10.1016/S0304-3975(02)00182-2 　

ISSN： 0304-3975

eISSN： 1879-2294
Uniform characterizations of polynomial-query learnabilities Peer-reviewed

Y Hayashi, S Matsumoto, A Shinohara, M Takeda

THEORETICAL COMPUTER SCIENCE　292　(2)　377-385　2003/01

DOI： 10.1016/S0304-3975(02)00177-9 　

ISSN： 0304-3975

eISSN： 1879-2294
A Note on Randomized Algorithm for String Matching with Mismatches. Peer-reviewed

Kensuke Baba, Ayumi Shinohara, Masayuki Takeda, Shunsuke Inenaga, Setsuo Arikawa

Nord. J. Comput.　10　(1)　2-12　2003
A String Pattern Regression Algorithm and Its Application to Pattern Discovery in Long Introns Peer-reviewed

Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Satoru Miyano

Genome Informatics　13　3-11　2002/12

DOI： 10.11234/gi1990.13.3 　
Progress in Discovery Science, Final Report of the Japanese Discovery Science Project Peer-reviewed

Progress in Discovery Science 2002　2281　2002
Publisher: Springer
DOI： 10.1007/3-540-45884-0 　
A Note on Randomized Algorithm for String Matching with Mismatches. Peer-reviewed

Kensuke Baba, Ayumi Shinohara, Masayuki Takeda, Shunsuke Inenaga, Setsuo Arikawa

Proceedings of the Prague Stringology Conference 2002, Prague, Czech Republic, September 23-24, 2002　9-17　2002
Publisher: Department of Computer Science and Engineering, Faculty of Electrical Engineering, Czech Technical University
Compact directed acyclic word graphs for a sliding window Peer-reviewed

Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　2476　310-324　2002
Publisher: Springer Verlag
DOI： 10.1007/3-540-45735-6_27 　

ISSN： 1611-3349 0302-9743
Processing text files as is: Pattern matching over compressed texts, multi-byte character texts, and semi-structured texts Peer-reviewed

Masayuki Takeda, Satoru Miyamoto, Takuya Kida, Ayumi Shinohara, Shuichi Fukamachi, Takeshi Shinohara, Setsuo Arikawa

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　2476　170-186　2002
Publisher: Springer Verlag
DOI： 10.1007/3-540-45735-6_16 　

ISSN： 1611-3349 0302-9743
Space-economical construction of index structures for all suffixes of a string Peer-reviewed

S Inenaga, A Shinohara, M Takeda, H Bannai, S Arikawa

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2002　2420　341-352　2002

DOI： 10.1007/3-540-45687-2_28 　

ISSN： 0302-9743
Finding Best Patterns Practically. Peer-reviewed

Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa, Masahiro Hirao, Hiromasa Hoshino, Shunsuke Inenaga

Progress in Discovery Science, Final Report of the Japanese Discovery Science Project　307-317　2002
Publisher: Springer
DOI： 10.1007/3-540-45884-0_21 　
Discovering best variable-length-don't-care patterns Peer-reviewed

S Inenaga, H Bannai, A Shmohara, M Takeda, S Arikawa

DISCOVERY SCIENCE, PROCEEDINGS　2534　86-97　2002

DOI： 10.1007/3-540-36182-0_10 　

ISSN： 0302-9743
The minimum DAWG for all suffixes of a string and its applications Peer-reviewed

S Inenaga, M Takeda, A Shinohara, H Hoshino, S Arikawa

COMBINATORIAL PATTERN MATCHING　2373　153-167　2002

DOI： 10.1007/3-540-45452-7_14 　

ISSN： 0302-9743
平衡直線的プログラムに対するパターン照合アルゴリズム Peer-reviewed

平尾昌啓, 篠原歩, 竹田正幸, 有川節夫

電子情報通信学会和文論文誌　J84-A　(6)　722-730　2001/06
Publisher: The Institute of Electronics, Information and Communication Engineers
ISSN： 0913-5707
Speeding up string pattern matching by text compression Peer-reviewed

Masayuki Takeda, Yusuke Shibata, Tetsuya Matsumoto, Takuya Kida, Ayumi Shinohara, Shuichi Fukamachi, Takeshi Shinohara, Setsuo Arikawa

Trans. Information Processing Society of Japan　42　(3)　370-384　2001/03
Publisher: Information Processing Society of Japan (IPSJ)
ISSN： 1882-7764

More details Close

This paper describes our recent studies on string pattern matching in compressed texts mainly from practical viewpoints. The aim is to speed up the string pattern matching task, in comparison with an ordinary search over the original texts. We have successfully developed(1)an Ac type algorithm forsearching in Huffman encoded files, and(2)a KMP type algorithm and(3)a BM type algorithm for searching in files compressed by the so-called byte pair encoding(BPE). Each of the algorithms reduces the search time at nearly the same rate as the compression ratio. Surprisingly, the BM type algorithm runs over BPE compressed files about 1.2-3.0 times faster than the exact match routines of the software package agrep, which is known as the fastest pattern matching tool.
More Speed and More Pattern Variations for Knowledge Discovery System BONSAI

Bannai Hideo, Iida Keisuke, Shinohara Ayumi, Takeda Masayuki, Miyano Satoru

GI　12　454-455　2001
Publisher: Japanese Society for Bioinformatics
DOI： 10.11234/gi1990.12.454 　

ISSN： 0919-9454
Discovery Science, 4th International Conference, DS 2001, Washington, DC, USA, November 25-28, 2001, Proceedings Peer-reviewed

Discovery Science 2001　2226　2001
Publisher: Springer
DOI： 10.1007/3-540-45650-3 　
Construction of the CDAWG for a Trie. Peer-reviewed

Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa

Proceedings of the Prague Stringology Conference 2001, Prague, Czech Republic, September 4, 2001　37-48　2001
Publisher: Department of Computer Science and Engineering, Faculty of Electrical Engineering, Czech Technical University
Musical sequence comparison for melodic and rhythmic similarities Peer-reviewed

T Kadota, M Hirao, A Ishino, M Takeda, A Shinohara, F Matsuo

EIGHTH SYMPOSIUM ON STRING PROCESSING AND INFORMATION RETRIEVAL, PROCEEDINGS　111-122　2001

DOI： 10.1109/SPIRE.2001.989744 　
On-line construction of symmetric Compact Directed Acyclic Word Graphs Peer-reviewed

S Inenaga, H Hoshino, A Shinohara, M Takeda, S Arikawa

EIGHTH SYMPOSIUM ON STRING PROCESSING AND INFORMATION RETRIEVAL, PROCEEDINGS　96-110　2001

DOI： 10.1109/SPIRE.2001.989743 　
Fragmentary pattern matching: Complexity, algorithms and applications for analyzing classic literary works Peer-reviewed

H Hori, S Shimozono, M Takeda, A Shinohara

ALGORITHMS AND COMPUTATION, PROCEEDINGS　2223　719-730　2001

DOI： 10.1007/3-540-45678-3_61 　

ISSN： 0302-9743
A Practical Algorithm to Find the Best Episode Patterns. Peer-reviewed

Masahiro Hirao, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa

Discovery Science, 4th International Conference, DS 2001, Washington, DC, USA, November 25-28, 2001, Proceedings　435-440　2001
Publisher: Springer
DOI： 10.1007/3-540-45650-3_37 　
Discovering Repetitive Expressions and Affinities from Anthologies of Classical Japanese Poems. Peer-reviewed

Koichiro Yamamoto, Masayuki Takeda, Ayumi Shinohara, Tomoko Fukuda, Ichiro Nanri

Discovery Science, 4th International Conference, DS 2001, Washington, DC, USA, November 25-28, 2001, Proceedings　416-428　2001
Publisher: Springer
DOI： 10.1007/3-540-45650-3_35 　
Compressed pattern matching for SEQUITUR Peer-reviewed

S Mitarai, M Hirao, T Matsumoto, A Shinohara, M Takeda, S Arikawa

DCC 2001: DATA COMPRESSION CONFERENCE, PROCEEDINGS　469-478　2001

DOI： 10.1109/DCC.2001.917178 　

ISSN： 1068-0314
Faster approximate string matching over compressed text Peer-reviewed

G Navarro, T Kida, M Takeda, A Shinohara, S Arikawa

DCC 2001: DATA COMPRESSION CONFERENCE, PROCEEDINGS　459-468　2001

DOI： 10.1109/DCC.2001.917177 　

ISSN： 1068-0314
Multiple Pattern Matching Algorithms on Collage System. Peer-reviewed

Takuya Kida, Tetsuya Matsumoto, Masayuki Takeda, Ayumi Shinohara, Setsuo Arikawa

Combinatorial Pattern Matching, 12th Annual Symposium, CPM 2001 Jerusalem, Israel, July 1-4, 2001 Proceedings　193-206　2001
Publisher: Springer
DOI： 10.1007/3-540-48194-X_18 　
On-Line Construction of Compact Directed Acyclic Word Graphs. Peer-reviewed

Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa, Giancarlo Mauri, Giulio Pavesi

Combinatorial Pattern Matching, 12th Annual Symposium, CPM 2001 Jerusalem, Israel, July 1-4, 2001 Proceedings　169-180　2001
Publisher: Springer
DOI： 10.1007/3-540-48194-X_16 　
Finding Sparse Gene Networks

Shinohara Ayumi, Iida Keisuke, Takeda Masayuki, Maruyama Osamu, Miyano Satoru, Kuhara Satoru

GI　11　249-250　2000
Publisher: Japanese Society for Bioinformatics
DOI： 10.11234/gi1990.11.249 　

ISSN： 0919-9454
Bit-parallel approach to approximate string matching in compressed texts Peer-reviewed

T Matsumoto, T Kida, M Takeda, A Shinohara, S Arikawa

SPIRE 2000: SEVENTH INTERNATIONAL SYMPOSIUM ON STRING PROCESSING AND INFORMATION RETRIEVAL - PROCEEDINGS　221-228　2000

DOI： 10.1109/SPIRE.2000.878198 　
Online construction of subsequence automata for multiple texts Peer-reviewed

H Hoshino, A Shinohara, M Takeda, S Arikawa

SPIRE 2000: SEVENTH INTERNATIONAL SYMPOSIUM ON STRING PROCESSING AND INFORMATION RETRIEVAL - PROCEEDINGS　146-152　2000

DOI： 10.1109/SPIRE.2000.878190 　
Fully compressed pattern matching algorithm for balanced straight-line programs Peer-reviewed

M Hirao, A Shinohara, M Takeda, S Arikawa

SPIRE 2000: SEVENTH INTERNATIONAL SYMPOSIUM ON STRING PROCESSING AND INFORMATION RETRIEVAL - PROCEEDINGS　132-138　2000

DOI： 10.1109/SPIRE.2000.878188 　
A Practical Algorithm to Find the Best Subsequence Patterns. Peer-reviewed

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

Discovery Science, Third International Conference, DS 2000, Kyoto, Japan, December 4-6, 2000, Proceedings　141-154　2000
Publisher: Springer
DOI： 10.1007/3-540-44418-1_12 　
A Boyer-Moore type algorithm for compressed pattern matching Peer-reviewed

Y Shibata, T Matsumoto, M Takeda, A Shinohara, S Arikawa

COMBINATORIAL PATTERN MATCHING　1848　181-194　2000

DOI： 10.1007/3-540-45123-4_17 　

ISSN： 0302-9743
Speeding up pattern matching by text compression Peer-reviewed

Y Shibata, T Kida, S Fukamachi, M Takeda, A Shinohara, T Shinohara, S Arikawa

ALGORITHMS AND COMPLEXITY　1767　306-315　2000

DOI： 10.1007/3-540-46521-9_25 　

ISSN： 0302-9743
Polynomial-time learning of elementary formal systems Peer-reviewed

S Miyano, A Shinohara, T Shinohara

NEW GENERATION COMPUTING　18　(3)　217-242　2000

DOI： 10.1007/BF03037530 　

ISSN： 0288-3635
A System to Find Genetic Networks Using Weighted Network Model

Moriyama Tomohiro, Shinohara Ayumi, Takeda Masayuki, Maruyama Osamu, Goto Takao, Miyano Satoru, Kuhara Satoru

GI　10　186-195　1999
Publisher: Japanese Society for Bioinformatics
DOI： 10.11234/gi1990.10.186 　

ISSN： 0919-9454

More details Close

We are developing a system which finds a genetic network from data obtained by multiple gene disruptions and overexpressions. We deal with a genetic network as a weighted graph, where each weight represents the strength of activation from a gene to another gene. In this paper, we explain the overview of our system, and our strategy to visualize the weighted network. Wealso study the computational complexity related to the visualization.
A unifying framework for compressed pattern matching Peer-reviewed

Takuya Kida, Yusuke Shibata, Masayuki Takeda, Ayumi Shinohara, Setsuo Arikawa

String Processing and Information Retrieval Symposium and International Workshop on Groupware, SPIRE 1999 and CRIWG 1999　89-96　1999
Publisher: Institute of Electrical and Electronics Engineers Inc.
DOI： 10.1109/SPIRE.1999.796582 　
Knowledge discovery from health data using weighted aggregation classifier Peer-reviewed

T Takae, M Chikamune, H Arimura, A Shinohara, H Inoue, S Takeya, K Uezono, T Kawasaki

DISCOVERY SCIENCE, PROCEEDINGS　1721　359-361　1999

DOI： 10.1007/3-540-46846-3_48 　

ISSN： 0302-9743
Pattern matching in text compressed by using antidictionaries Peer-reviewed

Yusuke Shibata, Masayuki Takeda, Ayumi Shinohara, Setsuo Arikawa

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　1645　37-49　1999
Publisher: Springer Verlag
DOI： 10.1007/3-540-48452-3_3 　

ISSN： 1611-3349 0302-9743
Shift-and approach to pattern matching in LZW compressed text Peer-reviewed

Takuya Kida, Masayuki Takeda, Ayumi Shinohara, Setsuo Arikawa

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　1645　1-13　1999
Publisher: Springer Verlag
DOI： 10.1007/3-540-48452-3_1 　

ISSN： 1611-3349 0302-9743
On the hardness of approximating the minimum consistent acyclic DFA and decision diagram Peer-reviewed

S Shimozono, K Hirata, A Shinohara

INFORMATION PROCESSING LETTERS　66　(4)　165-170　1998/05

DOI： 10.1016/S0020-0190(98)00065-9 　

ISSN： 0020-0190

eISSN： 1872-6119
Finding tree patterns consistent with positive and negative examples using queries Peer-reviewed

H Ishizaka, H Arimura, T Shinohara

ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE　23　(1-2)　101-115　1998

ISSN： 1012-2443

eISSN： 1573-7470
Finding Genetic Network from Experiments by Weighted Network Model

Noda Kiyoshi, Shinohara Ayumi, Takeda Masayuki, Matsumoto Satoshi, Miyano Satoru, Kuhara Satoru

GI　9　141-150　1998
Publisher: Japanese Society for Bioinformatics
DOI： 10.11234/gi1990.9.141 　

ISSN： 0919-9454

More details Close

We study the problem of finding a genetic network from data obtained by multiple gene disruptions and overexpressions. We define a genetic network as a weighted graph, and analyze the computational complexity of the problem. We show that if there exists a weighted network which is consistent with given data, we can find it in polynomial time. Moreover, we also consider the optimization problem, where we try to find an optimally consistent weighted network with given data. We show that the problem is NP-hard. On the other hand, we give a polynomial-time approximation algorithm to solve it with approximation ratio 2. We report some simulation results on experiments.
Uniform characterizations of polynomial-query learnabilities Peer-reviewed

Y Hayashi, S Matsumoto, A Shinohara, M Takeda

DISCOVERY SCIENCE　1532　84-92　1998

DOI： 10.1007/3-540-49292-5_8 　

ISSN： 0302-9743
Multiple pattern matching in LZW compressed text Peer-reviewed

T Kida, M Takeda, A Shinohara, M Miyazaki, S Arikawa

DCC '98 - DATA COMPRESSION CONFERENCE　103-112　1998

DOI： 10.1109/DCC.1998.672136 　

ISSN： 1068-0314
Learning Pattern Languages Using Queries. Peer-reviewed

Satoshi Matsumoto, Ayumi Shinohara

Computational Learning Theory, Third European Conference, EuroCOLT '97, Jerusalem, Israel, March 17-19, 1997, Proceedings　185-197　1997
Publisher: Springer
DOI： 10.1007/3-540-62685-9_16 　
An improved pattern matching algorithm for strings in terms of straight-line programs Peer-reviewed

M Miyazaki, A Shinohara, M Takeda

COMBINATORIAL PATTERN MATCHING, PROCEEDINGS　1264　1-11　1997

DOI： 10.1007/3-540-63220-4_45 　

ISSN： 0302-9743
An Efficient Pattern-Matching Algorithm for Strings with Short Descriptions. Peer-reviewed

Marek Karpinski, Wojciech Rytter, Ayumi Shinohara

Nord. J. Comput.　4　(2)　172-186　1997
HAKKE: A Multi-Strategy Prediction System for Sequences

Furukawa Naohiro, Matsumoto Satoshi, Shinohara Ayumi, Shoudai Takayoshi, Miyano Satoru

GI　7　98-107　1996
Publisher: Japanese Society for Bioinformatics
DOI： 10.11234/gi1990.7.98 　

ISSN： 0919-9454

More details Close

We developed a machine learning system HAKKE which is suitable for predicting functional regions from sequences, such as protein-coding region prediction, and transmembrane domain prediction. HAKKE is a hybrid system cooperated by a number of algorithms of a pool to make an accurate prediction. The system uses an extension of the weighted majority algorithm in order to fit the strength of each algorithm into given training examples. In this paper, we describe the core of the system and show some experimental results on transmembrane domain and a-helix predictions.
On the Hardness of Approximating the Minimum Consistent OBDD Problem. Peer-reviewed

Kouichi Hirata, Shinichi Shimozono, Ayumi Shinohara

Algorithm Theory - SWAT '96, 5th Scandinavian Workshop on Algorithm Theory, Reykjavík, Iceland, July 3-5, 1996, Proceedings　96　(45)　112-123　1996
Publisher: Springer
DOI： 10.1007/3-540-61422-2_125 　

More details Close

Ordered binary decision diagrams (OBDDs, for short) represent Boolean functions as directed acyclic graphs. The minimum consistent OBDD problem is, given an incomplete truth table of a function, to find the smallest OBDD that is consistent with the truth table with respect to a fixed variable ordering. We show that this problem is NP-hard, and prove that there is a constant ε>0 such that no polynomial time algorithm can approximate the minimum consistent OBDD within the ratio n^ε unless P=NP, where n is the number of variables. This result suggests that OBDDs are unlikely to be polynomial time learnable in PAC-learning model. Furthermore, we give a polynomial time learnable subclass of OBDDs representing symmetric functions.
Pattern-matching for strings with short descriptions Peer-reviewed

M Karpinski, W Rytter, A Shinohara

COMBINATORIAL PATTERN MATCHING　937　(22)　205-214　1995

ISSN： 0302-9743
Developments in Computational Learning and Discovery Theory within the Framework of Elementary Formal Systems. Peer-reviewed

Setsuo Arikawa, Masako Sato, Ayumi Shinohara, Takeshi Shinohara

Machine Intelligence 15, Intelligent Agents [St. Catherine's College, Oxford, UK, July 1995]　15　227-247　1995
Publisher: Oxford University Press
BONSAI Garden: Parallel Knowledge Discovery System for Amino Acid Sequences. Peer-reviewed

Takayoshi Shoudai, Michael Lappe, Satoru Miyano, Ayumi Shinohara, Takeo Okazaki, Setsuo Arikawa, Tomoyuki Uchida, Shinichi Shimozono, Takeshi Shinohara, Satoru Kuhara

Proceedings of the Third International Conference on Intelligent Systems for Molecular Biology, Cambridge, United Kingdom, July 16-19, 1995　359-366　1995
Publisher: AAAI
Pattern-matching for strings with short descriptions Peer-reviewed

M Karpinski, W Rytter, A Shinohara

COMBINATORIAL PATTERN MATCHING　937　205-214　1995

DOI： 10.1007/3-540-60044-2_44 　

ISSN： 0302-9743
COMPLEXITY OF COMPUTING VAPNIK-CHERVONENKIS DIMENSION AND SOME GENERALIZED DIMENSIONS Peer-reviewed

A SHINOHARA

THEORETICAL COMPUTER SCIENCE　137　(1)　129-144　1995/01

DOI： 10.1016/0304-3975(94)00164-E 　

ISSN： 0304-3975
Assessment Report of Doctoral Theses

16　(3)　359-368　1994/12/01
Publisher:
DOI： 10.15017/17351 　

ISSN： 0388-1717
Assignment of Certainty-Factor Parameters with a Given Reasoning Tree for the Prediction of Protein Localization Sites

Nakai Kenta, Shinohara Ayumi, Miyano Satoru

GI　5　170-171　1994
Publisher: Japanese Society for Bioinformatics
DOI： 10.11234/gi1990.5.170 　

ISSN： 0919-9454

More details Close

In this age of large-scale sequencing, we have many "potentially expressed" amino acidsequences of unknown function. Characterization of such sequences by computers is undoubtedlyuseful for further experimental analyses. We have developed a knowledge-based system PSORT for characterizing various sorting signals potentially coded in amino acid sequences andfor predicting their final localization sites in cells [1, 2]. The system calculates the probability (certainty factor) of an input protein to be localized at each candidate site. One of the difficultiesof our system is that, since it has many adjustable parameters, optimization of them toa given training data is difficult. Therefore, incorporation of recent knowledge into the systemhas not been easy. We present here a simple scheme for assigning certainty-factor parameters with a given reasoning tree. Since the size of training data, i. e., sequences of known localization sites, is not large inmost cases, we must suppress the number of parameters as possible. In this case, use of ourknowledge on the reasoning flow is favorable. Such a flow can be organized into a reasoningtree, in which an input flux is divided into thinner flows on a step-by-step basis according tosome characteristic values calculated from the input sequence (Fig. 1). Its final outputs areflows corresponding to candidate localization sites. In this stage, the amount of each flow can beinterpreted as the corresponding certainty factor. Thus, the problem is how to find appropriate functions that transform a characteristic value at each step in an optimized performance forthe classification of training data. We used the following formula for that function: F_p (x_p (i)) =1/1+exp (-10×(x_p (i)-b_p)) where x_p (i) represents a characteristic value of a sequence i at the step p, e.g., propensitythat the input sequence i encodes a membrane protein, and b_p is a threshold value which isobtained by the criterion that can classify the training data at step p with least mistakes.The certainty factor for localizing a candidate site is thus calculated as a probability to choosethe corresponding path, e.g., the certainty factor for a protein i to localize at the site #3 isF₁ (i)×F₂ (i)×(1-F₄ (i)) in Fig. 1. To test the validity of our model, we prepared 156 sequences of Bacillus subtilis whoselocalization sites are the prediction results of PSORT. The cross-validation test showed rathergood result. Thus, although there is no theoretical proof that our model always gives goodresults, it will be hopefully used for future improvement of PSORT. Moreover, because of itssimplicity, this method may be generally used to interpret unknown sequence data with the latest knowledge of molecular cell biology.
Machine Learning and Discovery for Bloinformatics: Introduction. Peer-reviewed

Satoru Miyano, Ayumi Shinohara

27th Annual Hawaii International Conference on System Sciences (HICSS-27), January 4-7, 1994, Maui, Hawaii, USA　111-112　1994
Publisher: IEEE Computer Society
Complexity of Computing Generalized VC-Dimensions. Peer-reviewed

Ayumi Shinohara

Machine Learning: ECML-94, European Conference on Machine Learning, Catania, Italy, April 6-8, 1994, Proceedings　415-418　1994
Publisher: Springer
DOI： 10.1007/3-540-57868-4_87 　
Refutably Probably Approximately Correct Learning. Peer-reviewed

Satoshi Matsumoto, Ayumi Shinohara

Algorithmic Learning Theory, 4th International Workshop on Analogical and Inductive Inference, AII '94, 5th International Workshop on Algorithmic Learning Theory, ALT '94, Reinhardsbrunn Castle, Germany, October 10-15, 1994, Proceedings　469-483　1994
Publisher: Springer
DOI： 10.1007/3-540-58520-6_84 　
Finding alphabet indexing for decision trees over regular patterns: An approach to bioinformatical knowledge acquisition

Shinichi Shimozono, Ayumi Shinohara, Takeshi Shinohara, Satoru Miyano, Satoru Kuhara, Setsuo Arikawa

Proceedings of the Annual Hawaii International Conference on System Sciences　1　763-772　1993
Publisher: IEEE Computer Society
DOI： 10.1109/HICSS.1993.270664 　

ISSN： 1530-1605
Running Learning Systems in Parallel for Machine Discovery from Sequences

Shinohara Ayumi, Miyano Satoru, Arikawa Setsuo, Shimozono Shinichi, Uchida Tomoyuki, Kuhara Satoru

GI　4　74-83　1993
Publisher: Japanese Society for Bioinformatics
DOI： 10.11234/gi1990.4.74 　

ISSN： 0919-9454

More details Close

We have developed a machine learning system BONSAI which gets positive and negative examples as inputs and produces a pair of a decision tree over regular patterns and an alphabet indexing as a hypothesis. This paper proposes two applications of BONSAI when we can run multiple BONSAI systems in parallel. The one is to classify given examples which are coming from several different unknown classes. The process of solving the problem consists of multiply spawned BONSAI systems, each of which tries to find a decision tree, an alphabet indexing and a group of examples. It will finally partition a hodgepodge of sequences into a small number of disjoint classes together with hypotheses explaining these classes accurately. The other is to find a good sample of a concept. Though the main interest of applying the BONSAI system is to discover good hypotheses, it is equally interesting to find a small set of examples from which a good hypothesis is made. We present a method for solving this problem by combining a strategy in genetic algorithms with multiply running BONSAI systems.
Complexity of Computing Vapnik-Chervonenkis Dimension. Peer-reviewed

Ayumi Shinohara

Algorithmic Learning Theory, 4th International Workshop, ALT '93, Tokyo, Japan, November 8-10, 1993, Proceedings　279-287　1993
Publisher: Springer
DOI： 10.1007/3-540-57370-4_54 　
A MACHINE DISCOVERY FROM AMINO-ACID-SEQUENCES BY DECISION TREES OVER REGULAR PATTERNS Peer-reviewed

S ARIKAWA, S MIYANO, A SHINOHARA, S KUHARA, Y MUKOUCHI, T SHINOHARA

NEW GENERATION COMPUTING　11　(3-4)　361-375　1993

DOI： 10.1007/BF03037183 　

ISSN： 0288-3635
ALGORITHMIC LEARNING-THEORY WITH ELEMENTARY FORMAL SYSTEMS Peer-reviewed

S ARIKAWA, S MIYANO, A SHINOHARA, T SHINOHARA, A YAMAMOTO

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS　E75D　(4)　405-414　1992/07

ISSN： 0916-8532
Knowledge Acquisition from Amino Acid Sequences by Decision Trees and Indexing

Miyano Satoru, Shinohara Ayumi, Arikawa Setsuo, Shimozono Shinichi, Shinohara Takeshi, Kuhara Satoru

GI　3　69-72　1992
Publisher: Japanese Society for Bioinformatics
DOI： 10.11234/gi1990.3.69 　

ISSN： 0919-9454

More details Close

We present a machine learning system for knowledge acquisition that produces hypotheses from positive and negative examples, and report some experiments on protein data using the PIR and Gen Bank databases. This learning system is developed with an algorithmic learning theory for decision trees over regular patterns, which we newly devised for this research. In the experiments on transmembrane domain identification, the system discovered very simple hypotheses with very high accuracy from a small number of positive and negative examples. These hypotheses show that negative motifs, namely, motifs of negative data, play a key role in such classification. In these experiments, we classified 20 symbols of amino acid residues into 3 categories according to the hydropathy indices due to Kyte and Doolittle. We call such transformation of symbols an indexing. We observed that the indexing by the hydropathy indices is important in making the learning algorithm efficient and accurate. This observation inspired us with a desire to discover such an indexing itself just by a learning algorithm. We succeeded in it by combining the above learning algorithm and the local search technique for finding good indexings. We also report some experiments on signal peptides. We have implemented this learning system, called BONSAI, which shall be presented at the Computer Demonstration Session during this workshop.
A MACHINE DISCOVERY FROM AMINO-ACID-SEQUENCES BY DECISION TREES OVER REGULAR PATTERNS Peer-reviewed

S ARIKAWA, S KUHARA, S MIYANO, Y MUKOUCHI, A SHINOHARA, T SHINOHARA

FIFTH GENERATION COMPUTER SYSTEMS 1992, VOLS 1 AND 2　618-625　1992
Which classes of elementary formal systems are polynomial-time learnable.

Satoru Miyano, Ayumi Shinohara, Takeshi Shinohara

Algorithmic Learning Theory(ALT)　139-150　1991
Publisher: Ohmsha
Machine Discovery of a Negative Motif

Arikawa Setsuo, Kuhara Satoru, Miyano Satoru, Shinohara Ayumi, Shinohara Takeshi

GI　2　62-65　1991
Publisher: Japanese Society for Bioinformatics
DOI： 10.11234/gi1990.2.62 　

ISSN： 0919-9454
A Text Database Management System SIGMA and Its Applications to Analyzing the Genetic Information

Shinohara Takeshi, Arikawa Setsuo, Kuhara Satoru, Miyahara Tetsuhiro, Inoue Hitoshi, Shinohara Ayumi, Uchida Tomoyuki

GI　2　28-32　1991
Publisher: Japanese Society for Bioinformatics
DOI： 10.11234/gi1990.2.28 　

ISSN： 0919-9454

More details Close

SIGMA is a general purpose text database management system and is now working at the Computer Center, Kyushu University for large scale full text databases, natural language analysis and bibliographic retrievals. SIGMA searches a 2MB file in 1 CPU second or in 3 seconds even if disk accessing time is included. Since Genetic information databases are of complicated formats and contain very long sequence information, converting them to full text databases and retrieving them by SIGMA system is useful for analyzing the Genetic Information. We have converted the text files of Genetic Sequence Data Bank (Genbank) and Protein Sequence database (PIR) and efficiently maintained and retrieved the converted files as full text databases.
More About Learning Elementary Formal Systems. Peer-reviewed

Setsuo Arikawa, Takeshi Shinohara, Satoru Miyano, Ayumi Shinohara

Nonmonotonic and Inductive Logic, Second International Workshop, Reinhardsbrunn Castle, Germany, December 2-6, 1991, Proceedings　107-117　1991
Publisher: Springer
DOI： 10.1007/BFb0030388 　
Teachability in Computational Learning. Peer-reviewed

Ayumi Shinohara, Satoru Miyano

Algorithmic Learning Theory, First International Workshop, ALT '90, Tokyo, Japan, October 8-10, 1990, Proceedings　247-255　1990
Publisher: Springer/Ohmsha
TEACHABILITY IN COMPUTATIONAL LEARNING Peer-reviewed

A SHINOHARA, S MIYANO

NEW GENERATION COMPUTING　8　(4)　337-347　1990

DOI： 10.1007/BF03037091 　

ISSN： 0288-3635

Show all ︎Show first 5

Misc. 93

実用的なサイバー救助犬スーツの開発-サイバー救助犬スーツの熱対策・傾き対策・軽量化・小型化-

西野間洋之, 大野和則, 大野和則, 濱田龍之介, 星達也, BEOKHAIMOOK Chayapol, 篠原歩, 田所諭

日本機械学会ロボティクス・メカトロニクス講演会講演論文集(CD-ROM)　2019　2019

ISSN： 2424-3124
慣性センサに基づく災害救助犬の行動推定・可視化システムの開発

三浦樹, 川又周, 清水俊汰, 五十嵐祐貴, 中鉢魁三郎, 成定真太郎, 益子直, 山口竣平, 星達也, 濱田龍之介, 吉仲亮, 大野和則, 篠原歩, 徳山豪

日本機械学会ロボティクス・メカトロニクス講演会講演論文集(CD-ROM)　2018　ROMBUNNO.2A2‐K01　2018/06/01
「手応え関数」の自動生成に基づく自律分散制御則の設計~一次元這行運動を用いた検証~

佐藤光暁, 脇本竜, 加納剛史, 篠原歩, 石黒章夫

日本機械学会ロボティクス・メカトロニクス講演会講演論文集(CD-ROM)　2018　ROMBUNNO.1P1‐D18　2018/06/01
Query Learning of Residual Symbolic Automata

Chubachi, K, Diptarama, H, Yoshinaka, R, Shinohara, A

Work in Progress Track, ICGI 2018　2018
慣性センサに基づく災害救助犬の行動推定

成定真太郎, 益子直, 清水俊汰, 大堀優, 菅原啓介, 佐久間俊平, 佐藤市也, 上木庸平, 濱田龍之介, 山口竣平, 星達也, 大野和則, 吉仲亮, 篠原歩, 徳山豪

日本機械学会ロボティクス・メカトロニクス講演会講演論文集(CD-ROM)　2017　ROMBUNNO.2A1‐Q04-Q04　2017/05/09
Publisher: The Japan Society of Mechanical Engineers
DOI： 10.1299/jsmermd.2017.2A1-Q04 　

More details Close

We propose an underlying system that can infer and visualize search and rescue (SAR) dogs' behavior. The system is aimed at identifying "run", "walk", "stop", "sniff" and "bark" behaviors of SAR dogs robustly from inertial sensors data, and visualizing the results for the users. In the system, we apply Short-Time Fourier Transform (STFT) to the sensors data, and use a random forest algorithm for learning investigation activities of SAR dogs. We performed an experiment on our system and got the results that some behaviors can be identified precisely. We also developed an on-line visualization system for streaming data of behavior probabilities.
Longest Common Subsequence Problem for Numerical Sequences by using Order-Isomorphic-Substrings

栗原理聡, 成澤和志, 篠原歩

電子情報通信学会技術研究報告　115　(510(COMP2015 37-39))　11‐20-20　2016/03/07
Publisher: 電子情報通信学会
ISSN： 0913-5685
順序保存カーネルを用いた時系列データ分類

柏葉祐輝, 成澤和志, 篠原歩

人工知能学会人工知能基本問題研究会資料　99th　1‐6　2016/01/20
Generalization of Efficient Implementation of Compression by Substring Enumeration Finite Alphabet and Explicit Phase Awareness

佐久間俊平, 成澤和志, 篠原歩

電子情報通信学会技術研究報告　115　(205(COMP2015 16-21))　13-20　2015/08/25

ISSN： 0913-5685
順序保存符号化n‐gramの高速な出現頻度計算手法

佐藤雄介, 成澤和志, 篠原歩

情報処理学会研究報告(Web)　2015　(AL-151)　VOL.2015-AL-151,NO.1 (WEB ONLY)-8　2015/01/06
Publisher: 一般社団法人情報処理学会
ISSN： 0919-6072
Memory-Efficient Indexing Structure for Permuted Pattern Matching on Multi-Track Strings

桂敬史, 大友雄平, 成澤和志, 篠原歩

電子情報通信学会技術研究報告　114　(199(COMP2014 15-24))　1-8　2014/08/26

ISSN： 0913-5685
On the minimum consistent DFA problem for prefix samples

上埜かおり, 下薗真一, 成澤和志, 篠原歩

電子情報通信学会技術研究報告　113　(371(COMP2013 38-59))　115-122　2013/12/13

ISSN： 0913-5685
Sample Complexity Reduction in Reinforcement Learning by Transferred Transition and Reward Probability

小國晃太, 成澤和志, 篠原歩

電子情報通信学会技術研究報告　113　(286(IBISML2013 36-66))　139-146　2013/11/05

ISSN： 0913-5685
Extension of Generalized Tic-Tac-Toe: p stones for one move

19-26　2013/11/01
Efficient Algorithm and Coding for Higher-Order Compression

矢口和也, 小林直樹, 篠原歩

電子情報通信学会技術研究報告　113　(252(COMP2013 32-37))　13-20　2013/10/11
Publisher: The Institute of Electronics, Information and Communication Engineers
ISSN： 0913-5685

More details Close

Higher-order compression is a scheme for compressing data in the form of functional programs that generate the data.This compression scheme can be viewed a generalization of grammar-based compression, and retains its advantage that the compressed data can be manipulated without decompression.Furthermore, the higher-order compression can achieve a high compression ratio and also discover patterns that cannot be found by traditional grammar-based compression.In this paper, we propose an efficient algorithm and a bit-coding scheme for higher-order compression and evaluate their effectiveness through experiments.
SATソルバを用いた学位論文審査の時間割作成システムの試作

奥田遼介, 小松智希, 石黒裕也, 柏葉祐輝, 成澤和志, 篠原歩

日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集　2013　232-233　2013/09/11
Publisher: 公益社団法人日本オペレーションズ・リサーチ学会
ISSN： 1883-1893
Analysis of the Maximum Sum of Exponents of Runs in Strings

草野一彦, 奥田遼介, 成澤和志, 篠原歩

電子情報通信学会技術研究報告　113　(14(COMP2013 1-8))　17-24　2013/04/17
Publisher: The Institute of Electronics, Information and Communication Engineers
ISSN： 0913-5685

More details Close

A run in a string is a periodic substring which can not be extendable neither to the left nor right with the same period. In this paper, we focus on the sum of exponents of runs. We compute exact values of the maximum sum σ_2(n) of exponents of runs in a binary string of length n, up to n=57, by an efficient pruning algorithm. The current best lower bound for the maximum sum σ(n) of exponents in a string of length n is 2.03525n. We show a new lower bound 2.03696n, which is discovered by exhaustively searching morphisms generating strings.
Approximate Permuted Pattern Matching and Indexing Structure for Multi-Track Data

大田裕之, 桂敬史, 成澤和志, 篠原歩

電子情報通信学会技術研究報告　113　(14(COMP2013 1-8))　9-16　2013/04/17
Publisher: The Institute of Electronics, Information and Communication Engineers
ISSN： 0913-5685

More details Close

A multi-track data is a multi-set of sequences. The permuted pattern matching problem is, given a multi-track text and a multi-track pattern, to find positions that the pattern occurs. We consider the approximate permuted pattern matching problem on numeric multi-tracks with respect to the Euclidean distance. For the problem, we propose a new indexing structure called LoFT, and construct a probabilistic pattern matching algorithm utilizing LoFT.
Constructing Position Heaps for Various Pattern Matching

大友雄平, 成澤和志, 篠原歩

電子情報通信学会技術研究報告　112　(340(COMP2012 43-51))　7-14　2012/12/03

ISSN： 0913-5685
Implementation of the Process Virtual Machine for Embedded Environment and its Application to ET Robocon.

奥田遼介, 成澤和志, 篠原歩

電気学会制御研究会資料　CT-12　(24.26-29)　9-14　2012/12/01
Publisher: 電気学会
Validation of Strategies for Bonus Stages in ET Robocon by Using SATORI2, An Automated Test System of Real Robots.

大井雄介, DIPTARAMA, 奥田遼介, 桂敬史, 成澤和志, 篠原歩

電気学会制御研究会資料　CT-12　(24.26-29)　15-20　2012/12/01
Publisher: 電気学会
Pattern matching on compressed text using smaller space

相原高雄, 篠原歩, 成澤和志

電子情報通信学会技術研究報告　112　(272(COMP2012 34-42))　17-24　2012/10/24
Publisher: The Institute of Electronics, Information and Communication Engineers
ISSN： 0913-5685

More details Close

In this paper, we propose a randomized algorithm for pattern matching on strings represented by straight-line programs (SLPs). Using the equivalence checking algorithm presented by Schmidt-Schauss and Schnitger, we realize FirstMismatch (a function which returns the first position at which a nonterminal of text and a nonterminal of pattern have different symbols, when comparison is started at a given position) in a way that is different from Miyazaki's. Then we use Miyazaki's algorithm to solve the problem. Our algorithm runs in O(n(n log N+m log M)log M) time using O(n log N+m log M) space, where n and m are the sizes of the SLPs which represent the text and pattern respectively, while N and M are the lengths of the decompressed text and pattern respectively. Our algorithm is slower than the fastest one known today, but uses smaller space. Therefore it is effective when only limited space is available.
Permuted Pattern Matching and Indexing Structure for Multi-Track Strings

桂敬史, 成澤和志, 篠原歩, 坂内英夫, 稲永俊介

電子情報通信学会技術研究報告　112　(199(COMP2012 26-33))　1-8　2012/08/27

ISSN： 0913-5685
Effective algorithm for decision making on hand-composing game

小松智希, 成澤和志, 篠原歩

情報処理学会研究報告(CD-ROM)　2012　(2)　ROMBUNNO.GI-28,NO.8　2012/08/15

ISSN： 2186-2583
覆面算を解析するためのオートマトン理論的アプローチ

遠藤洋, 成澤和志, 篠原歩

情報処理学会シンポジウム論文集　2011　(6)　54-61　2011/10/28

ISSN： 1344-0640
イベント列データにおけるVLDCエピソード生成モデル

棚橋広亮, 成澤和志, 篠原歩

人工知能学会人工知能基本問題研究会資料　82nd　63-68　2011/07/25
実ロボットの自律学習を支援する統合分析環境:SATORI

斎藤淳哉, 桂敬史, 一井宏次, 伊東裕二, 可児輝之, 棚橋広亮, 成澤和志, 篠原歩

人工知能学会人工知能基本問題研究会資料　82nd　37-42　2011/07/25
DS-1-12 Runs Structure in Strings

Matsubara Wataru, Shinohara Ayumi

Proceedings of the IEICE General Conference　2011　(1)　"S-23"-"S-24"　2011/02/28
Publisher: The Institute of Electronics, Information and Communication Engineers
文字列に含まれる連構造

松原渉, 篠原歩

電子情報通信学会大会講演論文集　2011　S.23-S.24　2011/02/28

ISSN： 1349-1369
A hypothesis verification strategy for Regression tree analysis of Semiconductor Yield

津田英隆, 白井英大, 寺邊正大, 橋本和夫, 篠原歩

電気学会情報システム研究会資料　IS-10　(73-75.77-82)　11-17　2010/11/26
Picross 3D is NP-complete

2010　(12)　108-113　2010/11/12
信頼区間上限の不確実性サンプリングへの応用

斎藤淳哉, 篠原歩

情報科学技術フォーラム講演論文集　9th　(1)　209-214　2010/08/20
Publisher: Forum on Information Technology
非可逆圧縮を用いた類似性指標と画像検索への応用

坂内恒介, 成澤和志, BRODKORB Felix, 篠原歩

情報科学技術フォーラム講演論文集　9th　(1)　215-220　2010/08/20
Publisher: Forum on Information Technology
2GPUによるCubicセミ・ラグランジュ法の高速化

須藤郁弥, 坂内恒介, 本田耕一, 松田健護, 篠原歩

情報処理学会シンポジウム論文集　2010　(5)　135-136　2010/05/20

ISSN： 1344-0640
Transposition Invariant Fully Compressed Pattern Matching Algorithm

松原渉, 篠原歩

電子情報通信学会技術研究報告　110　(12(COMP2010 1-9))　39-45　2010/04/15
Publisher: The Institute of Electronics, Information and Communication Engineers
ISSN： 0913-5685

More details Close

Transposition invariant pattern matching is the problem of matching given text and pattern to find the occurrence in the case where the pattern may be transformed by applying renaming bijection. This paper studies an problem on compressed string in terms of straight line programs (SLPs). We show efficient algorithms for transposition invariant fully compressed pattern matching and some generalized problem.
Elementary Formal Systems with Nonterminal Symbols

小出智彦, 篠原歩

電子情報通信学会技術研究報告　110　(12(COMP2010 1-9))　47-54　2010/04/15
Publisher: The Institute of Electronics, Information and Communication Engineers
ISSN： 0913-5685

More details Close

Elementary Formal Systems (EFS) are logic programs over strings, and they are useful to describe various language classes in formal language theory. In this paper, we introduce nonterminal symbols to EFS and study their description powers.
文字列に含まれる繰り返し構造の頻度について

草野一彦, 篠原歩

情報処理学会全国大会講演論文集　72nd　(1)　1.409-1.410-410　2010/03/08
DS-1-6 Complexity of Teaching by a Limited Number of Examples

Kobayashi Hayato, Shinohara Ayumi

Proceedings of the IEICE General Conference　2010　(1)　"S-11"-"S-12"　2010/03/02
Publisher: The Institute of Electronics, Information and Communication Engineers
非終端記号を導入した基本形式体系の言語記述力について

小出智彦, 篠原歩

電子情報通信学会大会講演論文集　2010　(1)　S.9-S.10-9"-"S-10"　2010/03/02
Publisher: The Institute of Electronics, Information and Communication Engineers
ISSN： 1349-1369
例数制限付き教示の複雑さ

小林隼人, 篠原歩

電子情報通信学会大会講演論文集　2010　S.11-S.12　2010/03/02

ISSN： 1349-1369
Cell BEを用いた文字列の編集距離計算の高速化

須藤郁弥, 篠原歩

情報処理学会シンポジウム論文集　2009　(5)　98-99　2009/05/21

ISSN： 1344-0640
文字列の繰り返し構造の平均解析 (理論計算機科学の深化と応用)

草野一彦, 松原渉, 石野明, 篠原歩

数理解析研究所講究録　1649　181-188　2009/05
Publisher: 京都大学
ISSN： 1880-2818
例数制限付き教示の複雑さ (理論計算機科学の深化と応用)

小林隼人, 篠原歩

数理解析研究所講究録　1649　165-172　2009/05
Publisher: 京都大学
ISSN： 1880-2818
置換のランク付けに対する$O$($n$log log$n$)ビット領域の線形時間アルゴリズム (理論計算機科学の深化と応用)

須藤郁弥, 篠原歩

数理解析研究所講究録　1649　173-180　2009/05
Publisher: 京都大学
ISSN： 1880-2818
連を多く含む文字列発見のための探索的手法 (理論計算機科学の深化と応用)

松原渉, 草野一彦, 坂内英夫, 石野明, 篠原歩

数理解析研究所講究録　1649　81-88　2009/05
Publisher: 京都大学
ISSN： 1880-2818
通信規約学習の拡張による協調精度の向上

葛西達也, 小林隼人, 篠原歩

情報処理学会全国大会講演論文集　71st　(2)　2.201-2.202-202　2009/03/10
An Algorithm to Test Square-Freeness of BSLP-Compressed Strings

松原渉, 稲永俊介, 篠原歩

電子情報通信学会技術研究報告　108　(443(COMP2008 54-62))　9-16　2009/02/23
Publisher: The Institute of Electronics, Information and Communication Engineers
ISSN： 0913-5685

More details Close

Balanced Straight line programs (BSLPs) is one of the most powerful and general compression schemes. An BSLP is a context-free grammar which generates only one string. This paper studies an problem on compressed string described in terms of BSLP. In order to process compressed strings efficiently (in polynomial time with respect to the compressed size), decompression is never feasible. We show efficient algorithm that testing square-freeness in O(max(n^2, nlog^2N)) time with O(n^2) space, where n and N are the size of a given compressed string and the corresponding decompressed string, respectively.
Cellスピードチャレンジ2008規定課題部門で用いた高速化手法

須藤郁弥, 本田耕一, 松田健護, 坂内恒介, 柴田悠希, 小林隼人, 石野明, 篠原歩

情報処理学会シンポジウム論文集　2008　(5)　13-14　2008/06/04

ISSN： 1344-0640
間引きを用いたパス技術の自律学習

小林隼人, 畑埜晃平, 石野明, 篠原歩

情報処理学会全国大会講演論文集　70th　(2)　2.209-2.210-210　2008/03/13
Polynomial time algorithms for computing longest common substring and all palindromes from compressed strings

松原渉, 稲永俊介, 石野明, 篠原歩, 中村智将, 橋本和夫

電子情報通信学会技術研究報告　107　(537(COMP2007 55-67))　55-62　2008/03/03
Publisher: The Institute of Electronics, Information and Communication Engineers
ISSN： 0913-5685

More details Close

Straight line programs (SLPs) is one of the most powerful and general compression schemes. An SLP is a context-free grammar which generates only one string. In order to process SLP efficiently (in polynomial time with respect to the compressed size) decompression is never feasible. This paper studies two problems on compressed strings described in terms of SLPs. One is to compute the length of the longest common substring of two given SLP-compressed strings, and the other is to compute all palindromes of a given SLP-compressed string. We show efficient algorithms that solve these problems in O(n^4 log n) time with O(n^3) space, ad in O(n^4) time with O(n^2) space, respectively, where n is the size of the input SLP-compressed strings.
Repetitions in the infinite n-bonacci word

佐々木崇人, 大崎嗣豊, 石野明, 篠原歩

電子情報通信学会技術研究報告　107　(24(COMP2007 1-10))　55-61　2007/04/19

ISSN： 0913-5685
間引きを用いたシュートモーション学習

小林隼人, 畑埜晃平, 石野明, 篠原歩

人工知能学会AIチャレンジ研究会　25th　52-57　2007
Acquisition of Swing Motion Skills by Real Robots

柳町修平, 大崎嗣豊, 小林隼人, 石野明, 篠原歩

人工知能学会人工知能基本問題研究会資料　62nd　17-22　2006/03/27
Publisher: 人工知能学会
スクリプト言語Luaを用いたロボカップ四足ロボットリーグシミュレータ

小林隼人, 井上淳, 石野明, 篠原歩

人工知能学会AIチャレンジ研究会　21st　20-25　2005
薬剤取り違え防止のための医薬品名類似性指標

今田結城, 竹田正幸, 篠原歩, 大谷寿一, 沢田康文

人工知能学会知識ベースシステム研究会資料　64th　165-170　2004/03/01
Publisher: 人工知能学会
Linear Time Algorithm for Text Compression by Longest-First Substitution

稲永俊介, 船本崇, 竹田正幸, 篠原歩

電子情報通信学会技術研究報告　103　(622(COMP2003 69-80))　29-36　2004/01/29

ISSN： 0913-5685
On the Length of the Minimum Solution of Word Equations in One Variable

馬場謙介, 鶴田聡士, 篠原歩, 竹田正幸

電子情報通信学会技術研究報告　103　(394(COMP2003 44-53))　65-69　2003/10/27

ISSN： 0913-5685
Pattern Matching over Compressed Texts: New Trend in Data Compression and Pattern Matching.

竹田正幸, 篠原歩

情報処理　43　(7)　763-769　2002/07/15
Publisher: Information Processing Society of Japan (IPSJ)
ISSN： 0447-8053
圧縮されたテキスト上のパターン照合－データ圧縮とパターン照合の新展開－

竹田正幸, 篠原歩

情報処理学会学会誌　43　(7)　763-769　2002/07
Publisher: Information Processing Society of Japan (IPSJ)
ISSN： 0447-8053
Fragmentary Pattern Matching : Complexity and Approximation Algorithms

HORI Hideaki, SHIMOZONO Shinichi, TAKEDA Masayuki, SHINOHARA Ayumi

IEICE technical report. Theoretical foundations of Computing　101　(431)　23-30　2001/11/09
Publisher: The Institute of Electronics, Information and Communication Engineers
ISSN： 0913-5685

More details Close

A fragmentary pattern is a multiset of non-empty strings, and it matches a string w if all the strings in it occur within any overlaps. We study some fundamental issues on computational complexity related the matching fragmentary patterns. We show that the fragmentary pattern matching problem is NP-complete, and the problem to find a fragmantary pattern common to two strings that maximizes the pattern score is NP-hard. Moreover, we propose a polynomial-time approximational algorithm for the fragmentary pattern matching, and show that it achieves a constant worst-case approximation ratio if either the strings in a pattern have the same langth, or the importance weights of strings in a pattern are proportional to their lengths.
Pattern Matching Algorithm for Balanced Straight-Line Programs.

平尾昌啓, 篠原歩, 竹田正幸, 有川節夫

電子情報通信学会論文誌 A　J84-A　(6)　722-730　2001/06/01
Publisher: The Institute of Electronics, Information and Communication Engineers
ISSN： 0913-5707
NReport on Data Search Methods in Biotechnology (2000, Patent Office of Japan).

熊谷健一, 塩原立也, 篠原歩, 菅原秀明, 高木利久, 中村春木, 深川正夫

バイオテクノロジー分野におけるサーチ手法に関する調査研究報告書平成12年度特許庁工業所有権制度問題調査報告書　114P　2001
Genome database. Figures of life stored in computers. No.5. Knowledge discovery from sequence data.

篠原歩, 宮野悟

BIT (Tokyo)　31　(11)　76-83　1999/11/01
Publisher: 共立出版
ISSN： 0385-6984
データ圧縮による文字列照合の高速化

柴田裕介, 喜田拓也, 竹田正幸, 篠原歩, 有川節夫

情報処理学会全国大会講演論文集　59th　(1)　1.175-1.176-176　1999/09/28
圧縮テキストに対する文字列照合のための統一的枠組み

喜田拓也, 柴田裕介, 竹田正幸, 篠原歩, 有川節夫

情報処理学会全国大会講演論文集　59th　(1)　1.177-1.178　1999/09/28
重み付き分類規則による保健データからのデータマイニング

高江徹, 近棟稔, 有村博紀, 篠原歩, 井上仁, 武谷俊一, 上園慶子, 川崎晃一

情報処理学会全国大会講演論文集　59th　(4)　4.311-4.312　1999/09/28
重み付きネットワークを用いた遺伝子発現ネットワークの発見 (文部省S)

篠原歩, 竹田正幸, 野田清志

ゲノムサイエンス:ヒトゲノム解析に基づくバイオサイエンスの新展開平成10年度 No.08283101　290-293　1999
Uniform Characterizations of Learnabilities via Polynomial Numbers of Queries.

林洋祐, 松本哲志, 篠原歩, 竹田正幸

情報処理学会全国大会講演論文集　57th　(2)　2.341-2.342　1998/10
Pattern Matching Algorithm in LZW Compressed Text.

喜田拓也, 竹田正幸, 篠原歩

情報処理学会全国大会講演論文集　57th　(1)　1.143-1.144　1998/10
Study of machine discovery system for region prediction. ( Ministry of Education S ).

篠原歩

ゲノムサイエンス:ヒトゲノム解析に基づくバイオサイエンスの新展開平成9年度 No.08283101　301-303　1998
Support of Knowledge Discovery by Computational Reasonings.

宮野悟, 篠原歩

蛋白質核酸酵素　42　(17)　3008-3013　1997/12

ISSN： 0039-9450
Development of a phase retrieval system shogi record database.

林洋祐, 石坂裕毅, 篠原歩

電気関係学会九州支部連合大会講演論文集　50th　222　1997/10
Implementation of string pattern matching algorithm for a Z-compression text.

喜田拓也, 竹田正幸, 宮崎正路, 篠原歩

電気関係学会九州支部連合大会講演論文集　50th　275　1997/10
Speeding up of the matching algorithm for a character string described by a straight line program.

宮崎正路, 篠原歩, 竹田正幸

電気関係学会九州支部連合大会講演論文集　50th　274　1997/10
On-Web-Teaching 2300 Students Information Processing and Computer Literacy at Kyushu University.

峯恒憲, 佐藤周行, 正代隆義, 広川佐千男, 有村博紀, 森雅生, 篠原歩, 竹田正幸

情報処理学会研究報告　97　(49(DD-7))　39-46　1997/05/23
Publisher: Information Processing Society of Japan (IPSJ)
ISSN： 0919-6072

More details Close

We are developing a Web system for the introductory course of programming and computer literacy. 2300 students take the course with this Web system at Kyushu University. Our main object of this system is to reappear our lecture in front of students in their private studies. Teaching how programs run is a hard problem to deal with in information processing educations. In order to deal with such a difficult subject easily, we propose a program animation compiler for assisting students to understand a motion of programs. This compiler systematically translates tiny Pascal programs into Java Applets. In this paper, we state our idea and future plans of the system.
Pattern Matching Algorithms on Compressed Strings.

篠原歩

電子情報通信学会大会講演論文集　1997　(Sogo Pt 6)　361-362　1997/03

ISSN： 1349-1369
Concept formation of organism information by machine learning and machine discovery.

篠原歩, 正代隆義

ゲノムサイエンス:ヒトゲノム解析に基づくバイオサイエンスの新展開平成8年度 No.08283101　281-283　1997
Implementation of matching algorithm on character string of shortening described.

宮崎正路, 篠原歩, 竹田正幸

電気関係学会九州支部連合大会講演論文集　49th　676　1996/10
Learnability of Subsequence Languages

MATSUMOTO Satoshi, SHINOHARA Ayumi

RIMS Kokyuroku　950　250-256　1996/05
Publisher: Kyoto University
ISSN： 1880-2818
Learnability of Ordered Binary Decision Diagrams

HIRATA Kouichi, SHINOHARA Ayumi, MATSUMOTO Satoshi

IEICE technical report. Theoretical foundations of Computing　95　(374)　37-44　1995/11/17
Publisher: The Institute of Electronics, Information and Communication Engineers

More details Close

Ordered binary decision diagrams (OBDDs, for short) represent Boolean functions as directed acyclic graphs. In this paper, we investigate the learnability of OBDDs. First, we show that OBDDs representing totally symmetric functions of n variables are polynomial-time learnable with at most n+1 equivalence queries alone, or just n+1 membership queries alone. Also we show that OBDDs representing the conjunction, or disjunction, of literals over n variables are polynomial-time learnable with at most TL equivalence queries alone. Hence, we can conclude that all of them are polynomial-time PAC-learnable with respect to n.
Polynomial-time Pattern-Matching Algorithm for Strings with Short Descriptions.

篠原歩, RYTTER W, KARPINSKI M

情報処理学会研究報告　95　(76(FI-38))　25-32　1995/07/28
Publisher: Information Processing Society of Japan (IPSJ)
ISSN： 0919-6072

More details Close

We investigate the time complexity of the pattern matching problem for strings which are succinctly described in terms of straight-line programs. Usually the strings of descriptive size n are of exponential length with respect to n. In our former work [6], we have developed O(n7) time pattern matching algorithm for strings with short descriptions. In this paper, we improve the time complexity : our new algorithm runs in O(n4 log n) time.
Refutably Probably Approximately Correct Learning.

松本哲志, 篠原歩

人工知能学会全国大会論文集　9th　81-84　1995/07
Parallel Machine Discovery System for Sequences-BONSAI Garden.

正代隆義, 宮野悟, LAPPE M, 内田智之, 岡崎威生, 篠原歩

情報処理学会全国大会講演論文集　50th　(3)　3.31-3.32　1995/03
Knowledge Acquisitiion from Amino Acid Sequences by Machine Learning System BONSAI

Shinichi Shimozono, Ayumi Shinohara, Takeshi Shinohara, Satoru Miyano, Satoru Kuhara, Setsuo Arikawa

Trans. Information Processing Society of Japan　35　(10)　2009-2018　1994/10/15
Publisher: Information Processing Society of Japan (IPSJ)
ISSN： 1882-7764

More details Close

We present a mahcine learning system, called BONSAI, for knowledge acquisition from positive and negative examples of strings, and report some experiments on protein data using the PIR and GenBank databases. This learning system is constructed with an algorithmic learning theory for decision trees over regular patterns, which is newly developed for this work. As a hypothesis, the system tries to find a pair of a classification of symbols called an alphabet indexing and a decision tree over regular patterns, which classifies given examples with high accuracy. Through the experiments, the system discovered very simple hypotheses that exhibit important knowledge about transmembrane domain and signal peptides.
BONSAI Garden: Knowledge Acquisition System from Amino Acid Sequences by Learning Algorithm.

宮野悟, 篠原歩, 内田智之, 久原哲, 下薗真一, 篠原武, 正代隆義, 有川節夫

情報処理学会研究報告　94　(69(AL-40))　41-47　1994/07/22
Publisher: Information Processing Society of Japan (IPSJ)
ISSN： 0919-6072

More details Close

We have developed a machine learning system BONSAI which gets positive and negative examples as inputs and produces a pair of a decision tree over regular patterns and an alphabet indexing as a hypothesis. We observed that the indexing by the hydropathy indices is important in making the learning algorithms efficient and accurate. We are also implementing a system BONSAI Garden, which runs several BONSAI systems in parallel, to acquire knowledge from a hodgepodge of data. Some experiments on the prototype shall be presented.
Special Issue: "Computation Complexiting in Artificial Intelligence". Computational Complexity of Machine Learning for Genome Informatics: Theory and Practice.

宮野悟, 篠原歩, 有川節夫

人工知能学会誌　9　(3)　350-357　1994/05

ISSN： 0912-8085
Parallel Knowledge Acquisition from Amino Acid Sequence Data by BONSAI Garden.

宮野悟, 正代隆義, LAPPE M, 内田智之, 岡崎威生, 篠原歩, 久原哲, 有川節夫

蛋白質の構造・機能予測　17-21　1994
BONSAI: Machine discovery system for genome data.

宮野悟, 篠原歩, 有川節夫, 久原哲, 下薗真一, 篠原武

日本生物物理学会年会講演予稿集　31st　S48　1993/09

ISSN： 0582-4052
BONSAI: A Machine Discovery System from Strings by Decision Trees and Indexings.

宮野悟, 篠原歩, 有川節夫, 下薗真一, 篠原武, 久原哲

人工知能学会全国大会論文集　7th　119-122　1993/07
Alphabet Indexing for Amino Acids by Learning Algorithm and its Experiments on Knowledge Acquisition from Protein Data.

宮野悟, 篠原歩, 有川節夫, 下薗真一, 篠原武, 久原哲

計算機科学研究報告　10　(10)　47-52　1993/03
Publisher: Kyushu University
ISSN： 0910-352X
Natarajan, B. K. : MACHINE LEARNING - A Theoretical Approach, Morgan Kaufmann Publishers (1991).

7　(6)　1118-1118　1992/11/01

ISSN： 0912-8085
Learnability of EFS and its Application for Identifying Transmembrane Domains.

有川節夫, 久原哲, 宮野悟, 篠原歩, 篠原武

情報処理学会研究報告　91　(74(FI-23))　23.1,1-8-8　1991/09/10

ISSN： 0919-6072
PAC-learning-Probably approximately correct learning.

篠原歩, 宮野悟

情報処理　32　(3)　257-263　1991/03
Publisher: オーム社
ISSN： 0447-8053
A theory of algorithmic teaching.

篠原歩, 宮野悟

人工知能学会人工知能基礎論研究会資料　9th　61-70　1990/01

Show all ︎Show first 5

Books and Other Publications 4

Encyclopedia of Bioinformatics

Japanese Society, for Bioinformatics

Kyoritsu Shuppan　2006/07
Encyclopedia of Artificial Intelligence

The Japanese, Society for Artificial Intelligence

Kyoritsu Shuppan　2005/12
Progress in Discovery Science : Final Report of the Japanese Discovery Science Project

Setsuo Arikawa, Ayumi Shinohara

Springer-Verlag　2002/04/08
Discovery Science : 4th International Conference, DS 2001

Klaus P. Jantke, Ayumi Shinohara

Springer-Verlag　2001/12/12

Research Projects 49

Data Compression: theoretical and practical approaches to the smallest grammar problem

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research (C)

Institution: Tohoku University

2021/04/01 - 2025/03/31
Refinement and Extension of Higher-Order Model Checking

Kobayashi Naoki

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research (S)

Institution: The University of Tokyo

2015/05/29 - 2020/03/31

More details Close

This research aimed to advance the theory of higher-order model checking and its applications. We have obtained good theoretical results, such as a pumping lemma for higher-order languages and the surprising connection between two kinds of higher-order model checking. We have also made progress in the applications of higher-order model checking, such as the big improvement in the efficiency of higher-order model checkers and program verification tools and in the class of program properties that can be verified, and a new technique for higher-order data compression using arithmetic coding.
Approach from learning theory toward understanding the limitations of computation

Takimoto Eiji, TSUDA Koji, CUTURI Marco

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area)

Institution: Kyushu University

2012/06/28 - 2017/03/31

More details Close

We made considerable achievements in bringing new insights into "computation", through the analysis of the complexity of learning problems. In the analysis of online prediction, we partially solved an important open problem, stating the equivalence between the complexity of online prediction and that of optimization. In the analysis of the complexity of hypothesis representation, we proposed a few decision problems defined on the discrete dynamical system, which is a generalization of recurrent neural networks. Our analysis suggests that the decision problems belong to an intermediate layer of the class of NP. In the analysis of learning grammars, we employs a breakthrough technique called the distributional learning and obtained many positive results in learning formal (graph) grammars. The distributional learning is a resume of designing learning algorithms by focusing on the relation of substrings/subgraphs and the structures surrounding them.
Development of e-learning system for university students

SHINOHARA Ayumi

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Challenging Exploratory Research

Institution: Tohoku University

2013/04/01 - 2016/03/31

More details Close

The goal of this project was to develop prototypes of e-learning system for university students, that is comfortably accessible from various mobile devices such as tablet PC and smartphones, mainly focused on the theory of automata and formal languages. We developed a system that interactively shows an essence of the pumping lemma for regular languages, and designed and implemented a puzzle game based on the behavior of finite automata. Moreover, we analyzed the computational complexity of finding minimum automaton that is consistent with given examples.
Higher-Order Model Checking and its Applications

Kobayashi Naoki, SHINOHARA Ayumi, IGARASHI Atsushi, UNNO Hiroshi, TERAUCHI Tachio, SUMII Eijiro, MATSUDA Kazutaka

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research (S)

2011/05/31 - 2016/03/31

More details Close

The main topic of this research project was higher-order model checking, which is an extension of model checking, a representative method for system verification. In 2009, Kobayashi, the leader of this project, has developed the first practical algorithm for higher-order model checking, and also shown that higher-order model checking is useful for program verification. This research project has been launched to extend his results. The major results include: the development of much faster higher-order model checkers, implementation of fully-automated tools for program verification, and applications to data compression (where data are compressed in the form of functional programs that generate them, and compressed data are manipulated without decompression).
Knowledge discovery based on data compression: a study in theory and practice

SHINOHARA AYUMI, NARISAWA Kazuyuki

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research (B)

Institution: Tohoku University

2011/04/01 - 2015/03/31

More details Close

We study various topics concerning with data compression and knowledge discovery, from both theoretical and practical points of view. We made several contributions on compressed string processing, string matching, combinatorial properties on the repetitive structures in strings, multi-agent system, computational learning theory, reinforcement learning, game analysis, and practical applications.
Development of A Research Support System for Stringology

SHINOHARA Ayumi

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Challenging Exploratory Research

Institution: Tohoku University

2011 - 2012

More details Close

We developed a research support system for Stringology, that deals with algorithms and data structures used for string processing. We designed and built a prototype of an online encyclopedia of strings, where we explained various fundamental properties, and typical algorithms and data structures on strings. We also showed an indexing structures that is suitable for parameterized pattern matching. We implemented efficient algorithms to find strings containing many runs, which are maximal repetitions instrings.
Foundational technology for light-weight XML-DBMS based on very fast compressed data stream processing

TAKEDA Masayuki, SHINOHARA Ayumi, BANNAI Hideo, TAKIMOTO Eiji, SAKAMOTO Hiroshi, HATANO Kohei, INENAGA Syunsuke

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research (B)

Institution: Kyushu University

2010 - 2012

More details Close

In this project we aimed to establish a foundational technology for lightweight DBMS and successfully developed:(1) Fast and lightweight online grammar based compression algorithms.(2) q-gram mining algorithms over compressed data.(3) Efficient filtering algorithms for XML data streams.Additionally, we tackled some problems such as efficient pattern enumeration, data classification, online prediction, which will be intelligent data processing primitives of DBMS.
A study on knowledge discovery based on data compression

SHINOHARA Ayumi

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research (B)

Institution: Tohoku University

2008 - 2010

More details Close

We studied various topics concerning with data compression and knowledge discovery, from both theoretical and practical points of view. We proposed a new similarity measure based on lossy compression, and analyzed its properties. We made several contributions on compressed string processing, combinatorial properties on the number of runs in strings, formal language theory, multi-agent system, computational learning theory, game analysis, and practical applications.
Key Technology for XML DB in Embedded Device Based on Efficient Compressed Pattern Matching

TAKEDA Masayuki, SAKAMOTO Hiroshi, BANNAI Hideo, BABA Kensuke, INENAGA Shunsuke, SHINOHARA Ayumi, ISHINO Akira

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research (B)

Institution: Kyushu University

2007 - 2009

More details Close

Standard RDB technique does not perform well in embedded device because of less amount of memory and/or disk storage. Based on our technique of very fast compressed pattern matching, we developed key technique for XML-DB running in embedded devices such as smart phones.
A novel therapeutic approach for heart failure with transcriptomic analysis and in vivo imaging.

NAKAYAMA Masaharu

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research (C)

Institution: Tohoku University

2007 - 2008
Development of efficient knowledge discovery systems for large semistructured data

OKAMOTO Seishi, TAKEDA Masayuki, SHINOHARA Ayumi, KIDA Takuya, SAKAMOTO Hiroshi, HIRATA Kouichi

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research (A)

Institution: FUJITSU LABORATORIES LTD.

2005 - 2007

More details Close

By the rapid progress of Internet and Web service technologies, a new kind of massive data called semistructured data emerged, where a semistructured data is a collection of weakly structured electronic data such as Web pages and XML documents. In this research project, we studied efficient knowledge discovery systems for large semistructured data. First we studied theoretical foundations of learning and discovery for semistructured data. One of our main contributions is on kernels for trees. We introduced a new kernel function for labeled ordered trees and showed a hardness result in designing tree kernels for more general labeled trees(JSAI Best Paper Award in 2006). Another important one is on episode mining. We showed that an episode is parallel-free if and only if it is serially constructive. Next, we studied practical processing methods for semistructured data such as pattern matching, text compression, and index structures. Main contributions are as follows We devised efficient matching algorithms for path patterns based on the one-way sequential processing. These algorithms run 2 - 6 times faster and 6 times space-efficient in comparison with XMLTK. We also proposed an efficient index structure for the fast reachability test on directed graphs and implemented it(DEWS2007 BestPaper Award). Furthermore, we developed a new compressed pattern matching(CPM) algorithm that improves both the compression ratio and the search time ratio in comparison with a BPE type CPM algorithm. Finally, we applied the theoretical and practical results in this project to knowledge discovery systems. We demonstrated that these applications work effectively in various areas such as bioinformatics, pharmacy, music, traffic, and security.
非明示的表現に対するアルゴリズムの開発

篠原歩, 竹田正幸, 下薗真一, 坂本比呂志, 石野明

Offer Organization: 日本学術振興会

System: 科学研究費助成事業

Category: 特定領域研究

2004 - 2007

More details Close

本研究は,非明示的に表現されたオブジェクトに対するアルゴリズムの開発とその計算量の解析を行うことを目的し,また同時に,効率のよいアルゴリズムの開発に適した非明示的な表現法を文字列やグラフなどの離散構造を対象として研究を展開してきた. 具体的には,直線的プログラムとして圧縮表現された文字列を対象として,繰り返し構造や共通部分を検出する問題に取り組んだ.直線的プログラムは,文字列の連結を基本命令とした代入式の列であり,種々の文法圧縮,辞書式圧縮を抽象化したものである.もしもこの直線的プログラムからもとの文字列を陽に展開してしまうと,その長さは指数的に長くなりうるため,決して多項式時間で処理を行うことができない.我々は文字列に内在する組み合わせ構造や周期に着目することにより,圧縮文字列に含まれる回文構造の検出や,最大共通部分文字列の計算を多項式時間で行うアルゴリズムを開発した. また,漸化式として表される文字列の性質を調べた.隣接2項の漸化式で表されるフィボナッチ文字列を一般化し,隣接n項の漸化式でn-ボナッチ文字列を定義した.本研究では,任意のn≧2に対して,無限n-ボナッチ文字列における第k項目の有限n-ボナッチ文字列の最大連続出現数はk→∞のとき2+1/(φ(n)-1)に収束することを証明した.ここに,φ(n)はn-ボナッチ定数であり,特にφ(2)=(1+√<5>)/2は黄金比として知られている.さらに,nを増加させると,最大連続数はちょうど3に近づくことを示した.
Network Analysis from microarray data

KUHARA Satoru, TASHTO Kousuke, ONISHI Sadanori, MARUYAMA Osamu

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research on Priority Areas

Institution: Kyushu University

2005 - 2005

More details Close

Microarray techniques provide new insights into molecular classification of cancer types, which is critical for cancer treatments and diagnosis. Recently, an increasing number of supervised machine learning methods have been applied to cancer classification problems using gene expression data. Support vector machines (SVMs), in particular, have become one of the most effective and leading methods. However, there exist few studies on the application of other kernel methods in the literature. We apply a kernel subspace (KS) method to multiclass cancer classification problems, and assess its validity by comparing it with multiclass SVMs. Our comparative study using seven multiclass cancer datasets demonstrates that the KS method has high performance that is comparable to multiclass SVMs. Furthermore, we propose an effective criterion for kernel parameter selection, which is shown to be useful for the computation of the KS method. Microarrays pose a great challenge on the data analysis, because the number of genes often exceeds tens of thousands, whereas the number of samples available is at most a few hundred. In microarray data analysis, gene selection has been a central issue in recent years. Gene selection plays several important tasks. If it is possible to identify a small subset of biological relevant genes, it may provide insights into understanding the underlying mechanism of a certain biological phenomenon. In general, gene selection can be performed in different manners: the filter and wrapper approaches. We propose a new filter approach to gene subset selection for kernel-based methods. Our major goal is to enhance the performance of kernel-based classifiers without resorting to the wrapper approach. This can be realized by direct performing classification in the same feature space. It is different from the conventional filter approach combined with kernel-based classifier, where gene subset selection is performed in input space. We show that several well-known class separability criteria can be kernelized. Gene subset selection is performed based on the kernelized criteria. Our strategy is assessed by combining it with three kernel-based classifiers, from simple to advanced ones. We apply it to cancer classification problems on acute lymphoblastic leukemia and demonstrate validity of our proposed strategy by comparing it with several methods.
医薬品の商標名類似度と処方関連度に基づく投薬ミス防止システム

竹田正幸, 篠原歩, 澤田康文, 大谷壽一, 坂内英夫, 畑埜晃平

Offer Organization: 日本学術振興会

System: 科学研究費助成事業

Category: 萌芽研究

Institution: 九州大学

2004 - 2005

More details Close

平成17年度は,以下の4項目について研究した. (1)薬名間の類似性指標の設計(竹田,坂内) 前年度に引き続き,薬名間の類似度を定量化する指標を設計した.各パラメータを決定するため,研究室現有のタキストスコープ装置を用いて視覚および聴覚に関する知覚誤りの実験を行った.得られたデータに機械学習アルゴリズムを適用しパラメータの学習を行った. (2)類似性指標の検証(澤田) 日本薬剤師会などから報告されている「取り違え事例」(日本薬剤師会雑誌53(Sup 4):60-63,2001)や,澤田らがインターネット上に運営している薬剤師間コミュニティーサイト(薬学雑誌122:185-192,2002)に寄せられた事例の医薬品等をもとに,(1)の類似性指標の妥当性を検証した. (3)類似薬名検索方式の開発(篠原,竹田) (1)(2)の成果をもとに,与えられた医薬品名に対して高い類似度を示す医薬品を,医薬品データベース中から高速に検索するためのアルゴリズムを開発した.これを,WS上に実装し,その性能を評価した. (4)処方関連度辞書の構築(大谷,畑埜) 医薬品の処方学的関連の度合を数量化した医薬品処方関連度辞書の構築を目指し,大量の処方箋データからのデータマイニング方式について検討した.
最適パターン発見に基づく大規模半構造データからの知的情報獲得システムの開発

トーマスツォイクマン, 有村博紀, 坂本比呂志, 篠原歩, 下薗真一, 湊真一, 喜田拓也, 竹田正幸

Offer Organization: 日本学術振興会

System: 科学研究費助成事業

Category: 特定領域研究

Institution: 北海道大学

2004 - 2005

More details Close

本研究は,大量のウェブページやXML等の大規模半構造データからのデータマイニング(ウェブマイニング)に基づき,大量のデータ解析を対話的に支援する効率的なツールとして,従来の情報検索システムを超えた新しい情報アクセスシステムの実現方式を明らかにすることを目標としている.その鍵になる技術として,最適パターン発見を木やグラフ構造に拡張し,計算量理論と計算学習理論の最新の成果を援用しながら,半構造データに対する頑健かつ高速な最適化パターン発見アルゴリズムの開発に取り組んだ. 平成17年度は,初年度から昨年度までの研究成果と統合し,最適半構造マイニングのプロトタイプシステム構築を目指した.研究項目としては,有用な情報源の発見,特徴的なパターンの発見,情報の抽出の3つの情報獲得問題に加えて,昨年度から新たに研究を開始した知識索引問題について取り組んだ.今年度得られた具体的な結果のうち主要なものは以下のとおりである. (1)大規模なトランザクションデータによく見られる疎な組み合わせ集合データを効率よく扱うことのできるデータ構造であるZBDD(Zero-suppress BDD)をベースに,その構造の元で重み付き積和集合を計算可能なZBDDパッケージツールVSOP(Valued Sum-Of-Products)の開発を推し進め,頻出するパターン集合を表現するZBDDを単純直交分解する機能を追加した.これにより,そのデータに内包された意味的構造を自動抽出することが可能になった.(湊) (2)パターン発見アルゴリズムによる分類・予測の長期的ふるまいに関する理論保証を与えることに成功した.(ツォイクマン) (3)系列データからの極大モチーフパターンを効率よく枚挙するアルゴリズムを得た.(有村:H13-H16代表) (4)Arc構造付きテキストに対する高速なパターン照合アルゴリズムを得た.(喜田)
Development of efficient machine discovery system based on data compression and pattern matching

TAKEDA Masayuki, SHINOHARA Ayumi, SAKUMOTO Hiroshi, SUGIMOTO Noriko, ISHINO Akira, NANRI Tomoko

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research (B)

Institution: KYUSHU UNIVERSITY

2003 - 2005

More details Close

We studied the following three items to build efficient machine discovery systems. (1)Text compression and pattern matching. We focused on grammar-based compression and develop efficient compression algorithms. Using them we addressed the compressed pattern matching problem and obtained efficient algorithms. (2)Time-efficient processing of text and semi-structured text. We developed text index structures to accelerate text processing. As index structures for substring pattern matching, suffix trees and DAWGs are well-known. We focus on CDAWG which is a hybrid structure of them, and devised an online linear-time construction algorithm for CDAWGs. We then devised a construction algorithm for CDAWGs with sliding windows, which has an application to text data compression. We also proposed a new index structure for large alphabets (such as Japanese texts), and proved its efficiency experimentally. On the other hand, we analyze the properties of subsequence automata which are index structures for subsequence pattern matching to accelerate subsequence pattern discovery. We successfully gave a solution to the problem of online linear-time construction of word suffix trees, which has been open over 10 years. We developed a fast tree pattern matching algorithm based on bit-parallel technique for efficient processing of semi-structured text data. (3)Pattern discovery and information extraction. We developed efficient pattern discovery algorithms for various classes of patterns. We implemented them and estimated their performances experimentally. We integrated the techniques developed into a knowledge discovery system, applied it to linguistic data and literary data and then obtained good results in corporation with linguists and literary scholars.
Study of High-speed Data Mining Algorithms from Massive Data Streams

IKEDA Daisuke, TAKEDA Masayuki, SHINOHARA Ayumi, KIDA Takuya, KASAHARA Yoshiaki, ISHINO Akira

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research (B)

2003 - 2005

More details Close

In this research, we investigated high-speed online knowledge discovery system for extracting useful information from massive semi-structured data streams. Particularly in this year, as theoretical researches, we extended further the theory of efficient pattern matching and pattern discovery methods for online streams. As application studies, we made a series of experiments on collection and analysis of network data from real high-speed networks in a huge organization. We have also published the results obtained in the research period of the last three years. In particular, we proceed the studies on the following issues: (1)Survey on semi-structured data : We have summarized and published a survey on stream data mining in an academic journal, which has been studied through this project for the last three years. (2)Study on streaming pattern matching technology for semi-structured data : We developed an efficient method for performing tree pattern matching with horizontal wildcards by bit parallel technology, which potentially gives drastic speed-up for Xpath and XQuery pattern matching languages for huge XML data. (3)Study on sequential and streaming pattern discovery technology for semi-structured data : We developed efficient algorithms for finding interesting patterns from massive data streams for various classes of complex patterns/motifs. In this year, we also published pattern discovery algorithms developed in the last year. Also, one of them got awarded for 2004 JSAI SIG AWARD. (4)Empirical study on knowledge discovery from real massive network data : As applications, we performed a series of surveys on data collection and online analysis of high-speed large-scale network for middle sized organization at Kyushu University. These experiments will give insights for future research on the development of efficient pattern matching/discovery algorithms for high-speed streaming data.
文字列集合からの高速パターン抽出アルゴリズムの開発と実働化

篠原歩

Offer Organization: 日本学術振興会

System: 科学研究費助成事業

Category: 若手研究(B)

Institution: 九州大学

2002 - 2004

More details Close

昨年度まで,入力として与えられた文字列集合から,それを特徴付ける一つのパターンを高速に見つけるアルゴリズムの開発をさまざまなパターン族に対して行ってきた.最終年度にあたる本年度は,それをさらに推し進め,複数のパターンの組み合わせによってより柔軟な表現を可能にすることを目指した.当然のことながらこの拡張を行うと,探索空間がさらに広がるために計算時間の増大が問題となる.我々は,接尾辞木を巧妙に活用することによって,与えられた文字列集合を特徴づけるのに最もよいパターン対を効率よく見つけるアルゴリズムの開発に成功した.接尾辞木は,線形サイズとはいえ領域効率があまりよくないため,大規模な文字列に対しては適用しにくくなる.そこで我々は,より領域効率のよい接尾辞配列を用いて接尾辞木を模倣することによって,実装上の観点からも有効なアルゴリズムを与え,計算機実験によってその効果を実証した.また,2つのパターン対の出現する位置の相対距離に関する条件を自由に与えることによって,より表現力を高めたパターン発見問題についても,効率のよいアルゴリズムを与えることができた.さらに,候補となるパターンが与えられた文字列に合致するかどうかを高速に判定するためのデータ構造として,3分木を活用した有向無閉路文字列グラフや,圧縮無閉路文字列グラフについての考察を行った.そしてこの一連のパターン発見問題に関する我々の研究を関連研究と比較しながら総括した.
最適パターン発見に基づく大規模半構造データからの知的情報獲得システムの開発

有村博紀, 篠原歩, 竹田正幸, 坂本比呂志, 下薗真一

Offer Organization: 日本学術振興会

System: 科学研究費助成事業

Category: 特定領域研究

Institution: 九州大学

2003 - 2003

More details Close

本研究では,大量のウェブページやXML等の大規模半構造データからのデータマイニング(ウェブマイニング)に基づき,大量のデータ解析を対話的に支援する効率的なツールとして,従来の情報検索システムを超えた新しい情報アクセスシステムの実現方式を明らかにすることを目標としている.鍵になる技術として,最適パターン発見を木やグラフ構造に拡張し,計算量理論と計算学習理論の最新の成果を援用しながら,半構造データに対する頑健かつ高速な最適化パターン発見アルゴリズムの開発に取り組んだ.平成15年度は,前年度の成果に基づき,(a)有用な情報源の発見,(b)特徴的なパターンの発見,(c)情報の抽出の3つの情報獲得問題について,次の研究を行った. (1)前年度開発した最適分類パターンを用いた高精度テキスト自動分類手法を一種の正規表現を扱えるよう一般化した.さらに,近似文字列照合を可能なパターン発見エンジンを開発し,加速学習法を用いて決定木学習システムBONSAIに組み込んだ(竹田・篠原). (2)XPathパターンに対する最適パターン発見アルゴリズムを設計し,半構造データマイニングエンジンを開発した.とくに今回は,より現実の半構造データに近い無順序木モデルに対して,高速なパターン発見エンジンを開発した.パターンの圧縮表現に対する,高速な列挙アルゴリズムを開発した.独自に開発したオンライン化技術を用いて,オンラインパターン発見手法を開発した(有村). (3)情報抽出に関して,現状の技術動向の調査を行い,水平方向制約(Sequence制約)付き半構造データに対するラッパー帰納アルゴリズムの設計を行った(坂本).さらに,半構造データに適した高性能圧縮アルゴリズムを開発し,性能に関する理論的解析を行った.並行して,開発したアルゴリズムの計算量を解析し(下薗,篠原),個々のアルゴリズムの最適化をおこない,性能を向上させた(全員).最後に,ウェブデータとXMLデータに関する評価実験をおこない,この方式の有効性を評価した(有村・篠原).
Development of Intelligent full text retrieval system based on data compression and fast string pattern matching algorithms

SHINOHARA Ayumi, KIDA Takuya, SAKAMOTO Hiroshi, TAKEDA Masayuki, SHIMOZONO Shinichi

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research (B)

Institution: Kyushu University

2001 - 2003

More details Close

Suffix trees and Directed Acyclic Word Graphs(DAWGs) are well-known data structures as efficient indexingstructures for strings. We focus on Compact Directed Acyclic Word Graphs(CDAWGs) which are more compact indexing structures, and showed online construction algorithms for them. We also showed an online construction algorithm for an indexing structure consists of every DAWGs for all prefixes of given strings, and proved a lower-bound of the number of states of subsequence automata accepting all subsequences of a given string. We then introduced a new implementation technique based on ternary trees for DAWGs, which balances space efficiency and search time for a large alphabet, such as Japanese texts. We proposed an inverse problem in which we infer an original string from a given unlabelled graph corresponding to the indexing structures of the string. We showed linear-time algorithms for DAWG, subsequence automata, and suffix arrays in this setting. Moreover, we succeeded to prove a tight upper-bound of the length of solutions of world equations containing one variable. Concerning with data compression, we showed a space, efficient algorithm which outputs a compact context-free grammar representing a given string, and proved its approximation ratio. We also showed a linear-time compression algorithm using longest first replacement heuristics. In order to find patterns from large database in reasonable time, we developed several algorithms for classes of generalized patterns. Especially, we proposed an efficient pattern discovery algorithm in which we allow small mismatches of the pattern with data, and verified that it is practical by a series of computational experiments.
最適パターン発見に基づく大規模半構造データからの知的情報獲得システムの開発

有村博紀, 下薗真一, 篠原歩, 竹田正幸

Offer Organization: 日本学術振興会

System: 科学研究費助成事業

Category: 特定領域研究

Institution: 九州大学

2002 - 2002

More details Close

ネットワーク上に分散したウェブページやXML等の半構造データの急速な増大に対して,これらのコンテンツに直接アクセスするための効率良い手法の開発が緊急の課題となっている.本研究では,大規模半構造データからのデータマイニング(ウェブマイニング)に基づき,大量のデータ解析を対話的に支援する効率的なツールとして,従来の情報検索システムを超えた新しい情報アクセスシステムの開発を目指す. そのための鍵となる技術として,最適パターン発見を木やグラフ構造に拡張して,半構造データに対する頑健かつ高速な最適化パターン発見アルゴリズムを開発する.さらに,ウェブマイニングを(a)有用な情報源の発見,および(b)特徴的なパターンの発見,(c)情報抽出の3つの過程ととらえ,これらを有機的に結合して,半構造データを対象とした知識獲得システムの効率良い実現方式を明らかにすることを目標とする.また,計算量理論と計算学習理論の最新成果を援用し,計算量に徹底的に配慮した高速なアルゴリズムの開発を目指すのも特色である. 平成14年度は,次の研究成果を得た. (a)「有用な情報源の発見」に関しては,従来より表現力の高いパターンである可変長変数パターン(VLDCパターン)に対する新しいテキスト索引構造を開発し,これを用いて,効率よい最適化マイニングアルゴリズムを開発した. (b)「特徴的なパターンの発見」に関しては,XML-MessagingとSOAPへの応用を目指して,昨年開発した半構造データマイニング手法FREQTを元に,高速な半構造データストリームマイニングSTREAMTを開発した.これは,非常に少なく資源を使いながらデータストリームを監視し、有用なパターンを逐次報告するアルゴリズムである.また,FREQTの最適化マイニングへの拡張と理論的性能解析を行い,この方式の最適性を示した. (c)「情報抽出」に関しては,XMLデータ処理の基本技術である符号語列上のパターン照合機械技術を開発し,XMLパターン検索への応用を考察した.
Foundations of Computational Knowledge Discovery from cDNA Microarray Data

MIYANO Satoru, MATSUNO Hiroshi, AKUTSU Tatsuya, KUHARA Satoru, MARUYAMA Osamu, SHINOHARA Ayumi

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research (B)

Institution: The University of Tokyo

2000 - 2002

More details Close

Since the beginning of this research project, the cDNA microarrays have been intensively employed for measuring gene expressions in laboratories. Some projects on genome-wide gene expression analysis have planed where commercialized statistical analysis program packages and databases are employed as bioinformatics tools in an ad hoc way. However, foundations based on information science were not paid attentions so much while only software tools have been developed from the viewpoint of practice in Japan. This reseach project has contributed to the development of novel microarray data analysis technology. First, we have created a mathematical framework for gene network models from cDNA microarray data (Boolean network model, Bayesian network model, system of ordinary differential equations), then we have developed computational methods for inferring these models from cDNA microarray data. These methods were examined through real biological analyzes. The second contribution is a development of modeling and simulation technology for gene networks (an extention of hybrid Petri net and model simulation of various biopathways). With these research contributions, we have established a computational strategy for developing systems biology.
最適パターン発見に基づく大規模半構造データからの知的情報獲得システムの開発

有村博紀, 篠原歩, 竹田正幸, 坂本比呂志, 下薗真一

Offer Organization: 日本学術振興会

System: 科学研究費助成事業

Category: 特定領域研究(C)

Institution: 九州大学

2001 - 2001

More details Close

ネットワーク上に分散したウェブページやXML等の半構造データの急速な増大に対して,これらのコンテンツに直接アクセスするための効率良い手法の開発が緊急の課題となっている.本研究では,大規模半構造データからのデータマイニング(ウェブマイニング)に基づき,大量のデータ解析を対話的に支援する効率的なツールとして,従来の情報検索システムを超えた新しい情報アクセスシステムの開発を目指す. そのために,鍵となる技術として,最適パターン発見を木やグラフ構造に拡張して,半構造データに対する頑健かつ高速な最適化パターン発見アルゴリズムを開発する.さらに,ウェブマイニングを(a)有用な情報源の発見,および(b)特徴的なパターンの発見,(c)情報抽出の3つの過程からなると考え,これらを有機的に結合して,半構造データを対象とした知識獲得システムの効率良い実現方式を明らかにすることを目標とする,また,計算量理論と計算学習理論の最新の成果を援用して,計算量に徹底的に配慮した高速なアルゴリズムの開発を目指すことも特色である. 平成13年度は,次の研究成果を得た. (a)「有用な情報源の発見」に関しては,部分系列パターンとエピソードパターンと呼ぶ組合せパターンに対する効率よい最適化マイニングアルゴリズムを開発し,これを文字列分類のための決定木学習アルゴリズムBONSAIに組み込んだ. (b)「特徴的なパターンの発見」に関しては,半構造データを最も基本的なラベル付き順序木(labeled ordered trees)のクラスとしてモデル化し,データ中の頻出共通部分構造に対する高速な発見アルゴリズムを開発した.木に関するパターン発見問題は,一般に高い計算量をもつことが多い.そこで,最右枝拡張法という効率よい発見手法を与え,これを複数の最適化手法と組み合わせて,半構造データに対する高速なマイニングアルゴリズムを与えた. (c)「情報抽出」に関しては,ウェブからの情報抽出問題を考察し,HTMLデータから木構造の情報を利用して必要な情報を効率よく切り出すTree-Wrapperアルゴリズムを開発した.
遺伝子ネットワークの解析と可視化システムの開発

篠原歩, 竹田正幸

Offer Organization: 日本学術振興会

System: 科学研究費助成事業

Category: 特定領域研究(C)

Institution: 九州大学

2001 - 2001

More details Close

本研究は,遺伝子の相互作用を明らかにするために,破壊や過剰発現による実験結果を集めた遺伝子発現プロファイルデータから,そこに内在する相互作用を表現するための規則をユーザとの対話の中で発見するためのシステムを開発することを目的とする.我々の研究グループでは,重み付きネットワークモデルを導入し,発現プロファイルデータから遺伝子間の力関係を辺の重みとして取り出すアルゴリズムを設計し,予備実験を行ってきた.このネットワークを効率よく可視化するための方法論を確立し,それを実装することが目的である. 本年は,グラフィカルモデリングと呼ばれる統計的手法の中で用いられている,共分散選択の技法を応用したシステムを構築し,実データに対して適用を行った.また,遺伝子発現プロファイルデータのみならず,遺伝子の配列情報を合わせてネットワークの同定をより高精度に行うことを目指して,配列データからそこに内在する共通なパターンを抽出する問題について,特に高機能化と高速化に力点をおいて研究を展開した.その結果,部分文字列パターンおよびエピソードパターンに関して,実用的な時間で最も分類精度の高いパターンを見つけだすアルゴリズムの開発に成功した.また,その中で頻繁に用いられる部分に特化したデータ構造を開発し,これらを機械発見システムBONSAIの中に組み込んだ.このことにより,これまでの部分文字列パターンのみを用いた表現方法よりも簡潔でより分類精度のよい決定木が抽出できることを確認した.
Development of Efficient Data Mining Systems for Large Semi-Structured Text Data

ARIMURA Hiroki, SHINOHARA Ayumi, TAKEDA Masayuki, SHOUDAI Takayoshi, HIRATA Kouichi, ISHINO Akira

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research (B)

Institution: Kyushu University

1999 - 2001

More details Close

The goal of this research project is to devise an efficient semi-automatic tool that supports human discovery from large unstructured and semi-structured text data. To achieve this goal, we studied in the following three directions. 1. The central process of text mining is pattern discovery. We employed the framework of optimized pattern discovery, and developed effcient and robust text mining algorithms that find simple combinatorial patterns from large unstructured texts. To implement these algorithms, we developed a text index structure based on the suffix arrays suitable for text mining. Based on these technologies, we implemented a prototype system and run computer experiments on Web data. 2. Another important technology for text is efficient pattern matching. As a theoretical framework, we proposed a unified framework, called Collage system, for realizing various dictionary-based compression methods. We developed both Knuth-Morris-Pratt type and Byer-Moore type pattern matching algorithms employing this framework. We also applied this framework to Byte-Pair-Encoding compression method and Sequitur, the former of which yields the fastest compressed pattern matching algorithm. 3. Final process of text mining is information extraction. From theoretical point of view, we first formalize the information extraction problem from semi-structured data, and then gave theoretical analysis of the power and the limitation of such tasks. Then, we developed efficient information extraction algorithms for various types of extraction rules including tree wrappers and hedge patterns and evaluate them through experiments on real-life semi-structured data on the internet.
遺伝子ネットワークの解析と可視化システムの開発

篠原歩, 竹田正幸

Offer Organization: 日本学術振興会

System: 科学研究費助成事業

Category: 特定領域研究(C)

Institution: 九州大学

2000 - 2000

More details Close

本研究は、遺伝子の相互作用を明らかにするために、破壊や過剰発現による実験結果を集めた遺伝子発現プロファイルデータから、そこに内在する相互作用を表現するための規則をユーザとの対話の中で発見するためのシステムを開発することを目的とする.我々の研究グループでは,重み付きネットワークモデルを導入し,発現プロファイルデータから遺伝子間の力関係を辺の重みとして取り出すアルゴリズムを設計し,予備実験を行ってきた.この一連の研究の過程で,出力されるネットワークが必ずしも疎ではないという問題点が浮き彫りになってきた.すなわち,出力されるネットワークが密であるために,その関連を直感的にとらえにくく,またそれを可視化するのも容易ではなかった.したがって,疎なネットワークを見つけ出すためには,何らかの指標に基づいて,このネットワークの辺を「間引く」必要がある.そこで,グラフィカルモデリングと呼ばれる統計的手法の中で用いられている共分散選択の技法を応用し,これを疎な遺伝子ネットワークを見つけるために適用した.しかしながら,遺伝子発現プロファイルデータのもつ共線形性によって,この手法をそのまま適用することは実用上,不可能であった.そこで,堀本らの手法と同様に,VIF指標と呼ばれる値を参照しながら,この問題を避けることができた.VIF指標を用いることによって,遺伝子数が40程度のものまでこの手法で取り扱うことができることがわかった.そこで,注目する遺伝子として指定されたものに,ランダムに選んだ他の遺伝子を加えてネットワークを作成し,これを数回繰り返すことによって安定したネットワークを取り出すという実験を行った.この実験結果の生物学的解釈については,現在検討中である
探索アルゴリズムの理論とその実働化に関する研究

篠原歩

Offer Organization: 日本学術振興会

System: 科学研究費助成事業

Category: 奨励研究(A)

Institution: 九州大学

1999 - 2000

More details Close

人工知能の問題解決において,探索は常に鍵となる役割を果たしている.実際のアプリケーションにおいては,問題固有の知識を利用しながら探索を制御し,探索経路の組み合わせ的爆発に対する工夫を行うことが必要である.今年度は,情報を表現し保持するための最も基本的なデータ構造である文字列に関する探索問題を設定し,部分文字列の持つ性質を生かして,実用上は多くの場合において全解探索を避けられる枝刈りヒューリスティックを提案し,実験によってその効果を検証した. この問題は,実用的な観点から,与えられた2つの文字列集合SとTを分類するために最良な部分列パターンを見つけ出す方法を示すことを目標としたものであるが,NP困難であることが知られている問題と深い関連があり,最悪時には潜在的に指数的に多い候補パターンを調べあげることを余儀なくされる.すなわち基本的には,それぞれのパターンωに対して,ωを部分文字列として含む文字がSとTにそれぞれいくつ存在するかを数え上げなければならない.そこでまず,文字列集合の部分列をすべて受理する部分列オートマトンを高速に構築するアルゴリズムを開発して実装することで,この数え上げ自身を高速化した.この部分列オートマトンの構築アルゴリズムは,現在知られている中で最も効率のよいものである.さらに,可能な限り候補となる部分列を減らすために,部分列に関する包含関係と,目的関数の性質をうまく組み合わせることによって,探索空間を効率的に枝刈りするヒューリスティクスを2つ提案した.これをアミノ酸配列やDNA配列に対する実験に適用し,それぞれのヒューリスティクスの効果と,部分列オートマトンによる高速化の度合いを確認した.
Development of Intelligent Full-text Search System using Efficient Pattern Matching Algorithms on Compressed Data

SHINOHARA Ayumi, SHIMOZONO Shinichi, SAKAMOTO Hiroshi, TAKEDA Masayuki

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research (B).

Institution: KYUSHU UNIVERSITY

1998 - 2000

More details Close

From a theoretical point of view on compressed pattern matching, we introduced a unified frame work, called Collage System, for various dictionary-based data compression methods. We developed both Knuth-Morris-Pratt type and Boyer-Moore type pattern matching algorithms for Collage Systems. We adopted these algorithms for Byte-Pair-Encoding compression method, that yields the fastest compressed pattern matching algorithm in practice. Multiple pattern matching and approximate string matching were also successfully dealt with Collage Systems. We also applied the method for Sequitur, that is another hopeful a compression program, and verified its performance. Moreover, we studied an efficient fully compressed pattern matching for balanced straight-line programs, where not only text strings but also pattern strings are compressed. We also developed an online algorithm that constructs a subsequence automaton from given set of strings, that accepts all subsequences of any string in the set. The algorithm is the fastest, and we verified that it is quite useful to accelerate a knowledge discovery system. On the other hand, concerning with knowledge discovery from database, we studied on the learnability of transformation rules of trees from examples, and searching optimal association rules of words from large text databases. Journal of Discrete Algorithms, 1(1), 2000
Computational Methodology for Knowledge Discovery

MARUOKA Akira, SHINOHARA Ayumi, IMAI Hiroshi, ABE Naoki, WATANABE Osamu, TAKASU Atsuhiro

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research on Priority Areas (A)

Institution: Tohoku University

1998 - 2000

More details Close

The amount of data collected from various fields is growing exponentially and the task of analyzing data to extract useful information behind it is becoming more and more difficult accordingly. To extract useful information from data, there must be certain appropriate interaction between the extraction process and data. Through the interaction various processes, such as memorizing certain information, Iearning, evolution, and possibly discovering knowledge will be performed. The major hurdles to automatically extracting knowledge from huge amount of data is the limitations on computational resources. Group A03 aims to propose and develop computational models and methodologies for knowledge discovery. To achieve the purpose we explore various topics including algorithms dealing with heterogeneous data which may be strongly structured or poorly structured. Among the results of this project, the ones concerning computational mechanisms to find efficiently effective rules from very large databases are as follows : Efficient mining from large databases by query learning ; A modification of AdaBoost for adaptive sampling methods ; Tree-based boosting using linear classifier ; The minimax strategy for Gaussian density estimation. Furthermore, algorithms to solve certain concrete problems are developed ; A practical algorithm to find the best subsequence patterns ; Biological sequence compression algorithms - Learning via compression schemes ; Effect of sample size in text categorization ; Knowledge discovery by using both experimental and theoretical methods ; Discovery of commonality among definition sentences by MDL-based compression.
Development of Data Mining System Using Binary Decision Diagrams for Knowledge Representation

MIYANO Satoru, SHINOHARA Ayumi, MARUYAMA Osamu, AKUTSU Tatsuya, SHIMOZONO Shinichi, SHOUDAI Takayoshi

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research (B)

Institution: The University of Tokyo

1997 - 1999

More details Close

Discovery is one of the most basic activities in sciences and it has been recognized that knowledge discovery is very important in human intellectual activity. However, this process of knowledge discovery is being replaced or assisted by systems called data minining, systems. In order to cope with this situation, this research ,vas started to develop a knowledge discovery system based on binary decision diagrams for knowledge representation. Our mathematical analyses proved that it is computationally hard to deal with binary decision diagrams directly for knowledge representation This insight directed us to develop a system which first deals with decision trees and then convert the decision trees to binary decision diagrams. As a result, we have developed a system called Hypothesis Creator which has (1) a parallelized hypothesis generator with the ability of dealing with several ten million attributes and (2) view design system for creating attributes We have also developed a system called Decision Diagram Editor for converting and crerating decision diagrams which encourages human intervention for hypothesis creation.
発見的探索アルゴリズムの理論と実働化

篠原歩

Offer Organization: 日本学術振興会

System: 科学研究費助成事業

Category: 奨励研究(A)

Institution: 九州大学

1997 - 1998

More details Close

人工知能の問題解決において,探索は常に鍵となる役割を果たしている.実際のアプリケーションにおいては,問題固有の知識を利用しながら探索を制御し,探索経路の組み合わせ的爆発に対する工夫を行うことが必要である.このような経験的な知識を利用した探索は,発見的探索アルゴリズムと呼ばれているが,そのパフォーマンスは個々の問題固有の性質に強く依存し,効率の良い探索技法の統一的な開発,解析が極めて困難である.この発見的アルゴリズムを計算論的学習理論の枠組みでとらえ,さらに具体的な問題を用いてその有効性を実証することを目標として研究を展開した.まず,質問学習のモデルにおいて,概念クラスが多項式回の質問によって学習可能になるための統一的な特徴付けを与えることに成功した.この特徴付けは,これまで等価性質問,所属性質問,およびその組み合わせについてそれぞれ個別に研究されてきたものであるが,我々の成果はそれを包含している.この特徴付けにより,質問による学習可能性の本質は例空間を効率よく絞り込む質問の存在と,絞り込んだ仮説が正しいことを検証できる質問の存在にあるという知見が得られた.次に,実際的によく用いられている決定木の学習アルゴリズムを土台にして,重み付き分類規則を見つけるアルゴリズムを提唱した.計算機実験によってこの方式が時間的にも,また予測精度の点からも決定木のものと同等以上の性能を有することを検証した.さらに,遺伝子の破壊と強制発現によるデータから遺伝子ネットワークを同定する問題を探索問題としてとらえ,この問題の計算量を解明し,理論的な面と実際的な面の両面からそのパフォーマンスを解析し,計算機実験を行った.
Studies on fast pattern matching algorithms based on text compressions

TAKEDA Masayuki, SHINOHARA Ayumi

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research (C)

Institution: KYUSHU UNIVERSITY

1997 - 1998

More details Close

The aim of text compressions is to decrease the amount for storing files in secondary disk stor- ages. Therefore the traditional criterion is the compression ratio. In this project we propose a new criterion to select a compression method. The criterion is the efficiency of string pattern matching in compressed texts without decoding. The goals of this project are : Goal 1 : A faster search in compressed text in comparison with a decompression followed by a simple search. Goal 2 : A faster search in compressed text in comparison with a simple search in uncompressed text. Main results of this research in these two years are summarized as follows. (1) We developed and implemented a multiple pattern matching algorithm in compressed text by the LZW compression method, which is used in the COMPRESS command in UNIX. (2) We also devised a more efficient algorithm for a single pattern in LZW compressed texts, which is based on the Shift-And approach. (3) We proved by experiments that the algorithms of (1) and (2) are approximately twice faster than a decompression followed by a simple search. That is, we have achieved Goal 1. (4) We proved by experiments that the algorithms of (1) and (2) are faster than a simple search on uncompressed texts. That is, we have achieved Goal 2. (5) We also developed compressed pattern matching algorithms for other compression methods, such as, byte pair encoding, Huffman encoding, finite-state encoding, and compression using antidictionaries, and then evaluate them. We have finished this project successfully.
領域予測のための機械発見システムの研究

篠原歩, 正代隆義

Offer Organization: 日本学術振興会

System: 科学研究費助成事業

Category: 重点領域研究

Institution: 九州大学

1997 - 1997

More details Close

本研究は,DNA配列データに対して,その中の遺伝子領域予測できるシステムを構築するための体系的な方式を研究し,実用的な領域予測システムを実働化することを目的とする.この目的を達成するために,我々は以下の項目に力点をおいて研究を展開した.(1)領域予測問題の抽象化と定式化.(2)領域予測アルゴリズムの開発.(3)上記アルゴリズムの理論的基礎.(4)計算機実験による上記アルゴリズムの評価.まず,文字列情報の中の特定の機能部位を同定する問題を,文字列の長さを保存する関数のクラスの学習問題として定式化した.そして,その関数の学習アルゴリズムとして,重み付き投票アルゴリズム(WM)を拡張したアルゴリズム(WM^*)を開発した.WMは,複数の予測アルゴリズムを統合して,よりよい精度で予測が行えることを指向するものであり,プールの中の各予測アルゴリズムに予測を投票させ,その投票結果によって全体的な判断を下すものである.我々の拡張によるWM^*は,おのおのの予測アルゴリズムが投票を棄権することを認めるものである.このことにより,直観的には,各予測アルゴリズムは自信のない予測については棄権によって発言権の低下を防ぐことができると期待される.実際に我々は,WM^*による予測の方がWMによる予測よりも原理的に優れていることを理論的に証明した.さらに,このWM^*を組み込んだ領域予測システムHAKKEのプロトタイプを作成し,DNA配列の中から遺伝子領域を予測する実験を行った.また,最も基本的な問題である,パターン照合問題に対して,テキストとパターンが両方とも直線的プログラムで記述されて与えらたときに高速にパターン照合を行うアルゴリズムの開発に成功した。
Development of Intelligent Full-Text Information Processing System Based on Efficient Pattern Matching Algorithms

ARIKAWA Setsuo, INOUE Hitoshi, TAKEDA Masayuki, SHINOHARA Ayumi, SHINOHARA Takeshi, MATSUO Fumihiro

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research (A)

Institution: KYUSHU UNIVERSITY

1995 - 1997

More details Close

The goal of this project is to develop a new type text database management system which exploits techniques of pattern matching and machine learning. We completed the project successfully with the following results achieved in this year. (1) We implemented and evaluated an intelligent full-text processing system. (2) We developed efficient pattern matching algorithms in compressed texts for several compression methods. (3) We presented the above algorithms at conference of Combinatorial Pattern Matching (CPM97) in Denmark at June 1997, and discussed them with experts in this research area. (4) We developed an efficient pattern matching algorithm which deals with pictures and wildcards. (5) We developed learning system for text processing and then incorporated it into the system of (1).
発見的探索アルゴリズムの理論と実働化

篠原歩

Offer Organization: 日本学術振興会

System: 科学研究費助成事業

Category: 奨励研究(A)

Institution: 九州大学

1996 - 1996

More details Close

人工知能の問題解決において,探索は常に鍵となる役割を果たしている.実際のアプリケーションにおいては,問題固有の知識を利用しながら探索を制御し,探索経路の組み合わせ的爆発に対する工夫を行うことが必要である.このような経験的な知識を利用した探索は,発見的探索アルゴリズムと呼ばれているが,そのパフォーマンスは個々の問題固有の性質に強く依存し,効率の良い探索技法の統一的な開発,解析が極めて困難である.この発見的アルゴリズムを計算論的学習理論の枠組みでとらえ,さらに具体的な問題を用いてその有用性を実証することを目標として研究を展開した. まず,複数の有力なアルゴリズムを統合して,よりパフォーマンスの高いシステムを構築するための手法として,重みつき投票アルゴリズム(WM)の拡張(WM^*)を行った.WMは,各アルゴリズムに予測を投票させ,その投票結果によって全体的な判断を下すものである.我々の拡張によるWM^*は,おのおののアルゴリズムが投票を棄権することを認めるものであり,直観的には,各アルゴリズムは自信のない予測については棄権によって発言権の低下を防ぐことができると期待される.実際に我々は,WM^*による予測の方がWMによる予測よりも原理的に優れていることを理論的に証明した.さらに,このWM*を組み込んだ領域予測システムHAKKEのプロトタイプを作成し,アミノ酸配列データからのαヘリックス部位と膜貫通部位の同定問題に対する計算機実験によって,この優位性を検証した. また,パターン言語の学習可能性を探究し,次のような知見を得た.(1)部分列言語の和集合のクラスは,非常に少ない所属性質問と等価性質問を用いて学習可能である.(2)部分列言語のクラスは,所属性質問のみで学習可能である.(3)パターン言語のある部分クラスは,1つの正例と非常に少ない所属性質問を用いて学習可能である.
機械学習と機械発見による生物情報の概念形成

篠原歩, 正代隆義

Offer Organization: 日本学術振興会

System: 科学研究費助成事業

Category: 重点領域研究

Institution: 九州大学

1996 - 1996

More details Close

本研究は,塩基配列やアミノ酸配列等の配列データに対して,その中の機能部位や機能領域を予測できるシステムを構築するための体系的な方式を研究し,実用的な領域予測システムを実働化することを目的とする.この目的を達成するために,我々は以下の項目に力点をおいて研究を展開した. (1)領域予測問題の抽象化と定式化.(2)領域予測アルゴリズムの開発.(3)上記アルゴリズムの理論的基礎.(4)計算機実験による上記アルゴリズムの評価. まず,文字列情報の中の特定の機能部位を同定する問題を,文字列の長さを保存する関数のクラスの学習問題として定式化した.そして,その関数の学習アルゴリズムとして,重み付き投票アルゴリズム(WM)を拡張したアルゴリズム(WM^*)を開発した.WMは,複数の予測アルゴリズムを統合して,よりよい精度で予測が行えることを指向するものであり,プールの中の各予測アルゴリズムに予測を投票させ,その投票結果によって全体的な判断を下すものである.我々の拡張によるWM^*は,おのおのの予測アルゴリズムが投票を棄権することを認めるものである.このことにより,直観的には,各予測アルゴリズムは自信のない予測については棄権によって発言権の低下を防ぐことができると期待される.実際に我々は,WM^*による予測の方がWMによる予測よりも原理的に優れていることを理論的に証明した.さらに,このWM^*を組み込んだ領域予測システムHAKKEのプロトタイプを作成し,アミノ酸配列データからのαヘリックス部位の同定問題と,膜貫通部位の同定問題に対する計算機実験によって,この優位性を検証することに成功した.この理論的解析および計算機実験の結果から,我々の提案するWM^*アルゴリズムは複数の戦略を統合する予測アルゴリズムとして従来のWMよりも優れていることが確認できた.
Development of efficient learning theory

THOMAS Zeugmann, SHINOHARA Ayumi

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research (C)

Institution: Kyushu University

1995 - 1996

More details Close

During the first phase of the project the average-case complexity of Lange and Wiehagen's (1991) pattern language learning algorithm has been studied. This algorithm learns the whole class of all pattern languages in the limit from positive data. We developed an appropriate average-case model addressing the total learning time behavior, i.e., the overall time taken by the algorithm until learning. Concerning Lange and Wiehagen's (1991) algorithm the following results have been obtained. Let ALPHA={0,1, ..} be any finite alphabet. For every pattern pi containing kappa different variables it has been shown that the total learning time is O (log^<|A|> (|A|+kappa) |pi|^2) in the best-case and unbounded in the worst-case. We calculated the expected total learning time to be O (2^<kappa>kappa^2|A||pi|^2log^<|A|> (kappa|A|)) with respect to the uniform distribution. However, most of the framework developed is distribution independent. Subsequently, using refined techniques we improved the result to O (2^<kappa>kappa^2|pi|^2log^<|A|> (kappa|A|)) which is qualitatively different, since it shows that the expected total time decreases if the alphabet size increases. The results obtained have numerous consequences and applications to other pattern language learning algorithms, e.g., their learnability in the query model, their learnability from good examples. In the second phase, we intensively studied the learnability of one-variable pattern languages from positive data and obtained three new algorithms. The first algorithm is a considerable and uniform improvement over Angluin's (1980) algorithm, since it reduces the time to compute descriptive updates from O (eta^4logeta) to O (eta^2logeta) for inputs of size eta. The algorithm obtained could be effectively parallelized, too, and a slight modification learns all one-variable pattern languages within Angluin' (1988) query model from superset queries only. Finally, we succeeded to design the first one-variable pattern language learning algorithm whose expected total learning time is O (l^2logl) provided the positive data are randomly drawn with respect to a probability distribution with expected string length l. Thus, our algorithm has an expected average-case behavior concerning its total learning time which is provably only by a constant factor larger than the best known update time though the total learning time remains unbounded in the worst-case. A further paper analyzing the total learning time of Haussler's (1987) prediction algorithm for learning conjunctive concepts is under preparation.
Development of Parallel Knowledge Acquisition System

MIYANO Satoru, SHIMOZONO Shinichi, SHINOHARA Ayumi, SHOUDAI Takayoshi, SHINOHARA Takeshi, ARIKAWA Setsuo

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research (A)

1994 - 1996

More details Close

The ability of knowledge acquision has strong effects on the developments of various scientific and industrial activities. The quality of the knowledge and the efficiency of the knowledge acquisition procedure are keys to these activities. A group or society with the such knowledge acquisition ability in information processing activities may be promised a big advance. The knowledge acquision activity is regarded as an activity which can be done by only human beings. Recently, however, computational learning technologies and artificial intelligence is realizing information systems which can play the knowledge acquisition activity instead of human beings. This research project has attained the following items by the above technologies. 1. Paradigm of parallel knowledge acquisition. 2. Design and development of a parallel knowledge acquisition system based on the above paradigm. With this system, we have made several computational experiments on knowledge acqusition, especially for DNA and amino acid sequences. The results were very successful. It is scheduled that this system will be open to publich via Human Genome Center of the University of Tokyo.
Machine Discovery by Learning Algorithms

ARIKAWA Setsuo, MIYANO Satoru, EIJU Hirowatari, SHINOHARA Ayumi, ZEUGMANN Thomas, NIIJIMA Kouichi

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research (B)

Institution: KYUSHU UNIVERSITY

1994 - 1996

More details Close

This project aimed at developing machine discovery systems based upon firm theoretical foundations of machine learning algorithms. In this project we have focused our attention specially on (1) computational logic of machine discovery, (2) knowledge representation for machine discovery, (3) machine discovery by PAC learning, (4) machine discovery in databases, and (5) making machine discovery algorithms parallel. First we have developed a logic of machine discovery compared with the logic of scientific discovery by K.Popper. We have made it clear that the essential of machine discovery is to be able to refute the hypothesis space itself by some observed facts, and showed that there are such rich hypothesis spaces in the framework of the elementary formal systems. Since scientific data are mostly numerical, we have studied representation of real numbers and real-valued functions in terms of recursive reals and interval analysis, and developed a method of identifying differential equations. We have extended our results on the logic of machine discovery to the PAC learning, which can cope with probably approximately correct hypotheses. Concerning the machine discovery in database, we have developed a machine discovery system based upon a decision trees over regular patterns called BONSAI,made it parallel, and also developed a prediction system for some domains in amino acid sequences. We have also made some experiments on the field of molecular biology, and got very successful results.
確率論的近似学習と計算論的教示の理論

篠原歩

Offer Organization: 日本学術振興会

System: 科学研究費助成事業

Category: 奨励研究(A)

Institution: 九州大学

1995 - 1995

More details Close

PAC学習可能性に関しては,仮説空間全体の反駁可能性を含めた「反駁PAC学習可能性」を提案し,学習に必要なデータの個数と計算時間についての解析を行った結果,次のような知見が得られた. 1.反駁学習に必要なデータの個数の解明.この結果により,従来のPAC学習モデルにおいて必要とされるデータの個数と,反駁学習モデルにおいて必要とされるデータの個数は,入力されるパラメーターの多項式サイズという点では,同じであることを示した. 2.概念クラスが多項式時間で反駁学習可能となるための必要十分条件となるアルゴリズムの構築.この結果は,多項式時間反駁学習可能性の特徴付けに役立ち,さらには,多項式時間で反駁学習可能となる概念クラスを見つけ出す手がかりとなる. また,実用的に広く用いられている,順序付き二分決定グラフ(OBDD)の学習可能性についても,そのPAC学習可能性を解明した. これらの結果をふまえて,ゲノム情報データからの知識獲得システムBONSAIを並列に走らせて知識獲得を行うBONSAI Gardenシステムを実働化し,計算機実験を行った. 一方,これらの情報処理技術の根幹をなす,文字列照合問題について,パタンもテキストも両方とも圧縮されたデータについて,それらを陽に展開することなく,そのまま文字列の照合を行う多項式時間アルゴリズムの開発にも成功した.これは,今後,さらにさまざまな方向へ拡張が期待される成果である.
STUDY ON EFFICIENT SEARCH ALGORITHMS

MIYANO Satoru, SHIMOZONO Shinichi, SHINOHARA Ayumi, SHOUDAI Takayoshi

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for General Scientific Research (C)

Institution: KYUSHU UNIVERSITY

1994 - 1995

More details Close

Technologies for discoverring knowledge from nucleic acid and amino acid sequences are most expected in Genome Informatics/Molecular Bioinformatics. Various search techniques have traditionally playd a very important role in knowledge discovery from sequence. Our goal of this research are to establish the fundamental search strategies and to analyze its computational complexity. The following are the selection of the result for our study on efficient seach algorithms : We define a new framework for rewriting graphs, called a formal graph system (FGS) , which is a logic program having hypergraphs instead of terms in first-order logic. We show that the refutation tree problem for three subclasses of FGSs are computed efficiently in parallel. A partial walk in an undirected edge-colored graph G is a path in G.If a partial walk in G contains all edges of G,it is called a walk in G.The graph inference from walk is, given a string x, to find the smallest graph which can realize x as a walk in G.We prove that the graph inference from a walk for tree of bounded degree 3 is NP-complete. The knowledge on sequences is often expressed as a motif which is a pattern common to a family of sequences. We presents a greedy strategy for finding such motifs wich ambiguity just from positive and negative examples by exploiting the probabilistic argument. We have developed a parallel machine discovery system BONSAI Garden by employing these results. This system has succeeded in discovering resonable knowledge on a hodgepodge of amino acid sequences.
計算論的教示の理論

篠原歩

Offer Organization: 日本学術振興会

System: 科学研究費助成事業

Category: 奨励研究(A)

Institution: 九州大学

1994 - 1994

More details Close

本研究は,教示と学習のメカニズムを計算量理論の観点からとらえる枠組みを構築し,それらの関係,違いを情報科学的に解明することを目的とするものである.本年度は,まず,PAC学習可能性を完全に特徴づける尺度として知られている,Vapnik-Chervonenkis次元(VC次元)について,その計算量に関する諸問題を解決した.具体的には,VC次元を求める問題と,O(log^n)変数の論理式の充足可能性問題との間の相互の多項式時間還元を与えることによって,この問題がNP完全でもなく,かつ多項式時間では解けないという強い状況証拠を与えることに成功した.こここまた,VC次元の様々な拡張に対しても同様な結果を得ている. 次に,「反駁学習可能性」を,PAC学習の枠組みにおいて定式化し,その特徴付けを行った.反駁可能性とは,想定している仮説空間の中に目標概念をうまく説明するものが存在しない場合に,その仮説空間全体を反駁できることをいい,原理的には,仮説空間そのものの善し悪しを判断する基準となる.ここで定義された反駁PAC学習可能性は,多項式サンプルという観点からは,通常のPAC学習可能性と同値であることを証明した. さらに,コンパクトに表現された文字列に対する多項式時間の文字列検索アルゴリズムを与えた.これは,テキストそのものは長大だが,そのテキストがある規則を用いてコンパクトに表現されているとき,一旦テキストを展開せずに,そのままの形で別の文字列を検索するという新しい手法である.今後は,複数の文字列への対応,近似を許した検索などへの様々な拡張が考えられる.
類推と最小記述長原理によるゲノムデータの知識処理

有川節夫, 篠原歩, 正代隆義

Offer Organization: 日本学術振興会

System: 科学研究費助成事業

Category: 重点領域研究

Institution: 九州大学

1994 - 1994

More details Close

本研究は,類推についての理論的研究の成果とシステム化の経験を基礎にして,類推という極めて自然で,問題解決の初期の段階で活用される推論方式とMDL原理という強力な知識獲得方式に基づく,ゲノムデータ処理に適した一般性のある知識処理の方式を確立することを目的としている.本年度は,以下の成果を得た. (1)ゲノムデータのための類比の研究配列間のホモロジーに対応するものが「類比」であるが,構造等を考慮したさらに高次の類比の定式化を行った.それと同時に高次パターンマッチングアルゴリズムを研究開発した. (2)MDL原理の研究アミノ酸のインデックス化は,KyteとDoolittleの研究に見られるように,タンパク質の機能・構造予測に極めて有用な概念である.このインデックス化と正則パターン上の決定木を組み合わせた概念は,これまでの研究でその有効性が実証されている.そこで,MDL原理を用いて,アミノ酸配列等のデータからそのインデックス化と決定木を作り出す方式を開発した. (3)類推の効率化およびMDL原理の効率的実現方式の研究これまで開発してきた類推方式で実現されている類推エンジンの高速・効率化を行った.また,(1)の成果に対応した効率の良い新たな類推方式を開発した.さらに,MDL原理を計算機上で実現し,そののアルゴリズムの効率化の理論的限界について研究した. (4)計算機実験高次パターンマッチングアルゴリズム,類推の効率化,およびMDL原理に基づく決定木構成のアルゴリズムを本研究費で購入したワークステーション等を用いて実現し,アミノ酸列からの知識獲得問題に適用し,有用な成果を得た.
確率的近似学習のパラダイムによる遺伝的アルゴリズムの効率の解析および実働化

篠原歩

Offer Organization: 日本学術振興会

System: 科学研究費助成事業

Category: 奨励研究(A)

Institution: 九州大学

1993 - 1993

More details Close

本研究の目的は、理論的な研究はすすんでいるが実用的な応用例に乏しいPAC学習のパラダイムと、理論的解析法の整備されないままにも実用的なアプリケーションが開発されつつある遺伝的アルゴリズムを融合し、理論と応用の両面から、生物学的データからの知識獲得を行なうシステムを開発することである。今年度は、以下の知見が得られた。 1.PAC学習可能性を確かめた上でワークステーション上に実働化した知識獲得システム「BONSAI」を、並列化可能性の観点から見直し、そのプロトタイプを作成した。その中で、特に計算量を要する、パターンの検索部分に対し、遺伝的アルゴリズムを適用して、その効果を確かめた。これらの理論的な解析については、今後ともに引き続き重要な研究の課題となると思われる。また、ここで構築したシステムは、実際の遺伝子データのように、もともとの分類のはっきりしない問題に対しても有効であると期待される。 2.PAC学習可能性を特徴づける組み合せ量として重要な、VC次元を求めるための計算量の評価を行った。さらに、これを一般の関数に関して拡張した次元についても同様な解析を行った。その結果、この計算量は、変数の個数を限定した論理式の充足可能性問題との還元可能性で特徴づけられ、NP完全にもなりそうにはないがPで解けそうもない、という、計算量理論の観点からも興味ある知見を得た。この結果は、学習アルゴリズムの計算量の評価とは独立した問題ではあるが、今までと異なる観点から学習モデルを評価する際に有用になると思われる。
確率的近似学習のパラダイムによる遺伝的アルゴリズムの効率の解析および実働化

篠原歩

Offer Organization: 日本学術振興会

System: 科学研究費助成事業

Category: 奨励研究(A)

Institution: 九州大学

1992 - 1992
並列学習アルゴリズムによる大量ゲノムデータからの知識獲得の研究

宮野悟, 篠原歩, 有川節夫

Offer Organization: 日本学術振興会

System: 科学研究費助成事業

Category: 重点領域研究

Institution: 九州大学

1992 - 1992

More details Close

1.決定木とインデックス化の機械学習による知識獲得機械学習によって,構造のわからない1次元の文次列データから知識を獲得する手法として,本年度は,初年度に着手した正規パターン上の決定木の学習についての理論的結果に基づき,機械学習システムの基本設計とその中核部分の実働化を行った。そして高度の学習を狙い,その学習可能性,探索に要する計算量などを解析した。そして,これらの理論的研究に基づき,その学習可能性,探索に要する計算量などを解析した。そして,これらの理論的研究に基づき,文字列データからの知識獲得システムBONSAIの開発を行い,ワークステーション上に実働化することに成功した。BONSA夫は,文字列データからの知識獲得システムである。このシステムは正の例と負の例の集合が与えられると,それらを分類する仮説として,アルファベットのインデックス化と正規パターン上の決定木を発見する。アルファベットのインデックス化とは,入力データに使われている文字を,あらかじめ設定された,より少ない個数の文字へ変換する対応づけである。例えば,アミノ酸配列のデータを入力とした場合,20種類のアミノ酸の記号を数種類に分類することに相当し,このようなアミノ酸の分類は分子生物学の世界で普通に行われていることである。正当パターン上の決定木とは,各ノードに正規パターンと呼ばれる判定規則を用いた決定木である。正規パターンとは,「モチーフ」を一般化した概念である。BONSAIから出力された決定木のノードに現れる正規パターンから,重要なモチーフが抽出されることになる。また同時に,タンパク質の分類にBONSAIを利用した場合,BONSAIが発見してくるインデックス化から,アミノ酸のどのような分類が有効であるのかを知ることができる。 2.実験結果BONSAIは膜貫通領域予測問題に対して極めて精度の良い仮説を発見した。それとともに,インデックス化の探索の方法として用いた局所探索法によって,親水度にほとんど対応したインデックス化をBONSAIが発見したことは,この方式の有効性を十分に証明している。またシグナル配列の問題に対しても極めて良いインデックス化と決定木を発見している。
Algorithmic research on computational learning and teaching

MIYANO Satoru, MIYAHARA Tetsuhiro, SHINOHARA Ayumi, ARIKAWA Setsuo

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for General Scientific Research (C)

Institution: Kyushu University

1990 - 1991

More details Close

This research concentrates on computational learning from the view point of algorithmic teaching. We introduced the notion of teachability with which we established a relationship between the learnability and teachability. We obtained some results on the complexity issues of a teacher in relation to learning. We also considered the analogical reasoning in relation to learning. We showed that NP-hard aspect appears in analogicaj reasoning. In our framework, the set cover problem proved to be an important issue for finding keys in teaching. For this problem we devised a parallel algorithm which solves the minimal set cover problem. We also investigated elementary formal systems with respect to polynomial-time learnability. We identified some important and useful subclasses of elementary formal systems which are polynomial-time learnable. Based on these theoretical researches, we developed a machine learning system which employs decision trees over regular patterns. This system finds important keys from randomly chosen samples which may explain the given samples reasonably. In addition to theoretical analysis of our system, experiments show that this machine learning system exhibited quite successful results. In order to find keys in teaching, we also developed a system based on elementary formal systems which employs the approximation algorithm for minimum set cover problem. Comparison of these two systems showed that the former is faster and efficient than the latter. But, by theoretical reasons, the latter system can cope with problems with larger variety.
ソフトウェア構成法における類推と帰納推論

有川節夫, 篠原歩, 篠原武, 宮野悟

Offer Organization: 日本学術振興会

System: 科学研究費助成事業

Category: 重点領域研究

Institution: 九州大学

1990 - 1990

More details Close

高機能高品質ソフトウェアの構成法を類推と帰納推論の観点からモデル化して,その本質に迫ることが本研究の目標である.この目標に沿って本年度は,論理型言語PrologとEFSを対象にして以下の要領で研究を行い多くの基礎的な成果を得た.ソフトウェア開発者は,問題が与えられたとき通常次の3つの手順で考える.(1)過去に同じ問題を扱ったことはないか.(2)過去に類似した問題を扱ったことはないか.(3)全く新しい問題であるか.本研究で対象にするのは(2)と(3)の場合である. (2)の場合には類推が使われることになる.具体的には,以下のようなプロセスが使われる.すなわち,開発しようとしているプログラム“A"に類似したプログラムBを選び出し,Bとゴ-ルの例glとを対象にして類推を行い,そこで使われたプログラム節C1を取り込む.こうしたプロセスを何回か繰り返して,ゴ-ルの例gl,…,gnに対して節Cl,…,Cnを取り込んで,“A"の骨格を形成する.この方式の理論を構築した.具体的には,まず類推のための抽象化の研究を行い,類推のソ-スを検索するために,プログラムを抽象化によって索引付け,それを用いて可能性のない対象を捨てる方式を開発した.また,学習の主要なパラダイムとして注目を集めているEBL(説明に基づく学習)の類推による拡張を行った. (3)の場合には,帰納推論が活用され得る.本年度は,EFS(Elementary Formal System)という文字列を直接扱える一種の論理型言語を用いて,帰納推論の統一的枠組みを与え,このEFSの有効性を明らかにした.また,正デ-タからの帰納推論の能力が実は相当に大きいことやPAC学習可能な言語族等をEFSの枠組みで明確にした.さらに,Muggletonによる逆導出法についても基礎研究を行い,初年度の研究は,ほぼ計画通りの成果が得られた.

Show all Show first 5

Teaching Experience 2

知能システム科学　東北大学大学院情報科学研究科
オートマトン・言語理論　東北大学工学部

Social Activities 2

東北大学サイエンスカフェ

2007/08/31 -

More details Close

第２５回「ロボカップサッカーと人工知能～考えるロボットは実現できるのか？」
ときめき☆ひらめきサイエンスようこそ大学の研究室へ日本学術振興会

2007/08/09 -

More details Close

科研費による研究成果の一端を高校生が見る，聞く，触れることで，学術と日常生活との関わりや，科学がもつ意味を理解してもらうプログラム．「アルゴリズムを体感しよう ---ロボットプログラミングを通じて---」と題して，講演とロボットプログラミングの実習を行った．