博士(工学), 電気通信大学, 1993年03月

計算機科学

知能情報学

計算理論

ゲーム情報学

組合せ最適化

計算論的学習理論

オートマトン・形式言語理論

情報通信, 知能情報学

情報通信, 情報学基礎論

2016年04月01日
電気通信大学大学院情報理工学研究科、情報理工学域, 助教

2010年04月01日 - 2016年03月31日
電気通信大学大学院情報理工学研究科、情報理工学部, 助教

2007年04月01日 - 2010年03月31日
電気通信大学電気通信学部, 助教

1993年04月01日 - 2007年03月31日
電気通信大学電気通信学部, 助手

1988年04月 - 1993年03月
電気通信大学大学院, 電気通信学研究科, 電子情報学専攻

1984年04月09日 - 1988年03月23日
電気通信大学, 電気通信学部, 通信工学科

1981年04月 - 1984年03月09日
東京都立国立高等学校, 普通科, 日本国

2022年12月 - 2023年03月
第85回全国大会現地実行委員, 情報処理学会, 学協会

2017年04月 - 2021年03月
数理モデル化と問題解決研究会運営委員, 情報処理学会, 学協会

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

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

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

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

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

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, 出版日 2021年10月12日, 査読付
研究論文（国際会議プロシーディングス）, 英語

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, 出版日 2021年09月30日, 査読付
研究論文（学術雑誌）, 英語

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, 出版日 2020年05月31日, 査読付
研究論文（学術雑誌）, 英語

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, 出版日 2019年07月, 査読付
研究論文（国際会議プロシーディングス）, 英語

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, 出版日 2019年07月, 査読付
研究論文（国際会議プロシーディングス）, 英語

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, 出版日 2019年01月, 査読付
研究論文（学術雑誌）, 英語

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, 出版日 2018年10月, 査読付
研究論文（国際会議プロシーディングス）, 英語

Decision tree analysis in game informatics
Masato Konishi; Seiya Okubo; Tetsuro Nishino; Mitsuo Wakatsuki
Studies in Computational Intelligence, Springer Verlag, 727巻, 掲載ページ 13-27, 出版日 2018年07月, 査読付, 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.
研究論文（学術雑誌）, 英語

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, 出版日 2018年07月, 査読付, 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.
研究論文（学術雑誌）, 英語

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, 出版日 2017年10月, 査読付
研究論文（国際会議プロシーディングス）, 英語

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, 出版日 2017年08月01日, 査読付, 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.
研究論文（学術雑誌）, 英語

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, 出版日 2017年07月, 査読付
研究論文（国際会議プロシーディングス）, 英語

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, 出版日 2016年06月, 査読付, 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.
研究論文（国際会議プロシーディングス）, 英語

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, 出版日 2016年04月, 査読付
研究論文（学術雑誌）, 英語

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, 出版日 2015年07月, 査読付, 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.
研究論文（国際会議プロシーディングス）, 英語

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, 出版日 2015年07月, 査読付
研究論文（学術雑誌）, 英語

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, 出版日 2015年03月, 査読付
研究論文（国際会議プロシーディングス）, 英語

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年, 査読付, 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.
研究論文（国際会議プロシーディングス）, 英語

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, 出版日 2014年06月, 査読付, 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.
研究論文（国際会議プロシーディングス）, 英語

最大クリーク問題の多項式時間的可解性の拡張の改良
中西裕陽; 富田悦次; 若月光夫; 西野哲朗
電子情報通信学会論文誌D分冊, 電子情報通信学会, J97-D巻, 6号, 掲載ページ 1106-1121, 出版日 2014年06月, 査読付
研究論文（学術雑誌）, 日本語

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, 出版日 2013年12月, 査読付
研究論文（学術雑誌）, 英語

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, 出版日 2013年07月, 査読付, 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.
研究論文（国際会議プロシーディングス）, 英語

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, 出版日 2013年06月, 査読付, 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.
研究論文（学術雑誌）, 英語

最大クリーク問題の多項式時間的可解性の拡張
中西裕陽; 富田悦次; 若月光夫; 西野哲朗
電子情報通信学会論文誌D分冊, 一般社団法人電子情報通信学会, J95-D巻, 9号, 掲載ページ 1716-1728, 出版日 2012年09月, 査読付, 典型的なNP完全問題である最大クリーク問題に対し,本論文では,次の結果を示す:"節点数nの一般グラフにおいて,Gの最大次数△が△≤2.994dlgn(d≥0:定数)なる条件を満たすとき,このグラフの最大クリーク問題はO(n^<1+d>)なる多項式時間で可解である."これに先立ち,最大次数△が△≤2.773dlgn(d≥0:定数)である場合に同様の結果を得ている(信学論(D),vol.J94-D,no.12,pp.2037-2046)が,本論文では,前結果における状況をより詳細に解析した上で,最大時間計算量が大きくなる場合に対して,更に詳細な場合分けを伴ったアルゴリズムと時間計算量解析を導入することにより,本結果を得ている.
研究論文（学術雑誌）, 日本語

最大クリーク問題の多項式時間的可解性の更なる改良結果
中西裕陽; 富田悦次; 若月光夫; 西野哲朗
電子情報通信学会論文誌D分冊, 一般社団法人電子情報通信学会, J94-D巻, 12号, 掲載ページ 2037-2046, 出版日 2011年12月, 査読付, 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)に近づく.これは,前発表ではグラフを隣接行列で表現することを前提としていたのに対して,本論文では隣接リスト表現を用いることにより実現している.
研究論文（学術雑誌）, 日本語

