博士(工学), 電気通信大学, Mar. 1993

Computer Science

Intelligent Informatics

Theory of Computation

Game Informatics

Combinatorial Optimization

Computational Learning Theory

Automata and Formal Language Theory

Informatics, Intelligent informatics

Informatics, Information theory

01 Apr. 2016
Graduate School of Informatics and Engineering & School of Informatics and Engineerings, The University of Electro-Communications, Assistant Professor

01 Apr. 2010 - 31 Mar. 2016
Graduate School of Informatics and Engineering & Faculty of Informatics and Engineerings, The University of Electro-Communications, Assistant Professor

01 Apr. 2007 - 31 Mar. 2010
Faculty of Electro-Communications, The University of Electro-Communications, Assistant Professor

01 Apr. 1993 - 31 Mar. 2007
Faculty of Electro-Communications, The University of Electro-Communications, Research Associate

Apr. 1988 - Mar. 1993
The University of Electro-Communications, Graduate School, Division of Electro-Communications, Course in Communications and Systems Engineering

09 Apr. 1984 - 23 Mar. 1988
The University of Electro-Communications, Faculty of Electro-Communications, Department of Communication Engineering

Apr. 1981 - 09 Mar. 1984
Tokyo Metropolitan Kunitachi High School, General Course, Japan

Dec. 2022 - Mar. 2023
Local Committee of the 85th National Convention of IPSJ, Information Processing Society of Japan, Society

Apr. 2017 - Mar. 2021
数理モデル化と問題解決研究会運営委員, 情報処理学会, Society

Apr. 2018 - Mar. 2019
2018年度事務局委員, LAシンポジウム, Society, IT担当（Webサイトおよびメーリングリストの運用・管理）

Apr. 2010 - Mar. 2014
数理モデル化と問題解決研究会運営委員, 情報処理学会, Society, メーリングリスト管理担当

Apr. 2010 - Mar. 2011
2010年度事務局委員, LAシンポジウム, Society, IT担当（Webサイトおよびメーリングリストの運用・管理）

Apr. 2002 - Mar. 2003
2002年度事務局委員, LAシンポジウム, Society, IT担当（Webサイトおよびメーリングリストの運用・管理）

Apr. 1999 - Mar. 2003
数理モデル化と問題解決研究会運営委員, 情報処理学会, Society, メーリングリスト管理担当

Distinguishing between humans and computers in a card game with imperfect information
Seiya Okubo; Masato Konishi; Mitsuo Wakatsuki; Tetsuro Nishino
EPiC Series in Computing, Proceedings of the 34th International Conference on Computer Applications in Industry and Engineering (CAINE 2021), 79, 140-149, 12 Oct. 2021, Peer-reviwed
International conference proceedings, English

The characteristics of the card game Daihinmin
Mitsuo Wakatsuki; Seiya Okubo; Yuta Kado; Yamato Takeuchi; Tetsuro Nishino
Information Engineering Express, International Institute of Applied Informatics, 7, 2, 11-21, 30 Sep. 2021, Peer-reviwed
Scientific journal, English

New applications of the Monte-Carlo tree search to computer Daihinmin
Seiya Okubo; Mitsuo Wakatsuki; Tasuku Mitsuishi; Yasuki Dobashi; Tetsuro Nishino
International Journal of Smart Computing and Artificial Intelligence, International Institute of Applied Informatics, 4, 1, 18-35, 31 May 2020, Peer-reviwed
Scientific journal, English

New applications of the Monte Carlo method for computer Daihinmin
Seiya Okubo; Tasuku Mitsuishi; Yasuki Dobashi; Mitsuo Wakatsuki; Tetsuro Nishino
Proceedings of the 8th International Congress on Advanced Applied Informatics (IIAI AAI 2019), 623-628, Jul. 2019, Peer-reviwed
International conference proceedings, English

What are the characteristics of the card game Daihinmin?
Mitsuo Wakatsuki; Yuta Kado; Yamato Takeuchi; Seiya Okubo; Tetsuro Nishino
Proceedings of the 8th International Congress on Advanced Applied Informatics (IIAI AAI 2019), 587-592, Jul. 2019, Peer-reviwed
International conference proceedings, English

Toward a statistical characterization of computer Daihinmin
Seiya Okubo; Yuuta Kado; Yamato Takeuchi; Mitsuo Wakatsuki; Tetsuro Nishino
International Journal of Software Innovation, IGI Global, 7, 1, 63-79, Jan. 2019, Peer-reviwed
Scientific journal, English

Route search method for autonomous mobile robots using machine learning
Mitsuo Wakatsuki; Seiya Okubo; Tetsuro Nishino
Proceedings of the 31th International Conference on Computer Applications in Industry and Engineering (CAINE 2018), 71-76, Oct. 2018, Peer-reviwed
International conference proceedings, English

Decision tree analysis in game informatics
Masato Konishi; Seiya Okubo; Tetsuro Nishino; Mitsuo Wakatsuki
Studies in Computational Intelligence, Springer Verlag, 727, 13-27, Jul. 2018, Peer-reviwed, Computer Daihinmin involves playing Daihinmin, a popular card game in Japan, by using a player program. Because strong player programs of Computer Daihinmin use machine-learning techniques, such as the Monte Carlo method, predicting the program’s behavior is difficult. In this study, we extract the features of the player program through decision tree analysis. The features of programs are extracted by generating decision trees based on three types of viewpoints. To show the validity of our method, computer experiments were conducted. We applied our method to three programs with relatively obvious behaviors, and we confirmed that the extracted features were correct by observing real behaviors of the programs.
Scientific journal, English

A decision tree analysis of a multi-player card game with imperfect information
Masato Konishi; Seiya Okubo; Tetsuro Nishino; Mitsuo Wakatsuki
International Journal of Software Innovation, Taru Publications, 6, 3, 1-17, Jul. 2018, Peer-reviwed, This article describes how computer Daihinmin involves playing Daihinmin, a popular card game in Japan, by using a player program. Because strong player programs of Computer Daihinmin use machine-learning techniques, such as the Monte Carlo method, predicting the program's behavior is difficult. In this article, the authors extract the features of the player program through decision tree analysis. The features of programs are extracted by generating decision trees based on three types of viewpoints. To show the validity of their method, computer experiments were conducted. The authors applied their method to three programs with relatively obvious behaviors, and they confirmed that the extracted features were correct by observing real behaviors of the programs.
Scientific journal, English

Strengthening methods of Computer Daihinmin programs
Mitsuo Wakatsuki; Yasuki Dobashi; Tasuku Mitsuishi; Seiya Okubo; Tetsuro Nishino
Proceedings of the 30th International Conference on Computer Applications in Industry and Engineering (CAINE 2017), 229-236, Oct. 2017, Peer-reviwed
International conference proceedings, English

A much faster algorithm for finding a maximum clique with computational experiments
Etsuji Tomita; Sora Matsuzaki; Atsuki Nagao; Hiro Ito; Mitsuo Wakatsuki
Journal of Information Processing, Information Processing Society of Japan, 25, 667-677, 01 Aug. 2017, Peer-reviwed, We present further improvements to a branch-and-bound maximum-clique-finding algorithm MCS (WALCOM 2010, LNCS 5942, pp.191-203) that was shown to be fast. First, we employ a variant of an efficient approximation algorithm KLS for finding a maximum clique. Second, we make use of appropriate sorting of vertices only near the root of the search tree. Third, we employ a lightened approximate coloring mainly near the leaves of the search tree. A new algorithm obtained from MCS with the above improvements is named k5_MCT. It is shown that k5_MCT is much faster than MCS by extensive computational experiments. In particular, k5_MCT is shown to be faster than MCS for gen400 p0.9 75, gen400 p0.9 65 and gen400 p0.9 55 by over 81,000, 39,000 and 19,000 times, respectively.
Scientific journal, English

Toward a statistical analysis of computer Daihinmin
Seiya Okubo; Yuuta Kado; Yamato Takeuchi; Mitsuo Wakatsuki; Tetsuro Nishino
Proceedings of the 5th International Conference on Applied Computing & Information Technology, 1-6, Jul. 2017, Peer-reviwed
International conference proceedings, English