量子セルオートマトンに基づく画像圧縮のための画像変換アルゴリズム
大畑和樹; 西野哲朗; 若月光夫
京都大学数理解析研究所講究録, 1744巻, 掲載ページ 181-184, 出版日 2011年06月
研究論文（大学，研究機関等紀要）, 日本語

最大クリーク問題の多項式時間的可解性について
中西裕陽; 富田悦次; 若月光夫; 西野哲朗
京都大学数理解析研究所講究録, 1744巻, 掲載ページ 169-176, 出版日 2011年06月
研究論文（大学，研究機関等紀要）, 日本語

実時間最終状態受理式決定性限定1カウンタ変換器の多項式時間等価性判定アルゴリズム
若月光夫; 清野和司; 富田悦次; 西野哲朗
京都大学数理解析研究所講究録, 京都大学, 1744巻, 掲載ページ 1-10, 出版日 2011年06月
研究論文（大学，研究機関等紀要）, 日本語

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, 出版日 2010年09月, 査読付, 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.
研究論文（国際会議プロシーディングス）, 英語

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, 出版日 2010年02月, 査読付, 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.
研究論文（国際会議プロシーディングス）, 英語

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, 出版日 2008年06月, 査読付, 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.
研究論文（学術雑誌）, 英語

実時間空スタック受理式決定性限定ワンカウンター変換器の多項式時間等価性判定
清野和司; 富田悦次; 若月光夫
電子情報通信学会論文誌D分冊, 一般社団法人電子情報通信学会, J91-D巻, 5号, 掲載ページ 1188-1201, 出版日 2008年05月, 査読付, 決定性プッシュダウンオートマトン(dpda)の等価性判定問題は,任意のクラスに対する可解性が示されている.しかし,そのアルゴリズムの効率化については,必ずしも十分な解は得られていない.オートマトンや形式文法を基礎とするシステムにおける学習などにおいて,等価性判定は主要な役割を果たし,その効率向上を実現する上で,多項式時間の等価性判定可解性は非常に重要である.本論文では,スタック記号が単一という制限をもつ実時間空スタック受理式決定性限定ワンカウンタオートマトンに出力機構を付与した,実時間空スタック受理式決定性限定ワンカウンタ変換器について,筆者らが提唱してきた,分岐アルゴリズムと名づけた単純で直接的な等価性判定手法を用いることにより,その等価性判定が多項式時間で解決できることを示す.
研究論文（学術雑誌）, 日本語

ε-推移を許したある決定性プッシュダウン変換器対の等価性判定
清野和司; 富田悦次; 若月光夫
電子情報通信学会論文誌D分冊, 一般社団法人電子情報通信学会, J90-D巻, 10号, 掲載ページ 2675-2690, 出版日 2007年10月, 査読付, 決定性プッシュダウンオートマトン(dpda)の等価性判定問題は,任意のクラスに対して可解であるとの結論が明らかにされたが,その可解性の証明は非常に複雑である.これに対し,筆者らは,dpdaの部分クラスを対象とする,分岐アルゴリズムと名づけた単純で直接的な等価性判定手法を提唱してきた.そして,一方が実時間空スタック受理式である決定性プッシュダウン変換器(dpdt)に対しても,この等価性判定方式が,ほぼ直接的に適応可能であることを既に証明している.本論文では,dpdtに対するその結果を更に拡張し,かつ,その直接的単純性を保ちながら,両者にε-推移を許したある種のdpdt対に対しても等価性判定を可能とする拡張アルゴリズムを提唱する.
研究論文（学術雑誌）, 日本語

Polynomial time identification of finite state transducers in some class
Mitsuo Wakatsuki; Etsuji Tomita
Proc. Advanced ICT 2007 (AICT2007), 掲載ページ 1-6, 出版日 2007年09月
研究論文（国際会議プロシーディングス）, 英語

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, 出版日 2006年09月, 査読付, 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.
研究論文（学術雑誌）, 英語

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, 出版日 2004年12月, 査読付
研究論文（学術雑誌）, 英語

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, 出版日 2004年10月, 査読付, 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.
研究論文（学術雑誌）, 英語

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, 出版日 2000年04月, 査読付, 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.
研究論文（学術雑誌）, 英語

構造反例付き等価性質問を用いた単純決定性言語の多項式時間MAT学習
但馬康宏; 富田悦次; 若月光夫
電子情報通信学会論文誌D-I分冊, 一般社団法人電子情報通信学会, J82-D-I巻, 4号, 掲載ページ 521-532, 出版日 1999年04月, 査読付, 本論文において, 単純決定性言語の多項式時間厳密学習を可能にする一手法を示す. 一般に等価性質問は, 仮説文法の入力に対して, その生成言語が学習対象の言語と等価か否かを出力し, 非等価の場合には更にその根拠となる反例も出力する. ここで反例が正の反例の場合, 更に学習対象における導出構造も出力する質問を構造反例付き等価性質問と新たに定義する. このとき任意の単純決定性言語は, 所属性質問及び構造反例付き等価性質問を用いて, 単純決定性文法の族により多項式時間厳密学習可能であることを示す. この学習アルゴリズムにおける仮説文法の構成方法は, Ishizaka(1990)における考え方に基づき, 質問を行うアルゴリズムはAngluin(1987)における考え方に基づいている.
研究論文（学術雑誌）, 日本語

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, 出版日 1998年01月, 査読付, 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.
研究論文（学術雑誌）, 英語

整数重みグラフの最大重みクリーク抽出アルゴリズム
鄭戴勇; 富田悦次; 若月光夫
電気通信大学紀要, 電気通信大学, 10巻, 1号, 掲載ページ 1-4, 出版日 1997年06月
研究論文（大学，研究機関等紀要）, 日本語

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, 出版日 1997年05月, 査読付, 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.
研究論文（学術雑誌）, 英語

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, 出版日 1996年07月, 査読付, 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.
研究論文（学術雑誌）, 英語

最大クリークを抽出する単純で効率的な分枝限定アルゴリズムと実験的評価
富田悦次; 今松憲一; 木幡康弘; 若月光夫
電子情報通信学会論文誌D-I分冊, J79-D-I巻, 1号, 掲載ページ 1-8, 出版日 1996年01月, 査読付
研究論文（学術雑誌）, 日本語

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, 出版日 1995年08月, 査読付, 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.
研究論文（学術雑誌）, 英語

近似彩色を用いた単純な最大重みクリーク抽出アルゴリズム
今松憲一; 富田悦次; 若月光夫
電気通信大学紀要, 電気通信大学, 8巻, 1号, 掲載ページ 17-21, 出版日 1995年06月
研究論文（大学，研究機関等紀要）, 日本語

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, 出版日 1995年04月, 査読付, 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.
研究論文（学術雑誌）, 英語

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, 出版日 1993年10月, 査読付, 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.
研究論文（学術雑誌）, 英語

単純決定性プッシュダウンオートマトンの等価性を決定する最短入力記号列長の上界
若月光夫; 富田悦次
電子情報通信学会論文誌D-I分冊, 電子情報通信学会, J75-D-I巻, 10号, 掲載ページ 950-953, 出版日 1992年10月, 査読付
研究論文（学術雑誌）, 日本語

単純決定性プッシュダウンオートマトンの等価性判定の改良分岐アルゴリズムとその最大時間計算量
若月光夫; 富田悦次
電子情報通信学会論文誌D-I分冊, 電子情報通信学会, J74-D-I巻, 9号, 掲載ページ 595-603, 出版日 1991年09月, 査読付
研究論文（学術雑誌）, 日本語

単純決定性プッシュダウンオートマトンの等価性判定を行う直接的分岐アルゴリズム
若月光夫; 富田悦次; 藤橋忠悟
電子情報通信学会論文誌D-I分冊, 電子情報通信学会, J72-D-I巻, 5号, 掲載ページ 327-334, 出版日 1989年05月, 査読付
研究論文（学術雑誌）, 日本語

情報工学のための離散数学入門
西野哲朗; 若月光夫
学術書, 日本語, 共著, 第１章「集合」，第２章「関係と関数」，第３章「論理と証明法」，およびそれらの演習問題解答, 数理工学社, 出版日 2015年08月25日, ISBN 9784864810326

応用オートマトン工学
西野哲朗; 若月光夫; 後藤隆彰
日本語, 共著, 第１章 オートマトン理論, コロナ社, 出版日 2012年02月

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

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

コンピュータUNOにおけるモンテカルロ木探索について
山﨑優; 大久保誠也; 若月光夫; 西野哲朗
口頭発表（一般）, 日本語, 情報処理学会第51回ゲーム情報学研究会, 情報処理学会ゲーム情報学研究会, 国立情報学研究所12Ｆ会議室, 日本国, 国内会議
発表日 2024年03月09日
開催期間 2024年03月08日- 2024年03月09日

コンピュータUNOにおけるモンテカルロ法のREINFORCEアルゴリズムによる方策学習
新木優典; 大久保誠也; 若月光夫; 西野哲朗
口頭発表（一般）, 日本語, 情報処理学会第51回ゲーム情報学研究会, 情報処理学会ゲーム情報学研究会, 国立情報学研究所12Ｆ会議室, 日本国, 国内会議
発表日 2024年03月09日
開催期間 2024年03月08日- 2024年03月09日

コンピュータUNOにおける発見的に得た戦略に関する研究
齋藤康平; 大久保誠也; 若月光夫; 西野哲朗
口頭発表（一般）, 日本語, 情報処理学会第85回全国大会
発表日 2023年03月04日
開催期間 2023年03月02日- 2023年03月04日

コンピュータUNOにおけるモンテカルロ法プレイヤの構築
稲葉颯弥; 大久保誠也; 若月光夫; 西野哲朗
口頭発表（一般）, 日本語, 情報処理学会第85回全国大会
発表日 2023年03月04日
開催期間 2023年03月02日- 2023年03月04日

D-Waveの量子アニーリングマシン上における最大クリーク探索の実験的評価
白石千尋; 大久保誠也; 若月光夫; 西野哲朗
口頭発表（一般）, 日本語, 情報処理学会第85回全国大会
発表日 2023年03月04日
開催期間 2023年03月02日- 2023年03月04日

大学図書館における対話型図書推薦システムに関する研究
田代大成; 大久保誠也; 若月光夫; 西野哲朗
口頭発表（一般）, 日本語, 情報処理学会第85回全国大会
発表日 2023年03月03日
開催期間 2023年03月02日- 2023年03月04日

Watson Assistantを用いたサイトレビューによる参考書の難易度推定手法
Muhammad Fauzan Mahfuzh; 大久保誠也; 若月光夫; 西野哲朗
口頭発表（一般）, 日本語, 情報処理学会第85回全国大会
発表日 2023年03月03日
開催期間 2023年03月02日- 2023年03月04日