A Much Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
Etsuji Tomita; Kohei Yoshida; Takuro Hatta; Atsuki Nagao; Hiro Ito; Mitsuo Wakatsuki
Frontiers in Algorithmics, FAW 2016, SPRINGER INT PUBLISHING AG, 9711, 215-226, Jun. 2016, Peer-reviwed, We present improvements to a branch-and-bound maximum-clique-finding algorithm MCS (WALCOM 2010, LNCS 5942, pp. 191-203) that was shown to be fast. First, we employ an efficient approximation algorithm for finding a maximum clique. Second, we make use of appropriate sorting of vertices only near the root of the search tree. Third, we employ a lightened approximate coloring mainly near the leaves of the search tree. A new algorithm obtained from MCS with the above improvements is named MCT. It is shown that MCT is much faster than MCS by extensive computational experiments. In particular, MCT is shown to be faster than MCS for gen400_p0.9_75 and gen400_p0.9_65 by over 328,000 and 77,000 times, respectively.
International conference proceedings, English

A decision making method based on society of mind theory in multi-player imperfect information games
Mitsuo Wakatsuki; Mari Fujimura; Tetsuro Nishino
International Journal of Software Innovation, IGI Global, 4, 2, 58-70, Apr. 2016, Peer-reviwed
Scientific journal, English

A Decision Making Method Based on Society of Mind Theory in Multi-player Imperfect Information Games
Mitsuo Wakatsuki; Mari Fujimura; Tetsuro Nishino
3RD INTERNATIONAL CONFERENCE ON APPLIED COMPUTING AND INFORMATION TECHNOLOGY (ACIT 2015) 2ND INTERNATIONAL CONFERENCE ON COMPUTATIONAL SCIENCE AND INTELLIGENCE (CSI 2015), IEEE, 69-74, Jul. 2015, Peer-reviwed, We are concerned with a card game called Daihinmin, which is a multi-player imperfect information game. Using Marvin Minsky's "Society of Mind" theory, we attempt to model the workings of the minds of game players. The UEC Computer Daihinmin Championship is held at The University of Electro-Communications every year, to bring together competitive client programs that correspond to players of Daihinmin, and contest their strengths. In this paper, we extract the behavior of client programs from actual competition records of the computer Daihinmin, and propose a method of building a system that determines the parameters of Daihinmin agencies by machine learning.
International conference proceedings, English

A source code plagiarism detecting method using sequence alignment with abstract syntax tree elements
Hiroshi Kikuchi; Takaaki Goto; Mitsuo Wakatsuki; Tetsuro Nishino
International Journal of Software Innovation, IGI Global, 3, 3, 41-56, Jul. 2015, Peer-reviwed
Scientific journal, English

A polynomial-time algorithm for checking the inclusion of deterministic restricted one-counter transducers which accept by final state
Mitsuo Wakatsuki; Etsuji Tomita; Tetsuro Nishino
Proceedings of the 30th International Conference on Computers and Their Applications (CATA-2015), 11-17, Mar. 2015, Peer-reviwed
International conference proceedings, English