小説の内容を表すキーワードの抽出に関する研究
若井龍弥; 大久保誠也; 若月光夫; 西野哲朗
口頭発表（一般）, 日本語, 情報処理学会第85回全国大会
発表日 2023年03月03日
開催期間 2023年03月02日- 2023年03月04日

セクション情報を用いた日本語長文文書の抽象型自動要約
沢畑英之; 大久保誠也; 若月光夫; 西野哲朗
口頭発表（一般）, 日本語, 情報処理学会第85回全国大会
発表日 2023年03月02日
開催期間 2023年03月02日- 2023年03月04日

最大クリーク抽出アルゴリズムMCTのさらなる高速化
柳澤士朗; 富田悦次; 片山謙吾; 金原一歩; 戸田貴久; 伊藤大雄; 若月光夫; 西野哲朗
口頭発表（一般）, 日本語, 電子情報通信学会コンピュテーション研究会技術研究報告，COMP2020-35, 国内会議
発表日 2021年03月08日

コンピュータ大貧民における戦略の定式化に関する研究
川崎伊織; 大久保誠也; 若月光夫; 西野哲朗
口頭発表（一般）, 日本語, 情報処理学会ゲーム情報学研究会研究報告，2021-GI-45, 国内会議
発表日 2021年03月05日

コンピュータ大貧民におけるレーティング手法の最適化に関する研究
藤村光希; 大久保誠也; 若月光夫; 西野哲朗
口頭発表（一般）, 日本語, 情報処理学会ゲーム情報学研究会研究報告，2021-GI-45, 国内会議
発表日 2021年03月05日

コンピュータ大貧民におけるレーティング手法について
五ヶ谷純平; 大久保誠也; 若月光夫; 西野哲朗
口頭発表（一般）, 日本語, 情報処理学会ゲーム情報学研究会研究報告，2020-GI-43, 国内会議
発表日 2020年03月13日

コンピュータ大貧民における提出手の影響に関する研究
三石亮; 大久保誠也; 若月光夫; 西野哲朗
口頭発表（一般）, 日本語, 情報処理学会ゲーム情報学研究会研究報告，2018-GI-41, 国内会議
発表日 2019年03月09日

大貧民におけるモンテカルロ法の報酬値に関する研究
土橋康希; 大久保誠也; 若月光夫; 西野哲朗
口頭発表（一般）, 日本語, 情報処理学会ゲーム情報学研究会研究報告，2018-GI-41, 国内会議
発表日 2019年03月09日

コンピュータ大貧民におけるローカルルールの効果に関する研究
門裕太; 大久保誠也; 若月光夫; 西野哲朗
口頭発表（一般）, 日本語, 情報処理学会ゲーム情報学研究会研究報告，2018-GI-41, 国内会議
発表日 2019年03月08日

大貧民におけるプレイヤーの提出手の傾向に関する研究
武内大和; 大久保誠也; 若月光夫; 西野哲朗
口頭発表（一般）, 日本語, 情報処理学会ゲーム情報学研究会研究報告，2018-GI-41, 国内会議
発表日 2019年03月08日

最大クリーク抽出アルゴリズムMCTの高速化(2)
松崎空良; 富田悦次; 長尾篤樹; 伊藤大雄; 若月光夫; 西野哲朗; 片山謙吾; 金原一歩
口頭発表（一般）, 日本語, 2018年度冬のLAシンポジウム資料，No.1，LAシンポジウム, 国内会議
発表日 2019年02月04日

近似最大クリーク抽出アルゴリズムIKLSの反復回数に対する適切な制御方法
長尾篤樹; 松崎空良; 富田悦次; 伊藤大雄; 若月光夫; 西野哲朗
口頭発表（一般）, 日本語, 電子情報通信学会コンピュテーション研究会技術研究報告，COMP2018-23, 国内会議
発表日 2018年10月26日

最大クリーク抽出アルゴリズムMCTの高速化
松崎空良; 富田悦次; 長尾篤樹; 伊藤大雄; 若月光夫; 西野哲朗
口頭発表（一般）, 日本語, 情報処理学会数理モデル化と問題解決研究会研究報告，2018-MPS-120, 国内会議
発表日 2018年09月26日

決定木を用いた大貧民プログラムの分析に関する研究
小西正人; 大久保誠也; 若月光夫; 西野哲朗
口頭発表（一般）, 日本語, 情報処理学会ゲーム情報学研究会研究報告，2016-GI-36, 国内会議
発表日 2016年08月05日

最大クリーク抽出アルゴリズムMCSの高速化
吉田幸平; 八田拓郎; 富田悦次; 長尾篤樹; 伊藤大雄; 若月光夫
口頭発表（一般）, 日本語, 情報処理学会アルゴリズム研究会研究報告，2016-AL-157, 国内会議
発表日 2016年03月06日

最終状態受理式決定性限定１カウンタ変換器の多項式時間包含性判定アルゴリズム
若月光夫; 富田悦次; 西野哲朗
口頭発表（一般）, 日本語, 2015年度冬のLAシンポジウム資料，No.14，LAシンポジウム, 国内会議
発表日 2016年01月28日

最大クリーク抽出アルゴリズムの高速化
八田拓郎; 富田悦次; 伊藤大雄; 若月光夫
口頭発表（一般）, 日本語, 2015年度夏のLAシンポジウム資料，No.9，LAシンポジウム, 国内会議
発表日 2015年07月16日

最大クリーク問題の多項式時間的可解性の拡張の更なる改良
中西裕陽; 富田悦次; 若月光夫; 西野哲朗
口頭発表（一般）, 日本語, 電子情報通信学会コンピュテーション研究会技術研究報告，COMP2014-13,コンピュテーション研究会
発表日 2014年06月14日

実時間決定性限定1カウンタ変換器に対する質問による多項式時間学習アルゴリズム
若月光夫; 富田悦次; 西野哲朗
口頭発表（一般）, 日本語, 2013年度冬のLAシンポジウム資料，No.21, LAシンポジウム
発表日 2014年01月30日

類似パターンの省略によりソースコードの可読性を向上させる新技法
菊池紘; 後藤隆彰; 若月光夫; 西野哲朗
口頭発表（一般）, 日本語, 電子情報通信学会知能ソフトウェア工学研究会技術研究報告，KBSE2013-36,電子情報通信学会知能ソフトウェア工学研究会, 電気通信大学 東3号館301号室
発表日 2013年09月12日

学習ゲームを用いた発達障害児向け文字学習支援システム
金山貴泰; 浅野久美子; 西野哲朗; 若月光夫
口頭発表（一般）, 日本語, 情報処理学会数理モデル化と問題解決研究会研究報告, 情報処理学会数理モデル化と問題解決研究会, 北海道大学 百年記念会館, 国内会議
発表日 2013年05月23日

決定性限定1カウンタ変換器のある部分クラスに対する質問による多項式時間学習アルゴリズム
若月光夫; 富田悦次; 西野哲朗
口頭発表（一般）, 日本語, 2012年度冬のLAシンポジウム資料，No.13,LAシンポジウム
発表日 2013年01月

最大クリーク問題の多項式時間的可解性の拡張の改良
中西裕陽; 富田悦次; 若月光夫; 西野哲朗
口頭発表（一般）, 日本語, 電子情報通信学会コンピュテーション研究会技術研究報告，COMP2012-28,コンピュテーション研究会
発表日 2012年09月

遺伝的アルゴリズムを用いたコンピュータ大貧民の思考ルーチンの自動チューニング
海川祥毅; 西野哲朗; 若月光夫
シンポジウム・ワークショップパネル（公募）, 日本語, 第6回エンターテイメントと認知科学シンポジウム, 電気通信大学エンターテイメントと認知科学研究ステーション, 調布
発表日 2012年03月

最終状態受理式決定性限定1カウンタ変換器の多項式時間等価性判定アルゴリズム
若月光夫; 清野和司; 富田悦次; 西野哲朗
口頭発表（一般）, 日本語, 2011年度冬のLAシンポジウム資料，No.11,LAシンポジウム
発表日 2012年01月

最大クリーク問題の多項式時間的可解性の拡張
中西裕陽; 富田悦次; 若月光夫; 西野哲朗
口頭発表（一般）, 日本語, 電子情報通信学会コンピュテーション研究会技術研究報告，COMP2011-30,コンピュテーション研究会
発表日 2011年10月

最大クリーク問題の多項式時間的可解性の更なる改良結果
中西裕陽; 富田悦次; 若月光夫; 西野哲朗
口頭発表（一般）, 日本語, 電子情報通信学会コンピュテーション研究会技術研究報告，COMP2011-6,コンピュテーション研究会
発表日 2011年04月

量子セルオートマトンに基づく画像圧縮のための画像変換アルゴリズム
大畑和樹; 西野哲朗; 若月光夫
口頭発表（一般）, 日本語, 2010年度冬のLAシンポジウム，No.S2,LAシンポジウム
発表日 2011年02月

最大クリーク問題の多項式時間的可解性について
中西裕陽; 富田悦次; 若月光夫; 西野哲朗
口頭発表（一般）, 日本語, 2010年度冬のLAシンポジウム資料，No.32,LAシンポジウム
発表日 2011年02月

実時間最終状態受理式決定性限定1カウンタ変換器の多項式時間等価性判定アルゴリズム
若月光夫; 清野和司; 富田悦次; 西野哲朗
口頭発表（一般）, 日本語, 2010年度冬のLAシンポジウム資料，No.1,LAシンポジウム
発表日 2011年02月

鳥の歌文法解析の自動化
鈴木徹; 若月光夫; 西野哲朗
口頭発表（一般）, 日本語, 2010年度夏のLAシンポジウム資料，No.S6,LAシンポジウム
発表日 2010年07月

最大クリーク抽出の単純な最大時間計算量評価と多項式時間的可解性
中西裕陽; 富田悦次; 若月光夫
口頭発表（一般）, 日本語, 2009年度冬のLAシンポジウム資料，No.29,LAシンポジウム
発表日 2010年02月

空スタック受理式決定性限定ワンカウンタ変換器の多項式時間等価性判定アルゴリズム
若月光夫; 清野和司; 富田悦次; 西野哲朗
口頭発表（一般）, 日本語, 2009年度冬のLAシンポジウム資料，No.14,LAシンポジウム
発表日 2010年02月

単純でより高速な最大クリーク抽出アルゴリズム
富田悦次; 須谷洋一; 東貴紀; 高橋真也; 若月光夫
口頭発表（一般）, 英語, 情報処理学会アルゴリズム研究会研究報告，2010-AL-128-10
発表日 2010年01月