A Polynomial-Time Algorithm for Checking the Equivalence of Deterministic Restricted One-Counter Transducers Which Accept by Final State
Mitsuo Wakatsuki; Etsuji Tomita; Tetsuro Nishino
SOFTWARE ENGINEERING, ARTIFICIAL INTELLIGENCE, NETWORKING AND PARALLEL/DISTRIBUTED COMPUTING, SPRINGER-VERLAG BERLIN, 569, 131-144, 2015, Peer-reviwed, This paper is concerned with a subclass of deterministic pushdown transducers, called deterministic restricted one-counter transducers (droct's), and studies the equivalence problem for droct's which accept by final state. In the previous study, we presented a polynomial-time algorithm for checking the equivalence of real-time droct's. By extending the technique, we present a polynomial-time algorithm for checking the equivalence of non-real-time droct's.
International conference proceedings, English

A Source Code Plagiarism Detecting Method Using Alignment with Abstract Syntax Tree Elements
Hiroshi Kikuchi; Takaaki Goto; Mitsuo Wakatsuki; Tetsuro Nishino
2014 15TH IEEE/ACIS INTERNATIONAL CONFERENCE ON SOFTWARE ENGINEERING, ARTIFICIAL INTELLIGENCE, NETWORKING AND PARALLEL/DISTRIBUTED COMPUTING (SNPD), IEEE, 375-380, Jun. 2014, Peer-reviwed, Learning to program is an important subject in computer science courses. During programming exercises, plagiarism by copying and pasting can lead to problems for fair evaluation. Some methods of plagiarism detection are currently available, such as sim. However, because sim is easily influenced by changing the identifier or program statement order, it fails to do enough to support plagiarism detection.
In this paper, we propose a plagiarism detection method which is not influenced by changing the identifier or program statement order. We also explain our method's capabilities by comparing it to the sim plagiarism detector. Furthermore, we reveal how our method successfully detects the presence of plagiarism.
International conference proceedings, English

An improved extended result on polynomial-time solvability of the maximum clique problem
Hiroaki Nakanishi; Etsuji Tomita; Mitsuo Wakastuki; Tetsuro Nishino
電子情報通信学会論文誌D分冊, 電子情報通信学会, J97-D, 6, 1106-1121, Jun. 2014, Peer-reviwed
Scientific journal, Japanese

A polynomial-time algorithm for checking the equivalence for real-time deterministic restricted one-counter transducers which accept by final state
Mitsuo Wakatsuki; Etsuji Tomita; Tetsuro Nishino
International Journal of Computer and Information Science, ACIS International, 14, 2, 45-53, Dec. 2013, Peer-reviwed
Scientific journal, English

A polynomial-time algorithm for checking the equivalence for real-time deterministic restricted one-counter transducers which accept by final state
Mitsuo Wakatsuki; Etsuji Tomita; Tetsuro Nishino
SNPD 2013 - 14th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing, 459-465, Jul. 2013, Peer-reviwed, This paper is concerned with a subclass of deterministic pushdown transducers, called deterministic restricted one-counter transducers (droct's), and studies the equivalence problem for real-time droct's which accept by final state. After providing some properties of these droct's, we present a polynomial-time algorithm for checking the equivalence for these droct's. © 2013 IEEE.
International conference proceedings, English

A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique with Computational Experiments
Etsuji Tomita; Yoichi Sutani; Takanori Higashi; Mitsuo Wakatsuki
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E96D, 6, 1286-1298, Jun. 2013, Peer-reviwed, Many problems can be formulated as maximum clique problems. Hence, it is highly important to develop algorithms that can find a maximum clique very fast in practice. We propose new approximate coloring and other related techniques which markedly improve the run time of the branch-and-bound algorithm MCR (J. Global Optim., 37, pp.95-111, 2007), previously shown to be the fastest maximum-clique-finding algorithm for a large number of graphs. The algorithm obtained by introducing these new techniques in MCR is named MCS. It is shown that MCS is successful in reducing the search space quite efficiently with low overhead. Extensive computational experiments confirm the superiority of MCS over MCR and other existing algorithms. It is faster than the other algorithms by orders of magnitude for several graphs. In particular, it is faster than MCR for difficult graphs of very high density and for very large and sparse graphs, even though MCS is not designed for any particular type of graph. MCS can be faster than MCR by a factor of more than 100,000 for some extremely dense random graphs. This paper demonstrates in detail the effectiveness of each new techniques in MCS, as well as the overall contribution.
Scientific journal, English

An extended result on polynomial-time solvability of the maximum clique problem
Hiroaki Nakanishi; Etsuji Tomita; Mitsuo Wakatsuki; Tetsuro Nishino
The IEICE Transactions on Information and Systems (Japanese Edition), The Institute of Electronics, Information and Communication Engineers, J95-D, 9, 1716-1728, Sep. 2012, Peer-reviwed, 典型的なNP完全問題である最大クリーク問題に対し,本論文では,次の結果を示す:"節点数nの一般グラフにおいて,Gの最大次数△が△≤2.994dlgn(d≥0:定数)なる条件を満たすとき,このグラフの最大クリーク問題はO(n^<1+d>)なる多項式時間で可解である."これに先立ち,最大次数△が△≤2.773dlgn(d≥0:定数)である場合に同様の結果を得ている(信学論(D),vol.J94-D,no.12,pp.2037-2046)が,本論文では,前結果における状況をより詳細に解析した上で,最大時間計算量が大きくなる場合に対して,更に詳細な場合分けを伴ったアルゴリズムと時間計算量解析を導入することにより,本結果を得ている.
Scientific journal, Japanese

A further improved result on polynomial-time solvability of the maximum clique problem
Hiroaki Nakanishi; Etsuji Tomita; Mitsuo Wakatsuki; Tetsuro Nishino
The IEICE Transactions on Information and Systems (Japanese Edition), The Institute of Electronics, Information and Communication Engineers, J94-D, 12, 2037-2046, Dec. 2011, Peer-reviwed, NP完全である最大クリーク問題に対して,本論文では,"節点数nの一般グラフにおいて,最大次数ΔがΔ≤2.773dlgn(d≥0:定数)なる条件を満たしているとき,このグラフの最大クリーク問題はO(n^<1+d>)なる多項式時間で可解である."ことを示す.これは,先の発表結果(信学論(D),vol.J94-D,no.5,pp.843-851)の改良であり,最大次数の上限に関する定数をいっそう増大させて,この定数2.773を得ている.更に,前発表ではd≥1であった条件をd≥0へと拡張している.これにより,dが0に近づくに従い,最大時間計算量はO(n)に近づく.これは,前発表ではグラフを隣接行列で表現することを前提としていたのに対して,本論文では隣接リスト表現を用いることにより実現している.
Scientific journal, Japanese

An image transformation algorithm for image compression based on quantum cellular automata
Kazuki Ohata; Tetsuro Nishino; Mitsuo Wakatsuki
RIMS Kokyuroku, Research Institute for Mathematical Sciences, Kyoto University, 1744, 181-184, Jun. 2011
Research institution, Japanese

On polynomial-time solvability of the maximum clique problem
Hiroaki Nakanishi; Etsuji Tomita; Mitsuo Wakatsuki; Tetsuro Nishino
RIMS Kokyuroku, Research Institute for Mathematical Sciences, Kyoto University, 1744, 169-176, Jun. 2011
Research institution, Japanese

A polynomial-time algorithm for checking the equivalence of real-time deterministic restricted one-counter transducers which accept by final state
Mitsuo Wakatsuki; Kazushi Seino; Etsuji Tomita; Tetsuro Nishino
RIMS Kokyuroku, Research Institute for Mathematical Sciences, Kyoto University, 京都大学, 1744, 1-10, Jun. 2011
Research institution, Japanese

Polynomial Time Identification of Strict Prefix Deterministic Finite State Transducers
Mitsuo Wakatsuki; Etsuji Tomita
GRAMMATICAL INFERENCE: THEORETICAL RESULTS AND APPLICATIONS, ICGI 2010, SPRINGER-VERLAG BERLIN, 6339, 313-316, Sep. 2010, Peer-reviwed, This paper is concerned with a subclass of finite state transducers, called strict prefix deterministic finite state transducers (SPDFST's for short), and studies a problem of identifying the subclass in the limit from positive data. After providing some properties of languages accepted by SPDFST's, we show that the class of SPDFST's is polynomial time identifiable in the limit from positive data in the sense of Yokomori.
International conference proceedings, English

A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
Etsuji Tomita; Yoichi Sutani; Takanori Higashi; Shinya Takahashi; Mitsuo Wakatsuki
WALCOM: ALGORITHMS AND COMPUTATION, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 5942, 191-203, Feb. 2010, Peer-reviwed, This paper proposes new approximate coloring and other related techniques which markedly improve the run time of the branch-and-bound algorithm MCR (J. Global Optim., 37, 95 111, 2007), previously shown to be the fastest maximum-clique-finding algorithm for a large number of graphs. The algorithm obtained by introducing these new techniques in MCR is named MCS. It is shown that MCS is successful in reducing the search space quite efficiently with low overhead. Consequently, it is shown by extensive computational experiments that. MCS is remarkably faster than MCR and other existing algorithms. It is faster than the other algorithms by an order of magnitude for several graphs. In particular, it is faster than MCR for difficult graphs of very high density and for very large and sparse graphs, even though MCS is not designed for any particular type of graphs. MCS can be faster than MCR. by a factor of more than 100,000 for sortie extremely dense random graphs.
International conference proceedings, English

Polynomial time identification of strict deterministic restricted one-counter automata in some class from positive data
Mitsuo Wakatsuki; Etsuji Tomita
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E91D, 6, 1704-1718, Jun. 2008, Peer-reviwed, A deterministic pushdown automaton (dpda) having just one stack symbol is called a deterministic restricted one-counter automaton (droca). When it accepts an input by empty stack, it is called strict. This paper is concerned with a subclass of real-time strict droca's, called Szilard strict droca's, and studies the problem of identifying the subclass in the limit from positive data. The class of languages accepted by Szilard strict droca's coincides with the class of Szilard languages (or, associated languages) of strict droca's and is incomparable to each of the class of regular languages and that of simple languages. After providing some properties of languages accepted by Szilard strict droca's, we show that the class of Szilard strict droca's is polynomial time identifiable in the limit from positive data in the sense of Yokomori. This identifiability is proved by giving an exact characteristic sample of polynomial size for a language accepted by a Szilard strict droca. The class of very simple languages, which is a proper subclass of simple languages, is also proved to be polynomial time identifiable in the limit from positive data by Yokomori, but it is yet unknown whether there exists a characteristic sample of polynomial size for any very simple language.
Scientific journal, English

A polynomial-time algorithm for checking the equivalence of real-time strict deterministic restricted one-counter transducers
Kazushi Seino; Etsuji Tomita; Mitsuo Wakatsuki
The Transactions of the Institute of Electronics, Information and Communication Engineers D, The Institute of Electronics, Information and Communication Engineers, J91-D, 5, 1188-1201, May 2008, Peer-reviwed, 決定性プッシュダウンオートマトン(dpda)の等価性判定問題は,任意のクラスに対する可解性が示されている.しかし,そのアルゴリズムの効率化については,必ずしも十分な解は得られていない.オートマトンや形式文法を基礎とするシステムにおける学習などにおいて,等価性判定は主要な役割を果たし,その効率向上を実現する上で,多項式時間の等価性判定可解性は非常に重要である.本論文では,スタック記号が単一という制限をもつ実時間空スタック受理式決定性限定ワンカウンタオートマトンに出力機構を付与した,実時間空スタック受理式決定性限定ワンカウンタ変換器について,筆者らが提唱してきた,分岐アルゴリズムと名づけた単純で直接的な等価性判定手法を用いることにより,その等価性判定が多項式時間で解決できることを示す.
Scientific journal, Japanese

A direct branching algorithm for checking the equivalence of a pair of non-realtime deterministic pushdown transducers
Kazushi Seino; Etsuji Tomita; Mitsuo Wakatsuki
The Transactions of the Institute of Electronics, Information and Communication Engineers D, The Institute of Electronics, Information and Communication Engineers, J90-D, 10, 2675-2690, Oct. 2007, Peer-reviwed, 決定性プッシュダウンオートマトン(dpda)の等価性判定問題は,任意のクラスに対して可解であるとの結論が明らかにされたが,その可解性の証明は非常に複雑である.これに対し,筆者らは,dpdaの部分クラスを対象とする,分岐アルゴリズムと名づけた単純で直接的な等価性判定手法を提唱してきた.そして,一方が実時間空スタック受理式である決定性プッシュダウン変換器(dpdt)に対しても,この等価性判定方式が,ほぼ直接的に適応可能であることを既に証明している.本論文では,dpdtに対するその結果を更に拡張し,かつ,その直接的単純性を保ちながら,両者にε-推移を許したある種のdpdt対に対しても等価性判定を可能とする拡張アルゴリズムを提唱する.
Scientific journal, Japanese

Polynomial time identification of finite state transducers in some class
Mitsuo Wakatsuki; Etsuji Tomita
Proc. Advanced ICT 2007 (AICT2007), 1-6, Sep. 2007
International conference proceedings, English

A unified algorithm for extending classes of languages identifiable in the limit from positive data
Mitsuo Wakatsuki; Etsuji Tomita; Go Yamada
GRAMMATICAL INFERENCE: ALGORITHMS AND APPLICATIONS, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 4201, 161-174, Sep. 2006, Peer-reviwed, We are concerned with a unified algorithm for extending classes of languages identifiable in the limit from positive data. Let L be a class of languages to be based on and let X be a class of finite subsets of strings. The extended class of L, denoted by C(L, X), is defined by these L and X. Here we give a sufficient condition for C(C, X) to be identifiable in the limit from positive data and we present a unified identification algorithm for it. Furthermore, we show that some proper subclasses of C (L, X) are polynomial time identifiable in the limit from positive data in the sense of Yokomori.
Scientific journal, English

Polynomial time learning of simple deterministic languages via queries and a representative sample
Yasuhiro Tajima; Etsuji Tomita; Mitsuo Wakatsuki; Matsuaki Terada
Theoretical Computer Science, Elsevier, 329, 1-3, 203-221, Dec. 2004, Peer-reviwed
Scientific journal, English

Polynomial time identification of strict deterministic restricted one-counter automata in some class from positive date
M Wakatsuki; K Teraguchi; E Tomita
GRAMMATICAL INFERENCE: ALGORITHMS AND APPLICATIONS, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 3264, 260-272, Oct. 2004, Peer-reviwed, A deterministic pushdown automaton (dpda) having just one stack symbol is called a deterministic restricted one-counter automaton (droca). When it accepts by empty stack, it is called strict. This paper is concerned with a subclass of real-time strict droca's called Szilard strict droca's. The class of languages accepted by Szilard strict droca's is incomparable to both the class of regular languages and that of simple languages. We show that the class of Szilard strict droca's is polynomial time identifiable in the limit from positive data in the sense of Yokomori. This identifiability is proved by giving an exact characteristic sample of polynomial size for a language accepted by a Szilard strict droca. The class of very simple languages is also proved to be polynomial time identifiable in the limit from positive data by Yokomori, but it is still unknown whether there exists a characteristic sample of polynomial size for any very simple language.
Scientific journal, English

Polynomial time learnability of simple deterministic languages from MAT and a representative sample
Y Tajima; E Tomita; M Wakatsuki
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E83D, 4, 757-765, Apr. 2000, Peer-reviwed, We propose a learning algorithm for simple deterministic languages from queries and a priori knowledge. To the learner, a special finite subset of the target language, called a representative sample, is provided at the beginning and two types of queries, equivalence queries and membership queries, are available. This learning algorithm constructs nonterminals of a hypothesis grammar based on Ishizaka(1990)'s idea. In Ishizaka(1990)'s algorithm, the learner makes rules as many as possible from positive counterexamples, and diagnoses wrong rules from negative counterexamples. In contrast, our algorithm guesses a simple deterministic grammar and diagnoses them using positive and negative counterexamples based on Angluin(1987)'s algorithm.
Scientific journal, English

Polynomial time MAT learning of simple deterministic languages with structural counterexamples
Yasuhiro Tajima; Etsuji Tomita; Mitsuo Wakatsuki
The Transactions of the Institute of Electronics, Information and Communication Engineers D-I, The Institute of Electronics, Information and Communication Engineers, J82-D-I, 4, 521-532, Apr. 1999, Peer-reviwed, 本論文において, 単純決定性言語の多項式時間厳密学習を可能にする一手法を示す. 一般に等価性質問は, 仮説文法の入力に対して, その生成言語が学習対象の言語と等価か否かを出力し, 非等価の場合には更にその根拠となる反例も出力する. ここで反例が正の反例の場合, 更に学習対象における導出構造も出力する質問を構造反例付き等価性質問と新たに定義する. このとき任意の単純決定性言語は, 所属性質問及び構造反例付き等価性質問を用いて, 単純決定性文法の族により多項式時間厳密学習可能であることを示す. この学習アルゴリズムにおける仮説文法の構成方法は, Ishizaka(1990)における考え方に基づき, 質問を行うアルゴリズムはAngluin(1987)における考え方に基づいている.
Scientific journal, Japanese

A polynomial-time algorithm for checking the inclusion for real-time deterministic restricted one-counter automata which accept by accept mode
K Higuchi; M Wakatsuki; E Tomita
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E81D, 1, 1-11, Jan. 1998, Peer-reviwed, A deterministic pushdown automaton (dpda) having just one stack symbol is called a deterministic restricted one-counter automaton (droca). A deterministic one-counter automaton (doca) is a dpda having only one stack symbol, with the exception of a bottom-of-stack marker. The class of languages accepted by droca's which accept by final state is a proper subclass of the class of languages accepted by doca's. Valiant has proved the decidability of the equivalence problem for doca's and the undecidability of the inclusion problem for doca's. Thus the decidability of the equivalence problem for droca's is obvious. In this paper, we evaluate the upper bound of the length of the shortest input string (shortest witness) that disproves the inclusion for a pair of real-time droca's which accept by accept mode, and present a direct branching algorithm for checking the inclusion for a pair of languages accepted by these droca's. Then we show that the worst-case time complexity of our algorithm is polynomial in the size of these droca's.
Scientific journal, English

An algorithm for finding a maximum weight clique in an integer-weighted graph
鄭戴勇; 富田悦次; 若月光夫
Bulletin of the University of Electro-Communications, The University of Electro-Communications, 10, 1, 1-4, Jun. 1997
Research institution, Japanese

A simple and efficient branch and bound algorithm for finding a maximum clique with experimental evaluations
Etsuji Tomita; Ken'Ichi Imamatsu; Yasuhiro Kohata; Mitsuo Wakatsuki
Systems and Computers in Japan, John Wiley and Sons Inc., 28, 5, 60-67, May 1997, Peer-reviwed, In this paper a simple and efficient branch and bound algorithm to extract a maximum clique from an undirected graph is proposed. In this method the crucial point for improving the efficiency of the algorithm is how to make the search space small using a tighter bound. However, the processing time to implement that bound must be kept small. Thus, in this paper a very simple and clever sequential approximate coloring-arranging method is developed considering trade-offs between these two factors. Using this, an upper bound on the maximum clique size at each search step is computed and branches are pruned based on this bound. The total computation time has been success-fully reduced using this method. It has been verified either by computational experiments or by comparing published experimental results that this algorithm is faster than other major algorithms on a wide range of random graphs with 600 or less vertices and on a number of random graphs with 1,000 vertices. © 1997 Scripta Technica, Inc.
Scientific journal, English

Some properties of deterministic restricted one-counter automata
K Higuchi; M Wakatsuki; E Tomita
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E79D, 7, 914-924, Jul. 1996, Peer-reviwed, A deterministic pushdown automaton (dpda) having just one stack symbol is called a deterministic restricted one-counter automaton (droca). A deterministic one-counter automaton (doca) is a dpda having only one stack symbol, with the exception of a bottom-of-stack marker. The class of languages accepted by droca's is a proper subclass of the class of languages accepted by doca's. Valiant has shown that the regularity problem for doca's is decidable in a single exponential worst-case time complexity. In this paper, we prove that the class of languages accepted by droca's which accept by final state is incomparable with the class of languages accepted by droca's which accept by empty stack (strict droca's), and that the intersection of them is equal to the class of strict regular languages. In addition, we present a new direct branching algorithm for checking the regularity for not only a strict droca but also a real-time droca which accepts by final state. Then we show that the worst-case time complexity of our algorithm is polynomial in the size of each droca.
Scientific journal, English

A simple and efficient branch and bound algorithm for finding a maximum clique with the experimental evaluations
Etsuji Tomita; Kenichi Imamatsu; Yasuhiro Kohata; Mitsuo Wakatsuki
The Transactions of the Institute of Electronics, Information and Communication Engineers D-I, J79-D-I, 1, 1-8, Jan. 1996, Peer-reviwed
Scientific journal, Japanese

A POLYNOMIAL-TIME ALGORITHM FOR CHECKING THE INCLUSION FOR REAL-TIME DETERMINISTIC RESTRICTED ONE-COUNTER AUTOMATA WHICH ACCEPT BY FINAL-STATE
K HIGUCHI; M WAKATSUKI; E TOMITA
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, IEICE-INST ELECTRON INFO COMMUN ENG, E78D, 8, 939-950, Aug. 1995, Peer-reviwed, A deterministic pushdown automaton (dpda) having just one stack symbol is called a deterministic restricted one-counter automaton (droca). A deterministic one-counter automaton (doca) is a dpda having only one stack symbol, with the exception of a bottom-of-stack marker. The class of languages accepted by droca's which accept by final state is a proper subclass of the class of languages accepted by doca's. Valiant has proved the decidability of the equivalence problem for doca's and the undecidability of the inclusion problem for doca's. Hence the decidability of the equivalence problem for droca's is obvious. In this paper, we evaluate the upper bound of the length df the shortest input string (witness) that disproves the inclusion for a pair of real-time droca's which accept by final state, and present a new direct branching algorithm for checking the inclusion for a pair of languages accepted by these droca's. Then we show that the worst-case time complexity of our algorithm is polynomial in the size of these droca's.
Scientific journal, English

A simple algorithm for finding a maximum weight clique based upon an approximate coloring
Kenichi Imamatsu; Etsuji Tomita; Mitsuo Wakatsuki
Bulletin of the University of Electro-Communications, The University of Electro-Communications, 8, 1, 17-21, Jun. 1995
Research institution, Japanese

A POLYNOMIAL-TIME ALGORITHM FOR CHECKING THE INCLUSION FOR STRICT DETERMINISTIC RESTRICTED ONE-COUNTER AUTOMATA
K HIGUCHI; E TOMITA; M WAKATSUKI
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, IEICE-INST ELECTRON INFO COMMUN ENG, E78D, 4, 305-313, Apr. 1995, Peer-reviwed, A deterministic pushdown automaton (dpda) having just one stack symbol is called a deterministic restricted one-counter automaton (droca). When it accepts by empty stack, it is called strict. A deterministic one-counter automaton (doca) is a dpda having only one stack symbol, with the exception of a bottom-of-stack marker. The class of languages accepted by strict droca's is a subclass of the class of languages accepted by doca's. Valiant has proved the decidability of the equivalence problem for doca's and the undecidability of the inclusion problem for doca's. Hence the decidability of the equivalence problem for strict droca's is obvious. In this paper, we present a new direct branching algorithm for checking the inclusion for a pair of languages accepted by strict droca's. Then we show that the worst-case time complexity of our algorithm is polynomial with respect to these automata.
Scientific journal, English

A FAST ALGORITHM FOR CHECKING THE INCLUSION FOR VERY SIMPLE DETERMINISTIC PUSHDOWN-AUTOMATA
M WAKATSUKI; E TOMITA
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E76D, 10, 1224-1233, Oct. 1993, Peer-reviwed, We are concerned with a subclass of deterministic pushdown automata (dpda) called very simple dpda's, and present a new direct branching algorithm for checking the inclusion for a pair of languages accepted by these dpda's. As usual, we take the maximal thickness (i.e., the length of the shortest input strings that make each stack symbol go to empty) of all stack symbols into account as one parameter of the given dpda's. Then the worst-case time complexity of our algorithm is polynomial with respect to these parameters. Without considering the thickness, the complexity is single exponential in the description length of the given dpda's. As far as we are concerned with very simple dpda's, our algorithm is very simple and direct, and is faster and much better than the previously given algorithms for the inclusion problem of dpda's.
Scientific journal, English

On the upper bound of the shortest length of input strings to decide equivalence of simple deterministic pushdown automata
Mitsuo Wakatsuki; Etsuji Tomita
The Transactions of the Institute of Electronics, Information and Communication Engineers D-I, 電子情報通信学会, J75-D-I, 10, 950-953, Oct. 1992, Peer-reviwed
Scientific journal, Japanese

An improved branching algorithm for checking the equivalence of simple DPDA's and its worst-case time complexity
Mitsuo Wakatsuki; Etsuji Tomita
The Transactions of the Institute of Electronics, Information and Communication Engineers D-I, 電子情報通信学会, J74-D-I, 9, 595-603, Sep. 1991, Peer-reviwed
Scientific journal, Japanese

A direct branching algorithm for checking equivalence of simple deterministic pushdown automata
Mitsuo Wakatsuki; Etsuji Tomita; Chugo Fujihashi
The Transactions of the Institute of Electronics, Information and Communication Engineers D-I, 電子情報通信学会, J72-D-I, 5, 327-334, May 1989, Peer-reviwed
Scientific journal, Japanese

情報工学のための離散数学入門
Tetsuro Nishino; Mitsuo Wakatsuki
Scholarly book, Japanese, Joint work, 第１章「集合」，第２章「関係と関数」，第３章「論理と証明法」，およびそれらの演習問題解答, 数理工学社, 25 Aug. 2015, 9784864810326

Applied Automata Engineering
Tetsuro Nishino; Mitsuo Wakatsuki; Takaaki Goto
Japanese, Joint work, 第１章 オートマトン理論, Corona Publishing Co., Ltd., Feb. 2012

UNIXコンピュータリテラシー - ネットワーク時代の計算機利用とモラル -（第2版）
渡辺成良; 若月光夫; 織田健
Japanese, Joint work, 共立出版株式会社, Apr. 2001

UNIXコンピュータリテラシー - ネットワーク時代の計算機利用とモラル -
渡辺成良; 若月光夫; 織田健
Japanese, Joint work, 共立出版株式会社, Jan. 1997

コンピュータUNOにおけるモンテカルロ木探索について
山﨑優; 大久保誠也; 若月光夫; 西野哲朗
Oral presentation, Japanese, 情報処理学会第51回ゲーム情報学研究会, 情報処理学会ゲーム情報学研究会, 国立情報学研究所12Ｆ会議室, Japan, Domestic conference
09 Mar. 2024
08 Mar. 2024- 09 Mar. 2024

コンピュータUNOにおけるモンテカルロ法のREINFORCEアルゴリズムによる方策学習
新木優典; 大久保誠也; 若月光夫; 西野哲朗
Oral presentation, Japanese, 情報処理学会第51回ゲーム情報学研究会, 情報処理学会ゲーム情報学研究会, 国立情報学研究所12Ｆ会議室, Japan, Domestic conference
09 Mar. 2024
08 Mar. 2024- 09 Mar. 2024

コンピュータUNOにおける発見的に得た戦略に関する研究
齋藤康平; 大久保誠也; 若月光夫; 西野哲朗
Oral presentation, Japanese, 情報処理学会第85回全国大会
04 Mar. 2023
02 Mar. 2023- 04 Mar. 2023

コンピュータUNOにおけるモンテカルロ法プレイヤの構築
稲葉颯弥; 大久保誠也; 若月光夫; 西野哲朗
Oral presentation, Japanese, 情報処理学会第85回全国大会
04 Mar. 2023
02 Mar. 2023- 04 Mar. 2023

D-Waveの量子アニーリングマシン上における最大クリーク探索の実験的評価
白石千尋; 大久保誠也; 若月光夫; 西野哲朗
Oral presentation, Japanese, 情報処理学会第85回全国大会
04 Mar. 2023
02 Mar. 2023- 04 Mar. 2023

大学図書館における対話型図書推薦システムに関する研究
田代大成; 大久保誠也; 若月光夫; 西野哲朗
Oral presentation, Japanese, 情報処理学会第85回全国大会
03 Mar. 2023
02 Mar. 2023- 04 Mar. 2023

Watson Assistantを用いたサイトレビューによる参考書の難易度推定手法
Muhammad Fauzan Mahfuzh; 大久保誠也; 若月光夫; 西野哲朗
Oral presentation, Japanese, 情報処理学会第85回全国大会
03 Mar. 2023
02 Mar. 2023- 04 Mar. 2023

小説の内容を表すキーワードの抽出に関する研究
若井龍弥; 大久保誠也; 若月光夫; 西野哲朗
Oral presentation, Japanese, 情報処理学会第85回全国大会
03 Mar. 2023
02 Mar. 2023- 04 Mar. 2023

セクション情報を用いた日本語長文文書の抽象型自動要約
沢畑英之; 大久保誠也; 若月光夫; 西野哲朗
Oral presentation, Japanese, 情報処理学会第85回全国大会
02 Mar. 2023
02 Mar. 2023- 04 Mar. 2023

最大クリーク抽出アルゴリズムMCTのさらなる高速化
Jiro Yanagisawa; Etsuji Tomita; Kengo Katayama; Kazuho Kanahara; Takahisa Toda; Hiro Ito; Mitsuo Wakatsuki; Tetsuro Nishino
Oral presentation, Japanese, IEICE Technical Report, COMP2020-35, Domestic conference
08 Mar. 2021

コンピュータ大貧民における戦略の定式化に関する研究
Iori Kawasaki; Seiya Okubo; Mitsuo Wakatsuki; Tetsuro Nishino
Oral presentation, Japanese, IPSJ SIG Technical Report, 2021-GI-45, Domestic conference
05 Mar. 2021

コンピュータ大貧民におけるレーティング手法の最適化に関する研究
Kouki Fujimura; Seiya Okubo; Mitsuo Wakatsuki; Tetsuro Nishino
Oral presentation, Japanese, IPSJ SIG Technical Report, 2021-GI-45, Domestic conference
05 Mar. 2021

コンピュータ大貧民におけるレーティング手法について
Jumpei Gokaya; Seiya Okubo; Mitsuo Wakatsuki; Tetsuro Nishino
Oral presentation, Japanese, IPSJ SIG Technical Report, 2020-GI-43, Domestic conference
13 Mar. 2020

コンピュータ大貧民における提出手の影響に関する研究
Tasuku Mitsuishi; Seiya Okubo; Mitsuo Wakatsuki; Tetsuro Nishino
Oral presentation, Japanese, IPSJ SIG Technical Report, 2018-GI-41, Domestic conference
09 Mar. 2019

大貧民におけるモンテカルロ法の報酬値に関する研究
Yasuki Dobashi; Seiya Okubo; Mitsuo Wakatsuki; Tetsuro Nishino
Oral presentation, Japanese, IPSJ SIG Technical Report, 2018-GI-41, Domestic conference
09 Mar. 2019

コンピュータ大貧民におけるローカルルールの効果に関する研究
Yuuta Kado; Seiya Okubo; Mitsuo Wakatsuki; Tetsuro Nishino
Oral presentation, Japanese, IPSJ SIG Technical Report, 2018-GI-41, Domestic conference
08 Mar. 2019

大貧民におけるプレイヤーの提出手の傾向に関する研究
Yamato Takeuchi; Seiya Okubo; Mitsuo Wakatsuki; Tetsuro Nishino
Oral presentation, Japanese, IPSJ SIG Technical Report, 2018-GI-41, Domestic conference
08 Mar. 2019

最大クリーク抽出アルゴリズムMCTの高速化(2)
Sora Matsuzaki; Etsuji Tomita; Atsuki Nagao; Hiro Ito; Mitsuo Wakatsuki; Tetsuro Nishino; Kengo Katayama; Kazuho Kanehara
Oral presentation, Japanese, 2018 LA Symposium in Winter, No.1, Domestic conference
04 Feb. 2019

近似最大クリーク抽出アルゴリズムIKLSの反復回数に対する適切な制御方法
Atsuki Nagao; Sora Matsuzaki; Etsuji Tomita; Hiro Ito; Mitsuo Wakatsuki; Tetsuro Nishino
Oral presentation, Japanese, Technical Report of IEICE, COMP2018-23, Domestic conference
26 Oct. 2018

最大クリーク抽出アルゴリズムMCTの高速化
Sora Matsuzaki; Etsuji Tomita; Atsuki Nagao; Hiro Ito; Mitsuo Wakatsuki; Tetsuro Nishino
Oral presentation, Japanese, IPSJ SIG Technical Report, 2018-MPS-120, Domestic conference
26 Sep. 2018

決定木を用いた大貧民プログラムの分析に関する研究
Masato Konishi; Seiya Okubo; Mitsuo Wakatsuki; Tetsuro Nishino
Oral presentation, Japanese, IPSJ SIG Technical Report, 2016-GI-36, Domestic conference
05 Aug. 2016

最大クリーク抽出アルゴリズムMCSの高速化
Kohei Yoshida; Takuro Hatta; Etsuji Tomita; Atsuki Nagao; Hiro Ito; Mitsuo Wakatsuki
Oral presentation, Japanese, IPSJ SIG Technical Report, 2016-AL-157, Domestic conference
06 Mar. 2016

A polynomial-time algorithm for checking the inclusion of deterministic restricted one-counter transducers which accept by final state
Mitsuo Wakatsuki; Etsuji Tomita; Tetsuro Nishino
Oral presentation, Japanese, 2015 LA Symposium in Winter, No.14, Domestic conference
28 Jan. 2016

An improved branch-and-bound algorithm for finding a maximum clique
Takuro Hatta; Etsuji Tomita; Hiro Ito; Mitsuo Wakatsuki
Oral presentation, Japanese, 2015 LA Symposium in Summer, No.9, Domestic conference
16 Jul. 2015

A further improved extended result on polynomial-time solvability of the maximum clique problem
Hiroaki Nakanishi; Etsuji Tomita; Mitsuo Wakatsuki; Tetsuro Nishino
Oral presentation, Japanese, 電子情報通信学会コンピュテーション研究会技術研究報告，COMP2014-13,コンピュテーション研究会
14 Jun. 2014

A polynomial time learning algorithm for real-time deterministic restricted one-counter transducers from queries and counterexamples
Mitsuo Wakatsuki; Etsuji Tomita; Tetsuro Nishino
Oral presentation, Japanese, 2013 LA Symposium in Winter, No.21
30 Jan. 2014

A new technique to improve code readability by omitting similar source code patterns
Hiroshi Kikuchi; Takaaki Goto; Mitsuo Wakatsuki; Tetsuro Nishino
Oral presentation, Japanese, IEICE Technical Report, Knowledge-Based Software Engineering, KBSE2013-36, 電気通信大学 東3号館301号室
12 Sep. 2013

学習ゲームを用いた発達障害児向け文字学習支援システム
金山貴泰; 浅野久美子; 西野哲朗; 若月光夫
Oral presentation, Japanese, 情報処理学会数理モデル化と問題解決研究会研究報告, 情報処理学会数理モデル化と問題解決研究会, 北海道大学 百年記念会館, Domestic conference
23 May 2013

A polynomial time learning algorithm for deterministic restricted one-counter transducers in some class from queries and counterexamples
Mitsuo Wakatsuki; Etsuji Tomita; Tetsuro Nishino
Oral presentation, Japanese, 2012 LA Symposium in Winter, No.13
Jan. 2013

An improved extended result on polynomial-time solvability of the maximum clique problem
Hiroaki Nakanishi; Etsuji Tomita; Mitsuo Wakatsuki; Tetsuro Nishino
Oral presentation, Japanese, The Institute of Electronics, Information and Communication Engineers, Techincal Report, COMP2012-28
Sep. 2012

Automatic optimizing of routine for computer daihinmin using genetic algorithm
Yoshitaka Umikawa; Tetsuro Nishino; Mitsuo Wakatsuki
Public symposium, Japanese, 第6回エンターテイメントと認知科学シンポジウム, The University of Electro-Communications, 調布
Mar. 2012

A polynomial-time algorithm for checking the equivalence of deterministic restricted one-counter transducers which accept by final state
Mitsuo Wakatsuki; Kazushi Seino; Etsuji Tomita; Tetsuro Nishino
Oral presentation, Japanese, 2011 LA Symposium in Winter, No.11
Jan. 2012

An extended result on polynomial-time solvability of the maximum clique problem
Hiroaki Nakanishi; Etsuji Tomita; Mitsuo Wakatsuki; Tetsuro Nishino
Oral presentation, Japanese, The Institute of Electronics, Information and Communication Engineers, Techincal Report, COMP2011-30
Oct. 2011

A further improved result on polynomial-time solvability of the maximum clique problem
Hiroaki Nakanishi; Etsuji Tomita; Mitsuo Wakatsuki; Tetsuro Nishino
Oral presentation, Japanese, The Institute of Electronics, Information and Communication Engineers, Techincal Report, COMP2011-6
Apr. 2011

An image transformation algorithm for image compression based on quantum cellular automata
Kazuki Oohata; Tetsuro Nishino; Mitsuo Wakatsuki
Oral presentation, Japanese, 2010 LA Symposium in Winter, No.S2
Feb. 2011

On polynomial-time solvability of the maximum clique problem
Hiroaki Nakanishi; Etsuji Tomita; Mitsuo Wakatsuki; Tetsuro Nishino
Oral presentation, Japanese, 2010 LA Symposium in Winter, No.32
Feb. 2011

A polynomial-time algorithm for checking the equivalence of real-time deterministic restricted one-counter transducers which accept by final state
Mitsuo Wakatsuki; Kazushi Seino; Etsuji Tomita; Tetsuro Nishino
Oral presentation, Japanese, 2010 LA Symposium in Winter, No.1
Feb. 2011

鳥の歌文法解析の自動化
Tooru Suzuki; Mitsuo Wakatsuki; Tetsuro Nishino
Oral presentation, Japanese, 2010 LA Symposium in Summer, No.S6
Jul. 2010

最大クリーク抽出の単純な最大時間計算量評価と多項式時間的可解性
Hiroaki Nakanishi; Etsuji Tomita; Mitsuo Wakatsuki
Oral presentation, Japanese, 2009 LA Symposium in Winter, No.29
Feb. 2010

A polynomial time algorithm for checking the equivalence of strict deterministic restricted one-counter transducers
Mitsuo Wakatsuki; Kazushi Seino; Etsuji Tomita; Tetsuro Nishino
Oral presentation, Japanese, 2009 LA Symposium in Winter, No.14
Feb. 2010

A simple and faster algorithm for finding a maximum clique
Etsuji Tomita; Yoichi Sutani; Takanori Higashi; Shinya Takahashi; Mitsuo Wakatsuki
Oral presentation, English, Information Processing Society of Japan, IPSJ SIG Technical Report, 2010-AL-128-10
Jan. 2010

鳥の歌構造解析におけるk可逆オートマトンとNグラムモデルの関係について
常田宏和; 若月光夫; 西野哲朗
Oral presentation, Japanese, 2009 LA Symposium in Summer, No.16
Jul. 2009

The learning problem for DAIHINMIN programs
Seiya Okubo; Mitsuo Wakatsuki; Tetsuro Nishino
Public symposium, Japanese, 第3回エンターテイメントと認知科学シンポジウム, The University of Electro-Communications, 東京都調布市
Mar. 2009

Report of the Third UEC computer DAIHINMIN championship (UECda-2008)
Seiya Okubo; Takeru Honda; Hideaki Manabe; Takuro Iizuka; Khan Md; Mahfuzus Salam; Hirokazu Tokida; Takeaki Gima; Tomoya Suzuki; Aimi Tanaka; Kanako Matsuno; Mitsuo Wakatsuki; Tetsuro Nishino
Oral presentation, Japanese, Information Processing Society of Japan, IPSJ SIG Technical Report, 2009-GI-21-3
Mar. 2009

An identification in the limit from positive data for some subclasses of languages extended by homomorphisms
Mitsuo Wakatsuki; Etsuji Tomita
Oral presentation, Japanese, Information Processing Society of Japan, IPSJ SIG Technical Report, 2009-MPS-73-20
Mar. 2009

オートマトンの学習困難性を安全性の基盤とする暗号システムについて
大久保誠也; 西野哲朗; 若月光夫
Oral presentation, Japanese, 2008 LA Symposium in Winter, No.25
Feb. 2009

A parallelization of an algorithm for finding a maximum clique on shared memory computers
Mitsuo Wakatsuki; Shinya Takahashi; Etsuji Tomita
Oral presentation, Japanese, Information Processing Society of Japan, IPSJ SIG Technical Report, 2008-MPS-71-5
Sep. 2008

Polynomial time identification of finite state transducers in some class
Mitsuo Wakatsuki; Etsuji Tomita
Oral presentation, English, IPSJ SIG Techincal Report, 2007-AL-115
Nov. 2007

A polynomial-time algorithm for checking the equivalence of real-time strict deterministic restricted one-counter transducers
Kazushi Seino; Etsuji Tomita; Mitsuo Wakatsuki
Oral presentation, Japanese, The Institute of Electronics, Information and Communication Engineers, Techincal Report, COMP2007-47
Oct. 2007

A unified algorithm for extending classes of languages identifiable in the limit from positive data
Mitsuo Wakatsuki; Etsuji Tomita; Go Yamada
Oral presentation, English, 2006 LA Symposium in Summer, No.18
Aug. 2006

A direct branching algorithm for checking the equivalence of a pair of non-real-time deterministic pushdown transducers
Kazushi Seino; Etsuji Tomita; Mitsuo Wakatsuki
Oral presentation, Japanese, Information Processing Society of Japan, IPSJ Technical Report, 2006-AL-104-9
Jan. 2006

A unified algorithm for extending classes of languages identifiable in the limit from positive data
Mitsuo Wakatsuki; Etsuji Tomita; Go Yamada
Oral presentation, English, Information Processing Society of Japan, IPSJ Techinical Report, 2005-AL-102
Sep. 2005

Polynomial time identification of strict deterministic restricted one-counter automata in some class from positive data
Mitsuo Wakatsuki; Kiyoshi Teraguchi; Etsuji Tomita
Oral presentation, English, Technical Report of IEICE, COMP2003-83
Mar. 2004

A Unified Method of Identification in the Limit from Positive Data in Some Subclasses of Regular Languages
若月光夫; 山田 剛; 富田悦次
Oral presentation, Japanese, 2002 LA Symposium in Summer, No.22
Jul. 2002

Polynomial time identification in the limit of regular languages in some subclass from positive data
吉成智和; 富田悦次; 若月光夫
Oral presentation, Japanese, Technical Report of IEICE, COMP2001-83
Mar. 2002

A polynomial time inference of generalized sequential machines in some class
西田大; 富田悦次; 若月光夫
Oral presentation, Japanese, 2001 LA Symposium in winter, No.45
Feb. 2002

Polynomial-time identification in the limit of counters in some class from positive data
寺口 潔; 富田悦次; 若月光夫; 菊地崇普; 奥尾幸司
Oral presentation, Japanese, Technical Report of IEICE, COMP2001-30
Sep. 2001

Polynomial time identification in the limit of regular languages in some subclass
吉成智和; 富田悦次; 若月光夫
Oral presentation, Japanese, Technical Report of IEICE, COMP2001-28
Jul. 2001

A randomized and genetic hybrid algorithm for the traveling salesman problem
軍司栄一; 富田悦次; 若月光夫
Oral presentation, Japanese, Technical Report of IPSJ, 2000-MPS-33-16
Mar. 2001

巡回セールスマン問題に対する確率及び遺伝的ハイブリッドアルゴリズムとその実験的評価
軍司栄一; 富田悦次; 若月光夫; 加賀屋俊介
Oral presentation, Japanese, 1999年電子情報通信学会情報・システムソサイエティ大会講演論文集，D-1-3
Sep. 1999

正則言語のある部分クラスに対する正の例からの多項式時間極限同定
高橋宣成; 富田悦次; 若月光夫
Oral presentation, Japanese, 1999年度人工知能学会全国大会(第13回)論文集，21-01
Jun. 1999

An efficient algorithm for finding a maximum clique and its experimental evaluations
富田悦次; 平賀直仁; 若月光夫
Oral presentation, Japanese, Technical Report of IPSJ, 99-MPS-24-1
May 1999

Query learning of simple deterministic languages in polynomial time
但馬康宏; 富田悦次; 若月光夫
Oral presentation, Japanese, Technical Report of JSAI, SIG-FAI-9804-3
Mar. 1999

Polynomial time learnability of simple deterministic languages from MAT and a representative sample
Yasuhiro Tajima; Etsuji Tomita; Mitsuo Wakatsuki
Oral presentation, English, Technical Report of IEICE, COMP98-35
Sep. 1998

最大重みクリーク抽出アルゴリズムの効率化
若井康; 富田悦次; 若月光夫
Oral presentation, Japanese, 人工知能学会全国大会（第12回）論文集，16-02
Jun. 1998

正則言語のある部分族に対する正の例からの多項式時間極限同定
若月光夫; 松村佳幸; 富田悦次
Oral presentation, Japanese, 人工知能学会全国大会（第12回）論文集，08-04
Jun. 1998

単純決定性言語のある部分族に対する多項式時間MAT学習
但馬康宏; 富田悦次; 若月光夫
Oral presentation, Japanese, 人工知能学会全国大会（第12回）論文集，08-03
Jun. 1998

A unified method to extend classes of languages learnable in the limit from positive data
山田剛; 富田悦次; 若月光夫
Oral presentation, Japanese, Technical Report of JSAI, SIG-FAI-9703-7
Mar. 1998

Randomized and hybrid algorithms for approximate graph coloring
菊池淳; 富田悦次; 若月光夫
Oral presentation, Japanese, Technical Report of IEICE, COMP97-109
Mar. 1998

Polynomial time MAT learning of simple deterministic languages with structural counterexamples
但馬康宏; 富田悦次; 若月光夫
Oral presentation, Japanese, Technical Report of IEICE, COMP97-59
Oct. 1997

Prediction of RNA secondary structure including pseudoknotting based on combinational optimization
田中健夫; 若月光夫; 富田悦次
Oral presentation, Japanese, Technical Report of IPSJ, 96-MPS-10-4
Nov. 1996

A polynomial-time algorithm for checking the inclusion for real-time deterministic one-counter automata which accept by accept mode
樋口健; 若月光夫; 富田悦次
Oral presentation, Japanese, Technical Report of IEICE, COMP95-97
Mar. 1996

グラフの近似彩色を行う確率アルゴリズム
菊池淳; 飯田卓; 富田悦次; 若月光夫
Oral presentation, Japanese, 情報処理学会第52回全国大会講演論文集（分冊1），4U-7
Mar. 1996

諸受理方式による決定性カウンタの言語クラスについて
樋口健; 若月光夫; 富田悦次
Oral presentation, Japanese, 情報処理学会第52回全国大会講演論文集（分冊1），4U-2
Mar. 1996

最大重みクリークの抽出アルゴリズムのRNAの二次構造予測への適用
若月光夫; 田中健夫; 富田悦次
Oral presentation, Japanese, 情報処理学会第52回全国大会講演論文集（分冊1），3U-9
Mar. 1996

最大重みクリークの近似抽出解法によるRNAの二次構造予測
田中健夫; 若月光夫; 富田悦次
Oral presentation, Japanese, 1995年電子情報通信学会情報・システムソサイエティ大会講演論文集，D-10
Sep. 1995

A fast algorithm for checking the inclusion for very simple deterministic pushdown automata
Mitsuo Wakatsuki; Etsuji Tomita
Oral presentation, English, Technical Report of IEICE, COMP92-43
Oct. 1992

An improvement on the worst-case time complexity of an algorithm for checking equivalence of simple deterministic pushdown automata
若月光夫; 富田悦次
Oral presentation, Japanese, Technical Report of IEICE, COMP90-24
Jul. 1990

Improvements on a direct branching algorithm for checking equivalence of simple deterministic pushdown automata
若月光夫; 富田悦次
Oral presentation, Japanese, Technical Report of IEICE, COMP90-23
Jul. 1990

A direct branching algorithm for checking equivalence of simple deterministic pushdown automata
若月光夫; 富田悦次; 小倉弘敬
Oral presentation, Japanese, Technical Report of IEICE, COMP87-81
Mar. 1988

Simple DPDAの等価性判定を行う直接的分岐アルゴリズムの簡単化
若月光夫; 富田悦次; 小倉弘敬
Oral presentation, Japanese, 昭和63年電子情報通信学会春季全国大会講演論文集（分冊D-1），D-343
Mar. 1988

Jul. 1998 - Present
The Japanese Society for Artificial Intelligence

Apr. 1993 - Present
LA Symposium

Apr. 1993 - Present
Information Processing Society of Japan

Jan. 1988 - Present
The Institute of Electronics, Information and Communication Engineers

Development of efficient learning algorithms of formal languages and construction of their application systems
WAKATSUKI Mitsuo; TOMITA Etsuji; NISHINO Tetsuro
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), The University of Electro-Communications, Grant-in-Aid for Scientific Research (C), Principal investigator, We have developed a polynomial-time algorithm for checking the equivalence of deterministic restricted one-counter transducers (DROCT's for short), which are deterministic pushdown transducers having just one stack symbol, that accept by final state with possible epsilon-moves. By extending this technique, we have also developed a polynomial-time algorithm for checking the inclusion of these DROCT's. Then, we have presented a polynomial-time algorithm for learning real-time DROCT's which accept by final state via membership and equivalence queries. Furthermore, we have shown that the regularity of the behavior of some programs for playing games of Daihinmin, which is one of card games, on computers can be extracted by using the EUREKA system which incorporated an identification algorithm of the class of k-reversible languages, which is a subclass of regular languages, for analyzing songs of the Bengalese finch., 23500011
Apr. 2011 - Mar. 2015

Developments of efficient algorithms for learning from examples of formal languages and their applications
WAKATSUKI Mitsuo; TOMITA Etsuji; NISHINO Tetsuro
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), The University of Electro-Communications, Grant-in-Aid for Scientific Research (C), Principal investigator, We have developed polynomial time algorithms for checking the equivalence of deterministic restricted one-counter transducers, which are deterministic pushdown transducers having just one stack symbol, that accept by empty stack or by final state. We have proved that a subclass of deterministic pushdown automata called Szilard strict deterministic restricted one-counter automata and a subclass of finite state transducers(FST's for short)called strict prefix deterministic FST's are polynomial time identifiable in the limit from positive data. Furthermore, we have improved the method for analyzing songs of the Bengalese finch using an identification algorithm for the class of k-reversible languages, which is a subclass of regular languages., 20500007
Apr. 2008 - Mar. 2011

Developments of LearningAlgorithms for Deterministic Context-Free Languages in Some Classes and Their Applications
WAKATSUKI Mitsuo; TOMITA Etsuji
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), The University of Electro-Communications, Grant-in-Aid for Scientific Research (C), Principal investigator, The machine learning is one of the most important research fields for the realization of the artificial intelligence, and the computational learning theory is a paradigm which analyzes mathematically about the possibility for the machine learning. In formal language theory, the class of deterministic context-free languages is important in practical use. In this research, we are concerned with some subclasses of deterministic pushdown automata (dpda's for short) which accept deterministic context-free languages and the corresponding subclasses of formal grammars. The aim of this research is to develop learning algorithms for subclasses of dpda's and to apply these algorithms to practical problems. We had the following research results. 1. Basics to develop learning algorithms: We have proposed a simple and direct algorithm for checking the equivalence of a certain pair of non-real-time deterministic pushdown transducers (dpdt's for short), where dpdt's are obtained by attaching the output function to dpda's. In addition, we have given a polynomial-time algorithm for checking the equivalence of real-time strict deterministic restricted one-counter transducers, which are real-time dpdt's that have just one stack symbol. We know that the equivalence checking algorithm plays an important role in learning systems which are formulated as automata and formal grammars. These results can be used for learning via queries for some subclasses of dpdt's. 2. Developments of learning algorithms: We have presented a unified identification algorithm in the limit from positive data for the extended class defined by a class of languages to be based on and a class of finite subsets of strings. Furthermore, we have proved that a subclass of dpda's called Szilard strict deterministic restricted one-counter automata and a certain subclass of finite state transducers are polynomial time identifiable in the limit from positive data., 18500108
Apr. 2006 - Mar. 2008

A neural model of the binding in the human brain and its application to pattern recognition
HARUHISA Takahashi; MITSUO Wakatsuki; TETSURO Nishino; ETSUJI Tomita
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The Unicersity of Electro-Communications, Grant-in-Aid for Scientific Research (C), The information binding in human brain is getting important to explain and to understand how human being can recognize the outer world so easily. Besides this, we expect that applying the binding mechanism to recognizer, we can get much better recognition performance. In this research we developed the neural networks that can well explain the information binding in the human brain. Based on the fact that the previous neural models are difficult to represent the spike synchronization or asynchronization, we developed two phasor neural models. One is the phase-rate oscillating neural model, in which the phase represents the sinusoidal phase. The other is covariance neural model, in which the cosine of the phase difference between two neurons represents the covariance coefficient. In both model we implemented the Hebb learning and Boltzmann learning rules to get the efficient learning. From the computer simulation results, we showed that the proposed learning rules work much more efficient than ordinal models. Applying the knowledge obtained from these models, we proposed the brain wave recognizer which shows much higher performance than previous. We also developed the theory of generalization in learning., 10650353
1998 - 2000

（英語タイトルなし）
WAKATSUKI Mitsuo
日本学術振興会, 科学研究費助成事業 奨励研究(A), 電気通信大学, 奨励研究(A), Principal investigator, 本研究では,決定性文脈自由言語を受理する決定性プッシュダウンオートマン(DPDA)の構造にある妥当な制約を課した部分族を対象として,計算論的学習理論のパラダイムに基づく帰納推論アルゴリズムを開発することを目的としている。その基礎構築のため,対象の言語族を特徴づける諸性質を明らかにし,その族に対する決定問題を解く効率的な判定アルゴリズムを開発することも研究対象である。 まず,DPDAのスタック記号をただ1種類に限定した決定性カウンタ(DROCA)と呼ぶ部分族を対象とし,次の結果を得た。DROCAの受理方式の違いによる言語族間の関係および各言語族の閉包性を明らかにした。続いて,空スタック受理式および実時間最終状態受理式DROCAに対する多項式時間包含性判定アルゴリズムをそれぞれ提案した(前者は1995年電子情報通信学会英文論文誌E-D分冊掲載予定。後者は同論文誌投稿中)。この結果を利用することで,これらDROCAに対する正則性判定が多項式時間で可能であることも明らかにした。これらは,DROCAの上位の族で,DPDAのスタックを底の1記号を除いてただ1種類に限定した決定性1カウンタオートマンに対して,包含性判定が非可解であること,指数オーダの時間量の正則性判定アルゴリズムが提案されているだけであることに比べ対照的な結果である。 更に,学習アルゴリズムについては次の結果を得た。実時間空スタック受理式DROCAに各入力記号に対し推移規則を高々1つに限定する等の制約を課した部分族に対する正の例からの極限同定アルゴリズムを開発した。これは,入力記号数を定数とみなせば多項式時間で同定可能である。また,接尾辞決定性正則言語と名付けた正則言語の真部分族に対する正の例からの多項式時間極限同定アルゴリズムを開発した。, 06780243
Apr. 1994 - Mar. 1995

科学研究費委員会奨励研究部会理工系小委員会審査委員
Review, Review, 日本学術振興会, Dec. 2016 - Mar. 2017