鳥の歌構造解析におけるk可逆オートマトンとNグラムモデルの関係について
常田宏和; 若月光夫; 西野哲朗
口頭発表（一般）, 日本語, 2009年度夏のLAシンポジウム資料，No.16,LAシンポジウム
発表日 2009年07月

大貧民プログラムの学習問題について
大久保誠也; 若月光夫; 西野哲朗
シンポジウム・ワークショップパネル（公募）, 日本語, 第3回エンターテイメントと認知科学シンポジウム, 電気通信大学エンターテイメントと認知科学研究ステーション, 東京都調布市
発表日 2009年03月

第3回UECコンピュータ大貧民大会(UECda-2008)の報告
大久保誠也; 本多武尊; 眞鍋秀聡; 飯塚拓郎; Khan Md; Mahfuzus Salam; 常田宏和; 儀間武晃; 鈴木智也; 田中愛美; 松野香菜子; 若月光夫; 西野哲朗
口頭発表（一般）, 日本語, 情報処理学会ゲーム情報学研究会研究報告，2009-GI-21-3,第21回ゲーム情報学研究会
発表日 2009年03月

準同型写像によって拡張されたある言語クラスに対する正例からの極限同定
若月光夫; 富田悦次
口頭発表（一般）, 日本語, 情報処理学会数理モデル化と問題解決研究会研究報告，2009-MPS-73-20,第73回数理モデル化と問題解決研究会
発表日 2009年03月

オートマトンの学習困難性を安全性の基盤とする暗号システムについて
大久保誠也; 西野哲朗; 若月光夫
口頭発表（一般）, 日本語, 2008年度冬のLAシンポジウム資料，No.25,LAシンポジウム
発表日 2009年02月

最大クリーク抽出アルゴリズムの共有メモリ型並列計算機上での並列化
若月光夫; 高橋真也; 富田悦次
口頭発表（一般）, 日本語, 情報処理学会数理モデル化と問題解決研究会研究報告，2008-MPS-71-5,第71回数理モデル化と問題解決研究会
発表日 2008年09月

ある種の有限状態変換器に対する多項式時間極限同定
若月光夫; 富田悦次
口頭発表（一般）, 英語, 情報処理学会,アルゴリズム研究会研究報告，2007-AL-115
発表日 2007年11月

実時間空スタック受理式決定性限定ワンカウンター変換器の多項式時間等価性判定アルゴリズム
清野和司; 富田悦次; 若月光夫
口頭発表（一般）, 日本語, 電子情報通信学会コンピュテーション研究会技術研究報告，COMP2007-47,コンピュテーション研究会
発表日 2007年10月

A unified algorithm for extending classes of languages identifiable in the limit from positive data
Mitsuo Wakatsuki; Etsuji Tomita; Go Yamada
口頭発表（一般）, 英語, 2006年度夏のLAシンポジウム資料, No.18,2006年度夏のLAシンポジウム(東広島)
発表日 2006年08月

ε-推移を許したある決定性プッシュダウン変換器対の等価性判定アルゴリズム
清野和司; 富田悦次; 若月光夫
口頭発表（一般）, 日本語, 情報処理学会アルゴリズム研究会研究報告，2006-AL-104-9,第104回アルゴリズム研究会
発表日 2006年01月

正の例から極限同定可能な言語クラスを拡張する統一的アルゴリズム
若月光夫; 富田悦次; 山田 剛
口頭発表（一般）, 英語, 情報処理学会アルゴリズム研究会研究報告, 2005-AL-102,アルゴリズム研究会
発表日 2005年09月

空スタック受理式決定性1カウンタオートマトンのある部分クラスに対する正の例からの多項式時間極限同定
Mitsuo Wakatsuki; Kiyoshi Teraguchi; Etsuji Tomita
口頭発表（一般）, 英語, 電子情報通信学会コンピュテーション研究会技術研究報告，COMP2003-83
発表日 2004年03月

正則言語の幾つかの部分クラスに対する正の例からの極限同定の統一的一方式
若月光夫; 山田 剛; 富田悦次
口頭発表（一般）, 日本語, 2002年度夏のLAシンポジウム資料，No.22
発表日 2002年07月

正則言語の部分クラスに対する正の例からの多項式時間極限同定
吉成智和; 富田悦次; 若月光夫
口頭発表（一般）, 日本語, 電子情報通信学会コンピュテーション研究会技術研究報告，COMP2001-83
発表日 2002年03月

ある種の一般化順序機械の多項式時間推論アルゴリズム
西田大; 富田悦次; 若月光夫
口頭発表（一般）, 日本語, 2001年度冬のLAシンポジウム資料，No.45
発表日 2002年02月

ある種のカウンタに対する正の例からの多項式時間極限同定
寺口 潔; 富田悦次; 若月光夫; 菊地崇普; 奥尾幸司
口頭発表（一般）, 日本語, 電子情報通信学会コンピュテーション研究会技術研究報告，COMP2001-30
発表日 2001年09月

正則言語のある部分クラスに対する正の例からの多項式時間極限同定
吉成智和; 富田悦次; 若月光夫
口頭発表（一般）, 日本語, 電子情報通信学会コンピュテーション研究会技術研究報告，COMP2001-28
発表日 2001年07月

巡回セールスマン問題に対する確率・遺伝的ハイブリッドアルゴリズム
軍司栄一; 富田悦次; 若月光夫
口頭発表（一般）, 日本語, 情報処理学会数理モデル化と問題解決研究会研究報告，2000-MPS-33-16
発表日 2001年03月

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

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

最大クリーク抽出アルゴリズムの効率化とその評価
富田悦次; 平賀直仁; 若月光夫
口頭発表（一般）, 日本語, 情報処理学会数理モデル化と問題解決研究会研究報告，99-MPS-24-1
発表日 1999年05月

単純決定性言語の質問による多項式時間学習について
但馬康宏; 富田悦次; 若月光夫
口頭発表（一般）, 日本語, 人工知能学会人工知能基礎論研究会資料，SIG-FAI-9804-3
発表日 1999年03月

質問および代表的な記号列集合を用いた単純決定性言語の多項式時間学習
Yasuhiro Tajima; Etsuji Tomita; Mitsuo Wakatsuki
口頭発表（一般）, 英語, 電子情報通信学会コンピュテーション研究会技術研究報告，COMP98-35
発表日 1998年09月

最大重みクリーク抽出アルゴリズムの効率化
若井康; 富田悦次; 若月光夫
口頭発表（一般）, 日本語, 人工知能学会全国大会（第12回）論文集，16-02
発表日 1998年06月

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

単純決定性言語のある部分族に対する多項式時間MAT学習
但馬康宏; 富田悦次; 若月光夫
口頭発表（一般）, 日本語, 人工知能学会全国大会（第12回）論文集，08-03
発表日 1998年06月

正の例から極限同定可能な言語クラスの統一的拡張手法
山田剛; 富田悦次; 若月光夫
口頭発表（一般）, 日本語, 人工知能学会人工知能基礎論研究会資料，SIG-FAI-9703-7
発表日 1998年03月

グラフ彩色問題における確率アルゴリズムとハイブリッドアルゴリズム
菊池淳; 富田悦次; 若月光夫
口頭発表（一般）, 日本語, 電子情報通信学会コンピュテーション研究会技術研究報告，COMP97-109
発表日 1998年03月

構造反例付き等価性質問を用いた単純決定性言語の多項式時間MAT学習
但馬康宏; 富田悦次; 若月光夫
口頭発表（一般）, 日本語, 電子情報通信学会コンピュテーション研究会技術研究報告，COMP97-59
発表日 1997年10月

組合せ最適化手法によるシュードノット構造を含んだRNAの二次構造予測
田中健夫; 若月光夫; 富田悦次
口頭発表（一般）, 日本語, 情報処理学会数理モデル化と問題解決研究会研究報告，96-MPS-10-4
発表日 1996年11月

実時間受理モード受理式DROCAの多項式時間包含性判定アルゴリズム
樋口健; 若月光夫; 富田悦次
口頭発表（一般）, 日本語, 電子情報通信学会コンピュテーション研究会技術研究報告，COMP95-97
発表日 1996年03月

グラフの近似彩色を行う確率アルゴリズム
菊池淳; 飯田卓; 富田悦次; 若月光夫
口頭発表（一般）, 日本語, 情報処理学会第52回全国大会講演論文集（分冊1），4U-7
発表日 1996年03月

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

最大重みクリークの抽出アルゴリズムのRNAの二次構造予測への適用
若月光夫; 田中健夫; 富田悦次
口頭発表（一般）, 日本語, 情報処理学会第52回全国大会講演論文集（分冊1），3U-9
発表日 1996年03月

最大重みクリークの近似抽出解法によるRNAの二次構造予測
田中健夫; 若月光夫; 富田悦次
口頭発表（一般）, 日本語, 1995年電子情報通信学会情報・システムソサイエティ大会講演論文集，D-10
発表日 1995年09月

Very Simple DPDの包含性判定を行う高速アルゴリズム
Mitsuo Wakatsuki; Etsuji Tomita
口頭発表（一般）, 英語, 電子情報通信学会コンピュテーション研究会技術研究報告，COMP92-43
発表日 1992年10月

単純決定性プッシュダウンオートマトンの等価性判定に要する最大時間計算量の改善
若月光夫; 富田悦次
口頭発表（一般）, 日本語, 電子情報通信学会コンピュテーション研究会技術研究報告，COMP90-24
発表日 1990年07月

単純決定性プッシュダウンオートマトンの等価性判定を行う直接的分岐アルゴリズムの改良
若月光夫; 富田悦次
口頭発表（一般）, 日本語, 電子情報通信学会コンピュテーション研究会技術研究報告，COMP90-23
発表日 1990年07月

Simple DPDAの等価性判定を行う直接的分岐アルゴリズム
若月光夫; 富田悦次; 小倉弘敬
口頭発表（一般）, 日本語, 電子情報通信学会コンピュテーション研究会技術研究報告，COMP87-81
発表日 1988年03月

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

1998年07月 - 現在
人工知能学会

1993年04月 - 現在
LAシンポジウム

1993年04月 - 現在
情報処理学会

1988年01月 - 現在
電子情報通信学会

形式言語の効率的学習アルゴリズムの開発及びその応用システムの構築
若月 光夫; 富田 悦次; 西野 哲朗
日本学術振興会, 科学研究費助成事業 基盤研究(C), 電気通信大学, 基盤研究(C), 研究代表者, 決定性プッシュダウン変換器のスタック記号を1種類に限定した決定性限定1カウンタ変換器について，それが最終状態受理式の場合，より一般的なε-推移を持つ場合についてもその等価性判定及び包含性判定が多項式時間で行えることを明らかにした．また，実時間最終状態受理式決定性限定1カウンタ変換器に対して，所属性質問及び等価性質問を用いた多項式時間の学習アルゴリズムを開発した．更に，正則言語の部分クラスに対する正例からの極限同定を組み込んだジュウシマツの歌構造解析ツールEUREKAを利用することによって，コンピュータ上でトランプゲームの大貧民の対戦を行うプログラムの挙動の規則性が抽出可能なことを示した．, 23500011
研究期間 2011年04月 - 2015年03月

形式言語に対する例からの学習を行う効率的アルゴリズムの開発・応用
若月 光夫; 富田 悦次; 西野 哲朗
日本学術振興会, 科学研究費助成事業 基盤研究(C), 電気通信大学, 基盤研究(C), 研究代表者, 決定性プッシュダウン変換器のスタック記号を1 種類に限定した決定性限定ワンカウンタ変換器について,それが空スタック受理式及び実時間最終状態受理式の場合,その等価性判定が多項式時間で行えることを証明した.また,決定性限定ワンカウンタオートマトンのある部分クラス等が,正例から多項式時間で極限同定可能なことを証明した.更に,正則言語の部分クラスに対する正例からの極限同定を利用した,ジュウシマツの歌文法の解析手法を改良し,自動化を図った., 20500007
研究期間 2008年04月 - 2011年03月

決定性文脈自由言語の部分クラスに対する学習アルゴリズムの開発と応用
若月 光夫; 富田悦次
日本学術振興会, 科学研究費助成事業 基盤研究(C), 電気通信大学, 基盤研究(C), 研究代表者, 計算論的学習理論は,人工知能の実現において最も重要な研究分野の一つである機械学習に対し,その可能性について数理的で厳密に解析を行うパラダイムである.その研究対象として形式言語を選択し,その部分クラスの中で実用上重要な決定性文脈自由言語を受理する決定性プッシュダウンオートマトン(DPDA)またはそれに対応した文法等に対し,その構造に妥当な制約を課した幾つかの部分クラスを対象として,計算論的な手法によって学習アルゴリズムを開発し,その応用を図ることを目的として研究を行った.その結果,以下の研究成果を得た. 1.学習アルゴリズム開発の基礎構築DPDAに出力機構を付与した決定性プッシュダウン変換器(DPDT)の等価性問題について,ε-推移を許したある種のDPDTに対する単純かつ直接的な判定アルゴリズムを開発し,これまでに発表した研究成果を拡張した.また,実時間空スタック受理式決定性限定ワンカウンタ変換器と呼ぶDPDTの部分クラスに限定した場合,その等価性判定が多項式時間で行えることを証明した.等価性判定は形式言語の学習において重要な意味を持っており,上記成果はDPDTの部分クラスに対する質問による学習に利用することが期待できる. 2.学習アルゴリズムの開発ある種の言語クラスを元にして準同型写像による変換を施すことで得られる言語クラスに対し,正例からの極限同定を統一的に扱える手法を開発した.また,Szilard strict DROCAと呼ぶDPDAの部分クラス,および有限状態のある種の変換器(DPDTの真部分クラス)に対する,正例からの極限同定アルゴリズムをそれぞれ開発し,ある意味において多項式時間極限同定可能であることを明らかにした. 上記の研究成果を踏まえ,今後はこれまでに開発してきた学習アルゴリズムを実際の問題事例に適用し,応用することを計画している., 18500108
研究期間 2006年04月 - 2008年03月

大脳における機能的結合問題の工学モデルとその応用に関する研究
高橋 治久; 若月 光夫; 西野 哲朗; 富田 悦次
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 高等生物において,外界からの情報が脳内で解析的に処理された後,いかにそれらが統合されるかを説明する問題をバインディング問題とよぶ.本研究では,バインディングを説明できるニューラルモデルの構築と応用を目指して研究を行った.従来のモデルでは,バインディングを説明するためのスパイクの同期あるいは相関を表すことができない.そこで,本研究では従来のアナログニューラルモデルの自然な拡張で,スパイクの相関や同期を位相として表現できる位相ニューラルモデルを開発し,その正当性と学習アルゴリズムを提案した.提案した位相ニューラルモデルは,振動モデルと,コバリアンスモデルの二つであり,これらに対し,Hebb学習則の提案とボルツマン学習規則を導出し,その計算機シミュレーション実験と応用を行った.まず,Hebb規則では,コバリアンスを考慮した本来の意味での学習則が初めて簡単な数理モデルに組み込めた.シミュレーション実験では,これが収束することを確認し,文字認識への応用を行った.さらに,ボルツマンマシンの学習規則が位相モデルに自然に拡張できることを示し,学習規則を導いた.とくにコバリアンス位相モデルは,従来のミーンフィールドモデルの拡張であり,相関も考慮しているため精度良く確率モデルの近似が行われる.計算機シミュレーションの結果,ミーンフィールドモデルでは収束しない多くの問題が,位相コバリアンスモデルでは収束することが示された.本研究では更に,学習の汎化性能を解析しいくつかの基本的な結果を,得ることができた.またバインディングに関して理論的モデルを構築した結果得られた知見を,音声認識と脳波識別に応用し従来のものより格段に性能の良い識別機を提案した., 10650353
研究期間 1998年 - 2000年

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

科学研究費委員会奨励研究部会理工系小委員会審査委員
審査・学術的助言, 審査・評価, 日本学術振興会, 実施期間 2016年12月 - 2017年03月