![](https://researchers.uec.ac.jp/search/content/images/noimage.png)
西野 哲朗
名誉教授・その他関係者 | 名誉教授 |
研究者情報
委員歴
- 2015年 - 2016年
審査・評価第二部会 情報学小委員会委員, 日本学術振興会 科学研究費委員会, 学協会 - 2013年04月 - 2016年
ゲーム情報学研究会 運営委員, 情報処理学会 - 2013年04月 - 2016年
数理モデル化と問題解決研究会 編集委員, 情報処理学会 - 2016年
領域アドバイザー:研究領域「量子状態の高度な制御に基づく革新的量子技術基盤の創出」, 科学技術振興機構 戦略的創造研究推進事業(CREST), 学協会 - 1999年 - 1999年
論文誌編集委員会主査, 情報処理学会, 学協会 - 1998年 - 1998年
論文誌編集委員会副査, 情報処理学会, 学協会 - 1996年 - 1998年
コンピュテーション研究専門委員, 電子情報通信学会, 学協会 - 1996年 - 1998年
人工知能基礎論研究会幹事, 人工知能学会, 学協会 - 1994年 - 1996年
コンピュテーション研究会幹事, 電子情報通信学会, 学協会 - 1992年 - 1992年
学会誌編集委員会主査, 情報処理学会, 学協会
研究活動情報
受賞
論文
- Automatic extractive summarization for Japanese documents by LDA
Hideyuki Sawahata; Tetsuro Nishino
Proceedings of 11th International Congress on Advanced Applied Informatics, 81巻, 掲載ページ 41-52, 出版日 2021年12月17日, 査読付
研究論文(国際会議プロシーディングス), 英語 - Distinguishing between humans and computers in a card game with imperfect information
Seiya Okubo; Masato Konishi; Mitsuo Wakatsuki; Tetsuro Nishino
Proceedings of the 34th International Conference on CAINE 2021, EPiC Series in Computing, 79巻, 掲載ページ 140-149, 出版日 2021年10月, 査読付
研究論文(国際会議プロシーディングス), 英語 - 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年, 査読付
研究論文(学術雑誌), 英語 - 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, 4巻, 1号, 掲載ページ 18-35, 出版日 2020年, 査読付
研究論文(学術雑誌), 英語 - 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 2019, 掲載ページ 587-529, 出版日 2019年07月07日, 査読付
研究論文(国際会議プロシーディングス), 英語 - 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 2019, 掲載ページ 623-628, 出版日 2019年07月07日, 査読付
研究論文(国際会議プロシーディングス), 英語 - Toward a statistical characterization of Computer Daihinmin
Seiya Okubo; Yuuta Kado; Yamato Takeuchi; Mitsuo Wakatsuki; Tetsuro Nishino
International Journal of Software Innovation, 7巻, 1号, 掲載ページ 63-79, 出版日 2019年, 査読付
研究論文(学術雑誌), 英語 - Route search method for autonomous mobile robots using machine learning
Mitsuo Wakatsuki; Seiya Okubo; Tetsuro Nishino
31th International Conference on Computer Applications in Industry and Engineering (CAINE 2018), 掲載ページ 71-76, 出版日 2018年10月, 査読付
研究論文(国際会議プロシーディングス), 英語 - 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月01日, 査読付, 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.
研究論文(学術雑誌), 英語 - Improve example-based machine translation quality for low-resource language using ontology
Khan Md Anwarus Salam; Setsuo Yamada; Nishio Tetsuro
Studies in Computational Intelligence, Springer Verlag, 727巻, 2017号, 掲載ページ 67-90, 出版日 2018年, 査読付, In this research we propose to use ontology to improve the performance of an EBMT system for low-resource language pair. The EBMT architecture use (CSTs) and unknown word translation mechanism. CSTs consist of a chunk in source-language, a string in target-language, and word alignment information. For unknown word translation, we used WordNet hypernym tree and English-Bengali dictionary. CSTs improved the wide-coverage by 57 points and quality by 48.81 points in human evaluation. Currently 64.29% of the test-set translations by the system were acceptable. The combined solutions of CSTs and unknown words generated 67.85% acceptable translations from the test-set. Unknown words mechanism improved translation quality by 3.56 points in human evaluation.
研究論文(学術雑誌), 英語 - Decision tree analysis in game informatics
Masato Konishi; Seiya Okubo; Tetsuro Nishino; Mitsuo Wakatsuki
Studies in Computational Intelligence, Springer Verlag, 727巻, 掲載ページ 13-27, 出版日 2018年, 査読付, 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.
研究論文(学術雑誌), 英語 - Decision tree analysis in game informatics
Masato Konishi; Seiya Okubo; Tetsuro Nishino; Mitsuo Wakatsuki
Studies in Computational Intelligence, Springer Verlag, 727巻, 掲載ページ 13-27, 出版日 2018年, 査読付, 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.
研究論文(学術雑誌), 英語 - Example-Based Machine Translation Quality for Low-Resource Language Using Ontology
Khan Md; Anwarus Salam; Setsuo Yamada; Tetsuro Nishino
5th International Conference on Applied Computing & Information Technology (ACIT 2017), July 9-13,巻, 2017号, 掲載ページ 176-191, 出版日 2017年, 査読付
研究論文(国際会議プロシーディングス), 英語 - Toward A Statistical Analysis of Computer Daihinmin
Seiya Okubo; Yuuta Kado; Yamato Takeuchi; Mitsuo Wakatsuki; Tetsuro Nishino
5th International Conference on Applied Computing & Information Technology (ACIT 2017), July 9-13,巻, 2017号, 出版日 2017年, 査読付
研究論文(国際会議プロシーディングス), 英語 - Strengthening Methods of Computer Daihinmin Programs
Mitsuo Wakatsuki; Yasuki Dobashi; Tasuku Mitsuishi; Seiya Okubo; Tetsuro Nishino
ISCA 30th International Conference on Computer Applications in Industry and Engineering (CAINE-2017), October 2-4,巻, 2017号, 出版日 2017年, 査読付
研究論文(国際会議プロシーディングス), 英語 - 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, 4巻, 2号, 掲載ページ 58-70, 出版日 2016年04月01日, 査読付
研究論文(学術雑誌), 英語 - Cluster Analysis Using N-gram Statistics for Daihinmin Programs and Performance Evaluations
Seiya Okubo; Takaaki Ayabe; Tetsuro Nishino
International Journal of Software Innovation, Vol.4巻, No.2号, 掲載ページ 33-57, 出版日 2016年, 査読付
研究論文(学術雑誌), 英語 - Feature Extraction and Cluster Analysis Using N-gram Statistics for DAIHINMIN Programs
Seiya Okubo; Takaaki Ayabe; Tetsuro Nishino
APPLIED COMPUTING & INFORMATION TECHNOLOGY, SPRINGER-VERLAG BERLIN, 619巻, 掲載ページ 27-41, 出版日 2016年, 査読付, In this paper, we elucidate the characteristics of the computer program to play DAIHINMIN, which is a popular Japanese card game with imperfect information. First, we propose a method to extract feature values using the n-gram statistics and a cluster analysis method using the feature values. By representing the program hands as several symbols and representing the order of hands as simplified symbol strings, we obtained the data suitable for feature extraction. Next, we evaluated the effectiveness of the proposed method through computer experiments. In these experiments, we applied our method to ten programs which were used in UECda contest. Finally, we show that our proposed method can successfully cluster DAIHINMIN programs with high probability.
研究論文(国際会議プロシーディングス), 英語 - A prototyping tool for developing ICT based course material for children with developmental disability
Hirokazu Asano; Takaaki Goto; Tetsuro Nishino
28th International Conference on Computer Applications in Industry and Engineering, CAINE 2015, International Society of Computers and Their Applications (ISCA), 掲載ページ 221-225, 出版日 2015年, Education programs for children with developmental disabilities have attempted to include information and communication technology (ICT) teaching materials. Thus, the Chofu Special Needs School and the University of Electro-Communications collaborated to develop teaching materials suitable for each child with developmental disabilities. Obtaining the requirements for ICT-based materials is difficult because teachers often have problems communicating with students regarding software specifications. In this study, we propose a tool for developing ICT-based course material for children with developmental disabilities and describe the results of the evaluation of the proposed tool.
研究論文(国際会議プロシーディングス), 英語 - 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, The International Society for Computers and Their Applications (ISCA), 掲載ページ 11-18, 出版日 2015年, This paper is concerned with a subclass of deterministic pushdown transducers, called deterministic restricted one-counter transducers (droct's), and studies the inclusion problem for droct's which accept by final state. In the previous study, we presented a polynomialtime algorithm for checking the equivalence of these droct's. By extending this technique, we present a polynomial-time algorithm for checking the inclusion of these droct's.
研究論文(国際会議プロシーディングス), 英語 - Parsing of UML package diagrams
Takaaki Goto; Tadaaki Kirishima; Tetsuro Nishino; Takeo Yaku; Kensei Tsuchida
Proceedings of the 30th International Conference on Computers and Their Applications, CATA 2015, 掲載ページ 25-30, 出版日 2015年, Copyright © 2015 by The International Society for Computers and Their Applications (ISCA). Program diagrams are used when we develop software. Unified Modeling Language (UML) is also used in software development. Package diagram is one of a diagram used in UML. Package diagram plays an important role to design or analyze structures of systems. So far we proposed a graph grammar for package diagram in order to formalize manipulation of package diagram. In this paper, we propose a parsing method of proposed a graph grammar for package diagram.
研究論文(国際会議プロシーディングス) - 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 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, 掲載ページ 67-72, 出版日 2015年, 査読付, 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.
研究論文(国際会議プロシーディングス), 英語 - Methodology for developing ICT based course material for children with a developmental disability based on EPISODE
Takahiro Kaneyama; Takaaki Goto; Tetsuro Nishino
PROCEEDINGS 2015 IEEE INTERNATIONAL CONFERENCE ON INDUSTRIAL INFORMATICS (INDIN), IEEE, 掲載ページ 1654-1658, 出版日 2015年, 査読付, Education curricula for children with developmental disabilities have attempted to include information and communication technology (ICT) teaching materials. However, such children demonstrate individual differences at the developmental stage of their cognitive faculties. Thus, it is difficult to adopt commercially available ICT teaching materials when working with them. In this study, we introduce the concept of inclusive design in the implementation of ICT teaching materials for children with developmental disabilities. Inclusive design allows for the participation of the elderly as well as those with disabilities at the early stages of development and can be used to identify special needs associated with the development. In addition to ICT teaching materials, the use of Extreme Programming Method for Innovative Software Based on Systems Design (EPISODE), which has agile development and innovation techniques at its core, has been proposed. Therefore, in this study, we attempt to develop a method comprising inclusive design and EPISODE to develop ICT teaching materials. Finally, we report on the practice of developing ICT teaching materials for children with developmental disabilities.
研究論文(国際会議プロシーディングス), 英語 - Generation of UML package diagrams based on an attribute graph grammar
Takaaki Goto; Tadaaki Kirishima; Tetsuro Nishino; Takeo Yaku; Kensei Tsuchida
JOURNAL OF COMPUTATIONAL SCIENCE, ELSEVIER SCIENCE BV, 5巻, 4号, 掲載ページ 606-615, 出版日 2014年07月, 査読付, Graphical representations are often used in software design and development because of their expressiveness. So far, various graphical program description languages have been reported. The Unified Modeling Language (UML), developed for modeling in software development was proposed recently, and in 2005 was standardized as the ISO/IEC 19501 standard.
Some tools for drawing UML diagrams have been proposed in recent years. However, it is hard for developers to draw UML diagrams using the UML tool because diagram layouts generally should be manually adjusted. Of course, there are tools that can automatically provide layout diagrams, though, sometimes such functions provide unexpected layouts.
In order to automate the drawing of these graphical representations aesthetically, a syntax for program diagrams must first be defined. We propose a framework for specifying these diagrams using a graph grammar, and a syntax-directed editor based on the graph grammar. (C) 2014 Elsevier B.V. All rights reserved.
研究論文(学術雑誌), 英語 - 最大クリーク問題の多項式時間的可解性の拡張の改良
中西裕陽; 富田悦次; 若月光夫; 西野哲朗
電子情報通信学会論文誌D分冊, J97-D巻, 6号, 掲載ページ 1106-1121, 出版日 2014年06月, 査読付
研究論文(学術雑誌), 日本語 - Software Ontology Design to Support Organized Open Source Software Development
Md Mahfuzus Salam Khan; Md Anwarus Salam Khan; Takaaki Goto; Tetsuro Nishino; Narayan Debnath
2014 15TH IEEE/ACIS INTERNATIONAL CONFERENCE ON SOFTWARE ENGINEERING, ARTIFICIAL INTELLIGENCE, NETWORKING AND PARALLEL/DISTRIBUTED COMPUTING (SNPD), IEEE, 掲載ページ 393-398, 出版日 2014年, 査読付, In the field of software engineering, a very old and important issue is how to understand the software. Understanding software means more than understanding the source code; it also refers to the other facts related to that particular software. Sometimes even experienced developers can be overwhelmed by a project's extensive development capabilities. In the development process, project leaders (PLs) have overall knowledge about the project and are keenly aware of its vision. Other members have only partial knowledge of the functions assigned to them. In this research, we propose a model to design ontology to support software comprehension and handle issues of knowledge management throughout the development process. By applying our methodology, understanding software and managing knowledge can become possible in a systematic way for open source and commercial projects. Furthermore, it will help beginners become more involved in a project and contribute to it in a productive way.
研究論文(国際会議プロシーディングス), 英語 - EPISODE: An Extreme Programming Method for Innovative Software Based on Systems Design
Takaaki Goto; Kensei Tsuchida; Tetsuro Nishino
2014 IIAI 3RD INTERNATIONAL CONFERENCE ON ADVANCED APPLIED INFORMATICS (IIAI-AAI 2014), IEEE, 掲載ページ 780-784, 出版日 2014年, 査読付, In software development, the waterfall model is commonly used, especially for large-scale software systems. For smaller-scale software development, agile software development approaches such as extreme programming or scrum are used. Traditional software development methodologies are mainly targeted toward customer-centric development, and therefore, new software methodologies are often not well received in the industry. In this study, we propose a new software development methodology that is aimed at developing innovative software using artificial intelligence (AI), idea creation, value engineering, and systems design. The name of our method is named as EPISODE (Extreme Programming method for Innovative SOftware based on systems DEsign). EPISODE supports the efficient and creative development of open source software (OSS) by small groups.
研究論文(国際会議プロシーディングス), 英語 - 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年, 査読付, 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.
研究論文(国際会議プロシーディングス), 英語 - EPISODE: An Extreme Programming Method for Innovative Software Baed on Systems Design and its Practical Study
Takaaki Goto; Kensei Tsuchida; Tetsuro Nishino
International Journal of Software Engineering & Applications, 5巻, 5号, 掲載ページ 1-13, 出版日 2014年, 査読付
研究論文(学術雑誌), 英語 - A source code plagiarism detecting method using alignment with abstract syntax tree elements
Hiroshi Kikuchi; Takaaki Goto; Mitsuo Wakatsuki; Tetsuro Nishino
2014 IEEE/ACIS 15th International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing, SNPD 2014 - Proceedings, Institute of Electrical and Electronics Engineers Inc., 3巻, 3号, 掲載ページ 41-56, 出版日 2014年, 査読付, 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.
研究論文(国際会議プロシーディングス), 英語 - Web Based UNL Ontology Visualization
Khan Md; Anwarus Salam; Hiroshi Uchida; Setsuo Yamada; Tetsuro Nishino
Journal of Convergence Information Technology, 8巻, 13号, 出版日 2013年08月, 査読付
研究論文(学術雑誌), 英語 - 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
Proceedings of the 14th IEEE/ACIS International Conference of Software engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing (SNPD2013), 掲載ページ 459-465, 出版日 2013年07月01日, 査読付
研究論文(国際会議プロシーディングス), 英語 - An attribute labeled grid graph grammar and its application to program specification forms
Tomokazu Arita; Tetsuro Nishino; Kimio Sugita; Kensei Tsuchida; Takeo Yaku
Studies in Computational Intelligence, Springer Verlag, 443巻, 掲載ページ 201-214, 出版日 2013年, In this paper, we introduce attribute graph grammars for labeled grid graphs, and propose their application to generating tabular forms representing program specification forms with grid structures, such as two-dimensional arrays. An attribute graph grammar to formalize tabular forms with grid structures and their layout information is defined by a context-sensitive graph grammar with semantic rules attached to its productions. Formalization of tabular forms based on an attribute graph grammar is enables detection of syntactic errors in item placement and solving of tabular form layout problems by evaluating the grammar's semantic rules. A parsing algorithm is proposed for detecting syntactic errors that is based on an attribute graph grammar for labeled grid graphs representing tabular forms. The production sequence for a tabular form is obtained by this parsing process. A table layout problem for a tabular form with a grid structure is solved by evaluating the grammar's semantic rules based on the production sequence. © 2013 Springer-Verlag Berlin Heidelberg.
研究論文(国際会議プロシーディングス), 英語 - How to translate unknown words for english to bangla machine translation using transliteration
Khan Md. Anwarus Salam; Setsuo Yamada; Tetsuro Nishino
Journal of Computers (Finland), 8巻, 5号, 掲載ページ 1167-1174, 出版日 2013年, 査読付, Due to small available English-Bangla parallel corpus, Example-Based Machine Translation (EBMT) system has high probability of handling unknown words. To improve translation quality for Bangla language, we propose a novel approach for EBMT using WordNet and International-Phonetic-Alphabet(IPA)-based transliteration. Proposed system first tries to find semantically related English words from WordNet for the unknown word. From these related words, we choose the semantically closest related word whose Bangla translation exists in English-Bangla dictionary. If no Bangla translation exists, the system uses IPA-based-transliteration. If unknown word is not found in the English IPA dictionary, the system uses Akkhor transliteration mechanism. We implemented the proposed approach in EBMT, which improved the quality of good translation by 16 points. © 2013 ACADEMY PUBLISHER.
研究論文(学術雑誌), 英語 - Universal Words relationship question-answering from UNL Ontology
Khan Md. Anwarus Salam; Hiroshi Uchida; Setsuo Yamada; Tetsuro Nishino
2013 IEEE/ACIS 12th International Conference on Computer and Information Science, ICIS 2013 - Proceedings, ICIS 2013巻, 掲載ページ 423-427, 出版日 2013年, 査読付, Universal Networking Language (UNL) represents natural language sentences as a semantic network of Universal Words (UWs). UNL Ontology provides the semantic background using relations for each UWs. However UWs are formal and all information provided by the UNL Ontology may not be understandable for human without the UNL specification. Especially we need to ensure the UW dictionary editors can understand the UWs information stored in UNL Ontology. To understand the UWs information, this research propose a question-answering system to provide the relationship information by explaining UWs relations with natural language. Using this system, the editors can easily understand the relationship information stored in UNL ontology. © 2013 IEEE.
研究論文(国際会議プロシーディングス), 英語 - Brain-inspired motion programming for hobby-use humanoid robots
Mamoru Kubota; Tadashi Yamazaki; Tetsuro Nishino
SNPD 2013 - 14th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing, SNPD 2013.37巻, 掲載ページ 472-477, 出版日 2013年, 査読付, Dynamic motion of hobby-use humanoid robots is defined by a sequence of static poses. Each pose is defined by specifying joint angles numerically for each joint. This is a difficult task, because typical hobby-use humanoid robots have motions easier. Our brain employs a different strategy for motion programming. Instead of specifying each joint angle or each muscle tone, the primary motor cortex has a set of primitive motions called motor primitives, and higher cortical areas and the basal ganglia generates a sequence of combinations of such motor primitives. Thus, our brain uses more abstract form to compose dynamic motions. In this article, we employ self-organizing maps (SOMs), which is an unsupervised learning algorithm used in machine learning and computational neuroscience communities, to extract motor primitives from a set of motion data of a hobby use humanoid robot. Then, we reprogram the original dynamic motions by the sequence of combinations of extracted primitives. We are able to reproduce the same motions by the proposed method. These results suggest that our brain-inspired method provides an easier means to program hobby-use humanoid robots than existing software bundled with the robots. © 2013 IEEE.
研究論文(国際会議プロシーディングス), 英語 - 高信頼細粒度部品再利用による形式手法におけるソフトウェア合成
中村丈洋; 織田健; 西野哲朗
情報処理学会論文誌, pp.2012-2024, 2013., 54巻, 8号, 掲載ページ 2012-2024, 出版日 2013年, 査読付, 部品再利用によるソフトウェア合成は開発コスト低減や信頼性向上に有効であるが,高信頼な部品の整備が容易でなく,また,適用可能な問題領域が限定される点が問題となる.本稿ではこの問題に対してモデル充足ソフトウェア合成(MSSS)を提案する.MSSSは形式手法B Methodの信頼性保証を応用したモデル充足細粒度部品に数学的判定による健全性の高い再利用を適用してソフトウェアを合成する.これにより部品の信頼性を静的に保証でき,また変数名や部品名の解釈に起因する誤りを排除できる.一方で変数名や部品名に意味を持たせないため,部品名での機能の呼び出しによる合成ができず,変数名の書き換えや結合が必要になる.よって,本稿ではMSSSの信頼性を'モデル充足'として数学的に定義し,そこからMSSSの手順を定めることで,互いに矛盾しない部品群を再利用したソフトウェアがB Methodの信頼性を満たすことを保証する.また,MSSSでは要求仕様を一意の粒度に細分化して部品の仕様に対する検索キーとするため,検索キーを不足部品の仕様として提示でき,さらに,部品自動生成により部品を容易に整備できる.これにより,合成手法を適用可能な問題領域の拡大と,それによる高信頼ソフトウェア開発の低コスト化と迅速化が期待できる.Software synthesis by reusing software components is effective to reduce development cost and to increase dependency. Nevertheless, it is not easy to prepare components, so domains to apply synthesis are limited. we must prepare components for each software domain to apply synthesis, and it's difficult to prepare dependable components. In this paper, we propose 'Model Satisfiable Software Synthesis (MSSS)' to resolve these problems. MSSS synthesises software by reusing 'Model Satisfiable Fine-grained Component (MSFC)' mathematically. We can ensure static dependability of MSFC by B Method. And mathematical reuse prevents bugs caused by misunderstanding of function name. However, MSSS needs intricate rewriting and combination to interlock MSFCs, because we can't reuse them by name of function. So we define mathematical dependency of MSSS as 'model satisfiable' to define procedure of it. MSSS slices requirement uniquely to search components by sliced requirement. So we can make lacked components easily by using search-keys as specification of them. And also we can generate MSFCs from existing software. MSSS will enable us to apply synthesis to more software domains, and to develop dependable software quickly in lower cost.
研究論文(学術雑誌), 日本語 - A Case Study of Calculation of Source Code Module Importance
Takaaki Goto; Setsuo Yamada; Tetsuro Nishino; Kensei Tsuchida
Proceedings of The 2013 International Conference on Parallel and Distributed Processing Techniques and Applications, I巻, 掲載ページ 155-160, 出版日 2013年, 査読付
研究論文(国際会議プロシーディングス), 英語 - A polynomial-time algorithm for checking the equivalence for real-time deterministic restricted one-counter taransducers which accept by final state
Mitsuo Wakatsuki; Etsuji Tomita; Tetsuro Nishino
International Journal of Computer and Information Science, 14巻, 2号, 掲載ページ 45-53, 出版日 2013年, 査読付
研究論文(学術雑誌), 英語 - O(n) and O(n 2) time algorithms for drawing problems of tree-structured diagrams
Tadaaki Kirishima; Tomoo Sumida; Yasunori Shiono; Goto Takaaki; Takeo Yaku; Tetsuro Nishino; Kensei Tsuchida
Proceedings - 13th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, SNPD 2012, 掲載ページ 530-535, 出版日 2012年, 査読付, We investigate sets of conditions with respect to narrower drawing of tree-structured diagrams on an integral lattice. We found that under certain sets of conditions there are practical procedural algorithms for narrower drawing of tree-structured diagrams, while under other sets of conditions there are none. Based on our findings, we present efficient algorithms that provide narrower placement satisfying given amorphous conditions. In intractable conditions, we propose a constraint-based algorithm for drawing tree-structured diagrams with a minimum-width by limiting the number of cells. Our results provide a criterion for deciding under given conditions, whether to use procedural or constraint-based algorithms to draw a tree-structured diagram. © 2012 IEEE.
研究論文(国際会議プロシーディングス), 英語 - UNL ontology visualization for web
Khan Md. Anwarus Salam; Hiroshi Uchida; Setsuo Yamada; Tetsuro Nishino
Proceedings - 13th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, SNPD 2012, 掲載ページ 542-545, 出版日 2012年, 査読付, Universal Networking Language (UNL) is an artificial language for computers to represent human language using graphs. UNL system consists of UNL Ontology, which provides the semantic background for each Universal Words (UWs) or concepts. UNL Ontology includes possible relations between UWs, UWs definition and UNL system hierarchy. UNL Ontology store all these information in a lattice structure, where UWs are inter-connected through relations including hierarchical relations such as icl (a-kind-of) and iof (an-instance-of). However, it is difficult for human to visualize the UNL ontology. To solve this problem, we have developed a web system to visualize UNL Ontology. This paper describes the web system and its real life applications. © 2012 IEEE.
研究論文(国際会議プロシーディングス), 英語 - Developing the First Balanced Corpus for Bangla Language
Khan Md. Anwarus Salam; Setsuo Yamada; Tetsuro Nishino
2012 INTERNATIONAL CONFERENCE ON INFORMATICS, ELECTRONICS & VISION (ICIEV), IEEE, 掲載ページ 1081-1084, 出版日 2012年, 査読付, The objective of this paper is to propose the development process of the first Bangladeshi National Corpus. The purpose of the study is to specify the domains to create a balanced Bangla corpus based on some selection criteria. This study focuses on three independent selection criteria: domain, time and medium. This paper also explains domain classifications and weight percentage for each domain. We also identify the prospective source of information for preparing the corpus.
研究論文(国際会議プロシーディングス), 英語 - Software Development Education Based on UEC Software Repository
Takaaki Goto; Takahiro Homma; Kensei Tsuchida; Tetsuro Nishino
SOFTWARE AND NETWORK ENGINEERING, SPRINGER-VERLAG BERLIN, 413巻, 掲載ページ 55-+, 出版日 2012年, 査読付, Most of the software developed in universities is primarily used by the developers themselves. Normally, most of this software is managed and stored on servers in the research laboratories, but since the software is generally lacking in documentation and is not developed with third-party use in mind, it tends to be used only by the original developers. It is seldom reused after the developers have graduated, and is often not in a fit state for use by third parties. Today's information systems graduates have not been provided with sufficient education with regard to the knowledge, techniques and experience needed for the usual software development process of actual software development businesses from project planning through to execution and management (requirements analysis, development, implementation, testing, etc.) and lack the basic skills for handling actual business situations. In this paper, we report on our approach to software management using the UEC software repository to consolidate software assets, and on practical software development education based on this repository.
研究論文(国際会議プロシーディングス), 英語 - Parallel Monte Carlo search for imperfect information game Daihinmin
Junji Nishino; Tetsuro Nishino
2012 FIFTH INTERNATIONAL SYMPOSIUM ON PARALLEL ARCHITECTURES, ALGORITHMS AND PROGRAMMING (PAAP), IEEE, 掲載ページ 3-6, 出版日 2012年, 査読付, Computer games, such as chess, have recently become an important research topic in the field of computation intelligence. Monto Carlo massive searching is very successful in the game of GO as it has a huge intractable search space and no good partial evaluation heuristics. Imperfect information games also have intractable properties, such as large scale search space, less heuristics, and unknown state information. Monte Carlo search is therefore effective to make computer players for the imperfect information game. There is always a time limit for using computational intelligence in actual applications. Such constraints require parallel processing to be speed up the Monte Carlo simulations.
We introduce a parallel Monte Carlo searching method for imperfect information card game Daihinmin, a familiar card game in Japan. Computer Daihinmin competitions have been held since 2006. We present two kinds of parallelization algorithms for Monte Carlo computer Daihinmin players.
研究論文(国際会議プロシーディングス), 英語 - 最大クリーク問題の多項式時間的可解性の拡張
中西裕陽; 富田悦次; 若月光夫; 西野哲朗
電子情報通信学会論文誌D分冊, J95-D巻, 9号, 掲載ページ 1716-1728, 出版日 2012年, 査読付
研究論文(学術雑誌), 日本語 - Practice and Evaluation of Open Source Software evelopment Education Based on the UEC Software Repository
Takaaki Goto; Kensei Tsuchida; Tetsuro Nishino
ACIS International Journal of Computer & Information Science, 13巻, 2号, 掲載ページ 37-45, 出版日 2012年, 査読付
研究論文(学術雑誌), 英語 - Stimulus-Dependent State Transition between Synchronized Oscillation and Randomly Repetitive Burst in a Model Cerebellar Granular Layer
Takeru Honda; Tadashi Yamazaki; Shigeru Tanaka; Soichi Nagao; Tetsuro Nishino
PLOS COMPUTATIONAL BIOLOGY, PUBLIC LIBRARY SCIENCE, 7巻, 7号, 出版日 2011年07月, 査読付, Information processing of the cerebellar granular layer composed of granule and Golgi cells is regarded as an important first step toward the cerebellar computation. Our previous theoretical studies have shown that granule cells can exhibit random alternation between burst and silent modes, which provides a basis of population representation of the passage-of-time (POT) from the onset of external input stimuli. On the other hand, another computational study has reported that granule cells can exhibit synchronized oscillation of activity, as consistent with observed oscillation in local field potential recorded from the granular layer while animals keep still. Here we have a question of whether an identical network model can explain these distinct dynamics. In the present study, we carried out computer simulations based on a spiking network model of the granular layer varying two parameters: the strength of a current injected to granule cells and the concentration of Mg2+ which controls the conductance of NMDA channels assumed on the Golgi cell dendrites. The simulations showed that cells in the granular layer can switch activity states between synchronized oscillation and random burst-silent alternation depending on the two parameters. For higher Mg2+ concentration and a weaker injected current, granule and Golgi cells elicited spikes synchronously (synchronized oscillation state). In contrast, for lower Mg2+ concentration and a stronger injected current, those cells showed the random burst-silent alternation (POT-representing state). It is suggested that NMDA channels on the Golgi cell dendrites play an important role for determining how the granular layer works in response to external input.
研究論文(学術雑誌), 英語 - How to develop universal vocabularies using automatic generation of the meaning of each word
Md. Anwarus Salam Khan; Hiroshi Uchida; Tetsuro Nishino
NLP-KE 2011 - Proceedings of the 7th International Conference on Natural Language Processing and Knowledge Engineering, 掲載ページ 243-246, 出版日 2011年, 査読付, To develop a computer-understandable and international-communication- language, we need not to develop a pivot language but an artificial language which can express every meaning in each natural language. That artificial language needs enough vocabulary to express the meanings contained in each language. Those vocabularies can only be developed by native speakers and should be defined by formal ways. Considering the situation, at this moment Universal Networking Language (UNL) is the best solution and Universal Words (UWs) are the most promising candidates. But UWs itself are formal and not always to be understandable for human. We need to provide the way to express the correct meaning of UWs for humans, to ensure every language speakers can create the correct UWs. The semantic backgrounds of each UWs are provided by UNL Ontology. This research proposes the way to auto generate the meaning of each UWs using UNL Ontology. © 2011 IEEE.
研究論文(国際会議プロシーディングス), 英語 - 最大クリーク問題の多項式時間的可解性の更なる改良結果
中西裕陽; 富田悦次; 若月光夫; 西野哲朗
電子情報通信学会論文誌D分冊, J94-D巻, 12号, 掲載ページ 2037-2046, 出版日 2011年, 査読付
研究論文(学術雑誌), 日本語 - 小脳スパイキングネットワークモデルにおける条件刺激強度依存性タイミング制御
本多武尊; 山崎匡; 田中繁; 西野哲朗
情報処理学会論文誌数理モデル化と応用, 情報処理学会, 3巻, 2号, 掲載ページ 1-10, 出版日 2010年03月, 査読付, 我々がこれまで構築してきた小脳顆粒層の大規模スパイキングネットワークモデルは,苔状線維刺激呈示からの時間経過を表現する.本研究では,時間経過表現が苔状線維刺激の強度によって制御されるかどうかを調べた.瞬目反射の条件付けの計算機シミュレーションを行い,条件刺激と侵害刺激のペアを繰り返し与えると,プルキンエ細胞が侵害刺激呈示のタイミングの直前で発火を停止するようになることを確認した.その後条件刺激の強度を上げると,プルキンエ細胞の発火停止のタイミングがより早まることを示した.この結果は,条件反応のタイミングを決定するプルキンエ細胞の発火停止のタイミングが条件刺激強度に依存して変化することを示唆する.We have been developing a large-scale spiking network model of the cerebellar granular layer that represents the passage of time (POT) from the mossy fibre (MF) stimulus onset. In this study, we examined whether the POT representation can be controlled by changing the strength of the MF stimulus. We conducted simulations of the delay eyeblink conditioning, in which pairing of a sustained conditioned stimulus (CS) conveyed by MFs with a delayed unconditioned stimulus (US) showed that the Purkinje cell (PC) learned to pause slightly earlier than the onset of the US. When we increased the CS strength, the PC pause shifted earlier. This result suggests that the timing of the conditioned response determined by that of PC pause is adaptively changed by the CS strength.
研究論文(学術雑誌), 日本語 - 多人数不完全情報ゲームの簡略化評価値による探索を用いた終盤データベースの構築
西野順二; 西野哲朗
情報処理学会論文誌数理モデル化と応用, 3巻, 2号, 掲載ページ 11-21, 出版日 2010年03月, 査読付
研究論文(学術雑誌), 日本語 - Behavioral verification in hichart development environment for embedded software
Takaaki Goto; Yasunori Shiono; Tetsuro Nishino; Takeo Yaku; Kensei Tsuchida
Proceedings - 9th IEEE/ACIS International Conference on Computer and Information Science, ICIS 2010, 掲載ページ 337-340, 出版日 2010年, 査読付, Developing embedded systems is becoming more complicated. However, the time taken to develop an embedded system must be shortened. Software development environments especially for test purposes are still inadequate. To reduce bugs, specifications in the upper process need to be checked, and model checking-methodologies are often used to do so. So far we have developed a visual software development environment for Hichart that targets LEGO MINDSTORM. We also enhanced the behavioral specifications table function to make it applicable to the environment for checking physical parameters of real machine. In this paper, we adopt model-checking methodologies to the environment. We propose a visual software development environment for embedded software with physical and logical checking. © 2010 IEEE.
研究論文(国際会議プロシーディングス), 英語 - A Possible Mechanism for Controlling Timing Representation in the Cerebellar Cortex.
Takeru Honda; Tadashi Yamazaki; Shigeru Tanaka; Tetsuro Nishino
Advances in Neural Networks - ISNN 2010, 7th International Symposium on Neural Networks, ISNN 2010, Shanghai, China, June 6-9, 2010, Proceedings, Part I, Springer, 掲載ページ 67-76, 出版日 2010年, 査読付 - A Feasible Approach for Automatic Detection and Recognition of the Bengalese Finch Songnotes and Their Sequences
Khan Md; Mahfuzus Salam; Tetsuro Nishino; Kazutoshi Sasahara; Miki Takahasi; Kazuo Okanoya
Journal of Intelligent Learning Systems and Applications, 2巻, 掲載ページ 221-228, 出版日 2010年, 査読付
研究論文(学術雑誌), 英語 - Automatic generation of SVG program documents with animation based on attribute graph grammars
Takaaki Goto; Tomoo Sumida; Tadaaki Kirishima; Takeo Yaku; Kensei Tsuchida
Proceedings - 9th IEEE/ACIS International Conference on Computer and Information Science, ICIS 2010, 13巻, 2号, 掲載ページ 347-350, 出版日 2010年, 査読付, We have been developing a software development environment using the program diagram "Hichart" [1, 2, 3]. In our research, we have implemented a graphical editor for Hichart. We add new features and capabilities to the editor, including calculation of a cyclomatic complexity and generation of SVG files for a given Hichart diagram. In this paper, we present a method of automatically generating a SVG file for a given program diagram based on attribute graph grammars. The thus obtained SVG file can animate a process of calculating a cyclomatic complexity of a given Hichart diagram on any readily available Web browsers. We also describe an automatic generation of a SVG file which can be displayed when diagrams are aesthetically drawn. © 2010 IEEE.
研究論文(国際会議プロシーディングス), 英語 - Hichart development environment for embedded software
Takaaki Goto; Yasunori Shiono; Takeo Yaku; Kensei Tsuchida; Tetsuro Nishino
TriSAI 2009 - Proceedings of Triangle Symposium on Advanced ICT 2009, 掲載ページ 17-20, 出版日 2009年12月01日, Embedded systems are becoming increasingly large and complicated, so development methodologies and efficient testing systems for embedded systems are highly desirable. Checking behavioral specification of upstream operations is especially important. At the same time, we have been studying a diagram called Hichart for many years and also developed a visual software development environment for Hichart. In this study, we expand our visual software development environment to support developing embedded systems. The target of this research is NQC, which is the program language for LEGO MINDSTORM. Our visual software development system for embedded system can (I) treat source codes for embedded Software as Hichart diagrams and (II) set physical parameters on behavioral specification table. - Strength of a conditional stimulus controls the timing of a conditional response: Computational study of the dynamics of a cerebellar spiking network model
T. Honda; T. Yamazaki; S. Tanaka; T. Nishino
Proc. of SfN 2009, N. 367.3/DD25号, 出版日 2009年10月, 査読付
研究論文(国際会議プロシーディングス), 英語 - Ethological data mining: an automata-based approach to extract behavioral units and rules
Yasuki Kakishita; Kazutoshi Sasahara; Tetsuro Nishino; Miki Takahasi; Kazuo Okanoya
DATA MINING AND KNOWLEDGE DISCOVERY, SPRINGER, 18巻, 3号, 掲載ページ 446-471, 出版日 2009年06月, 査読付, We propose an efficient automata-based approach to extract behavioral units and rules from continuous sequential data of animal behavior. By introducing novel extensions, we integrate two elemental methods-the N-gram model and Angluin's machine learning algorithm into an ethological data mining framework. This allows us to obtain the minimized automaton-representation of behavioral rules that accept (or generate) the smallest set of possible behavioral patterns from sequential data of animal behavior. With this method, we demonstrate how the ethological data mining works using real birdsong data; we use the Bengalese finch song and perform experimental evaluations of this method using artificial birdsong data generated by a computer program. These results suggest that our ethological data mining works effectively even for noisy behavioral data by appropriately setting the parameters that we introduce. In addition, we demonstrate a case study using the Bengalese finch song, showing that our method successfully grasps the core structure of the singing behavior such as loops and branches.
研究論文(学術雑誌), 英語 - Development of Web Counseling System
Yasunori Shiono; Takaaki Goto; Tetsuro Nishino; Chieko Kato; Kensei Tsuchida
2009 INTERNATIONAL CONFERENCE ON NETWORK-BASED INFORMATION SYSTEMS, IEEE, 掲載ページ 370-+, 出版日 2009年, 査読付, Some areas in Asian have no medical facilities and proper mental health care is unavailable. Therefore, online counseling systems are needed. We have been studying and putting into practice online counseling for people assigned overseas. We constructed a system using agile software development for those assigned overseas in Asia. The first step involved developing a prototype system based on system requirements after we repeatedly discussed system development with people in charge of a clinic. Next, we conducted interviews about the online counseling system. We also discussed and analyzed the interviews. Finally, we completed the online Web counseling system by repeatedly discussing possible improvements with the clinic and then incorporating the changes in the system. We report on the construction of the system.
研究論文(国際会議プロシーディングス), 英語 - The P Versus NP Problem
Tetsuro Nishino
SUGAKU EXPOSITIONS, Vol.22巻, No.2号, 掲載ページ 215-228, 出版日 2009年, 査読付
研究論文(学術雑誌), 英語 - 小脳顆粒層をモデル化したスパイキングネットワークの研究:NMDA受容体を介した同期発火状態と時間表現状態の遷移
本多武尊; 山崎匡; 田中繁; 西野哲朗
電子情報通信学会論文誌 D, 一般社団法人電子情報通信学会, J91-D巻, 11号, 掲載ページ 2709-2718, 出版日 2008年11月, 査読付, 本研究では,小脳穎粒層のスパイキングネットワークモデルを構築し,その挙動を解析した.入力刺激が弱いときは,穎粒細胞は9Hz程度で同期発火した.入力刺激が強いときは,穎粒細胞は間欠的にスパイク発射状態と停止状態を繰り返し,細胞集団の発火パターンにより時間経過を表現した.よって,小脳穎粒層の活動状態は苔状線維信号の強さによって制御されることが示唆された.また,時間経過を表現する発火パターンの生成には再現性があった.NMDAチャネルをブロックすると,このような状態遷移は見られなくなった.更に,瞬目反射のタイミング学習のシミュレーションも行った.音刺激(CS)が苔状線維から入力されると,穎粒細胞の発火パターンがCS呈示開始からの時間経過を表現し,平行線維-プルキンエ細胞間シナプスで長期抑圧(LTD)が生じ,プルキンエ細胞は侵害刺激(US)入力の前後でスパイク発射を停止することを学習した.
日本語 - 小脳顆粒層をモデル化したスパイキングネットワークの研究:NMDA受容体を介した同期発火状態と時間表現状態の遷移
本多武尊; 山崎匡; 田中繁; 西野哲朗
電子情報通信学会論文誌 D, J91-D巻, 11号, 掲載ページ 1-10, 出版日 2008年, 査読付
研究論文(学術雑誌), 英語 - 小脳顆粒層をモデル化したスパイキングネットワークの研究:NMDA受容体を介した同期発火状態と時間表現状態の遷移
本多武尊; 山崎匡; 田中繁; 西野哲朗
電子情報通信学会論文誌 D, Vol.J91-D巻, No.11号, 掲載ページ 1-10, 出版日 2008年, 査読付
研究論文(学術雑誌), 日本語 - Pattern extraction improves automata-based syntax analysis in songbirds
Yasuki Kakishita; Kazutoshi Sasahara; Tetsuro Nishino; Miki Takahasi; Kazuo Okanoya
PROGRESS IN ARTIFICIAL LIFE, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 4828巻, 掲載ページ 320-+, 出版日 2007年, 査読付, We propose an automata induction approach to modeling birdsongs on the basis of Angluin's induction algorithm, which ensures that k-reversible languages can be learned from positive samples in polynomial time. There are similarities between Angluin's algorithm and the vocal learning of songbirds; for example, during a critical period, songbirds learn songs from positive samples of conspecific birds. In our previous method, we could not construct song syntaxes for complex songs. In this paper, we introduce a pattern extraction method to improve our previous method and propose a new birdsong modeling method. We estimate the robustness and properness of our method by using artificial song data, and demonstrate that the song syntaxes of the Bengalese finch can be successfully represented as reversible automata. As a result, almost all Bengalese finchs' song syntaxes can be represented with lower k-reversibility; further, one song has 3-reversibility song syntax showing the highest reversibility.
研究論文(国際会議プロシーディングス), 英語 - インターナルクロックモデルに基づくロボット制御法の実現
眞鍋秀聡; 西野哲朗; 山崎匡; 田中繁
情報処理学会論文誌:数理モデル化と応用, 48巻, SIG19(TOM19)号, 掲載ページ 139-154, 出版日 2007年, 査読付
研究論文(学術雑誌), 日本語 - Constructing song syntax by automata induction
Kazutoshi Sasahara; Yasuki Kakishita; Tetsuro Nishino; Miki Takahasi; Kazuo Okanoya
GRAMMATICAL INFERENCE: ALGORITHMS AND APPLICATIONS, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 4201巻, 掲載ページ 351-353, 出版日 2006年, 査読付
研究論文(学術雑誌), 英語 - A reversible automata approach to modeling birdsongs
Kazutoshi Sasahara; Yasuki Kakishita; Tetsuro Nishino; Miki Takahasi; Kazuo Okanoya
CIC 2006: 15TH INTERNATIONAL CONFERENCE ON COMPUTING, PROCEEDINGS, IEEE COMPUTER SOC, 掲載ページ 80-+, 出版日 2006年, 査読付, We propose a new automata-based approach to modeling birdsongs on the basis of Angluin's induction algorithm, which ensures that k-reversible languages can be learned from positive samples with polynomial time. There are similarities between Angluin's algorithm and the vocal learning of songbirds; for example, during a critical period, songbirds also learn songs from positive samples of conspecific birds. Using the proposed method, we demonstrate that the song syntaxes of the Bengalese finch can be represented as reversible automata with lower k-reversibility and that juvenile song syntaxes have two types of development. Our approach provides an effective way to understand the vocal learning of songbirds in terms of computational learning.
研究論文(国際会議プロシーディングス), 英語 - 物理的実現可能性に優れた量子探索アルゴリズム
大久保誠也; 西野哲朗; 太田和夫; 國廣昇
情報処理学会論文誌, 46巻, 6号, 掲載ページ 1416-1425, 出版日 2005年, 査読付
研究論文(学術雑誌), 日本語 - Bulk量子計算モデル上におけるGroverのアルゴリズムの繰り返し回数について
大久保誠也; 西野哲朗; 太田和夫; 國廣昇
情報処理学会論文誌:数理モデル化と応用, 46巻, SIG17(TOM13)号, 出版日 2005年, 査読付
研究論文(学術雑誌), 日本語 - A Quantum Algorithm for Finding the Minimum on NMR Quantum Computers
Seiya Okubo; Tetsuro Nishino; Kazuo Ohta; Noboru Kunihiro
ERATO Workshop on Quantum Information Science 2004, 掲載ページ ?, 出版日 2004年, 査読付
研究論文(国際会議プロシーディングス), 英語 - A quantum algorithm using NMR computers to break secret-key cryptosystems
K Ohta; T Nishino; S Okubo; N Kunihiro
NEW GENERATION COMPUTING, SPRINGER-VERLAG, 21巻, 4号, 掲載ページ 347-361, 出版日 2003年, 査読付, In this paper, we discuss quantum algorithms that, for a given plaintext m(O) and a given ciphertext c(O), will find a secret key, k(O), satisfying c(O) = E(k(O), m(O)), where an encryption algorithm, E, is publicly available. We propose a new algorithm suitable for an NMR (Nuclear Magnetic Resonance) computer based on the technique used to solve the counting problem. The complexity of our algorithm decreases as the measurement accuracy of the NMR computer increases. We discuss the possibility that the proposed algorithm is superior to Grover's algorithm based on initial experimental results.
研究論文(学術雑誌), 英語 - The study on quantum algorithm using NMR computers for code breaking of secret key cryptosystems
Kazuo Ohta; Tetsuro Nishino; Seiya Okubo
ERATO Workshop on Quantum Information Science 2002, 掲載ページ 54-55, 出版日 2002年09月, 査読付
研究論文(国際会議プロシーディングス), 英語 - A mathematical theory of NMR quantum computations
T Nishino
ENABLING SOCIETY WITH INFORMATION TECHNOLOGY, SPRINGER-VERLAG TOKYO, 掲載ページ 340-347, 出版日 2002年, 査読付, In this paper, we develop a theory of bulk quantum computations such as NMR (Nuclear Magnetic Resonance) quantum computations, For this purpose, we first define bulk quantum Turing machines (BQTMs for short) as a model of bulk quantum computation. Then, we define complexity classes EBQP, BBQP and ZBQP as counterparts of the quantum complexity classes EQP, BQP and ZQP, respectively, and show that EBQP=EQP, BBQP=BQP, and ZBQP=ZQP. This implies that BQTMs are polynomially related to ordinary QTMs as long as they are used to solve decision problems. We also show that these two types of QTMs are also polynomially related when they solve a function problem which has a unique solution. Furthermore, we show that BQTMs can solve certain instances of NP-complete problems efficiently.
研究論文(国際会議プロシーディングス), 英語 - 制限された離散的拡張単純回帰ネットワークと実時間 DPDA の等価性
守谷純之介; 西野哲朗
電子情報通信学会論文誌 D-I, J85-D-I巻, 2号, 掲載ページ 160-167, 出版日 2002年, 査読付
日本語 - Mathematical models of quantum computation
T Nishino
NEW GENERATION COMPUTING, SPRINGER-VERLAG, 20巻, 4号, 掲載ページ 317-337, 出版日 2002年, 査読付, In this paper, we introduce two mathematical models of realistic quantum computation. First, we develop a theory of bulk quantum computation such as NMR (Nuclear Magnetic Resonance) quantum computation. For this purpose, we define bulk quantum Turing machine (BQTM for short) as a model of bulk quantum computation. Then, we define complexity classes EBQP, BBQP and ZBQP as counterparts of the quantum complexity classes EQP, BQP and ZQP, respectively, and show that EBQP=EQP, BBQP=BQP and ZBQP=ZQP. This implies that BQTMs are polynomially related to ordinary QTMs as long as they are used to solve decision problems. We also show that these two types of QTMs are also polynomially related when they solve a function problem which has a unique solution. Furthermore, we show that BQTMs can solve certain instances of NP-complete problems efficiently.
On the other hand, in the theory of quantum computation, only feed-forward quantum circuits are investigated, because a quantum circuit represents a sequence of applications of time evolution operators. But, if a quantum computer is a physical device where the gates are interactions controlled by a current computer such as laser pulses on trapped ions, NMR and most implementation proposals, it is natural to describe quantum circuits as ones that have feedback loops if we want to visualize the total amount of the necessary hardware. For this purpose, we introduce a quantum recurrent circuit model, which is a quantum circuit with feedback loops. Let C be a quantum recurrent circuit which solves the satisfiability problem for a blackbox Boolean function including n variables with probability at least 1/2. And let s be the size of C (i.e. the number of the gates in C) and t be the number of iterations that is needed for C to solve the satisfiability problem. Then, we show that, for those quantum recurrent circuits, the minimum value of max(s, t) is O(n(2)2(n/3)).
研究論文(学術雑誌), 英語 - 効率的量子アルゴリズムの設計手法
西野哲朗
情報処理学会論文誌:数理モデル化と応用, 43巻, SIG7(TOM6)号, 掲載ページ 1-9, 出版日 2002年, 査読付
研究論文(学術雑誌), 日本語 - NMR 量子計算による NP 完全問題と因数分解の解法
渥美賢嗣; 西野哲朗
情報処理学会論文誌:数理モデル化と応用, 一般社団法人情報処理学会, 43巻, SIG7(TOM6)号, 掲載ページ 10-18, 出版日 2002年, 査読付, 1985年にDavid Deutschは,量子並列計算を実行できるuring機械として,量子uring機械(QTMと略す)を導入した.そして,1994年にPeter Shorが,QTMは任意に小さな誤り確率で,整数を多項式時間内に因数分解できることを示した.決定性uring機械は,整数を多項式時間内には因数分解できないと広く信じられているので,QTMは本質的に新しい計算モデルである可能性が高い.一方,多くの研究者が,QTMに基づく量子コンピュータを物理的に実現する方法について研究を進めている.なかでもNMR(核磁気共鳴)は,いくつかの理由から,量子コンピュータの実現方法として有望と考えられている.しかし,NMR上で実行される量子計算は,QTM上で実行される量子計算とは若干異なっている.たとえば,Shorの因数分解アルゴリズムは,そのままではNMR量子コンピュータ上では実行できない.本論では,最初にNMR 量子計算のモデルとして,Bulk量子uring機械(BQTMと略す)を定義する.そして,BQTMはNP完全問題のある種のインスタンスを効率良く解くことができ,また,整数を多項式時間内に因数分解できることを示す.In 1985, David Deutsch introduced quantum uring machines (QTMs for short)as Turing machines which can perform so called quantum parallel computations. Then, in 1994, Peter Shor showed that QTM can factor integers with arbitrary small error probability in polynomial time. Since it is widely believed that any deterministic uring machines cannot factor integers in polynomial time, it is very likely that QTM is an essentially new model of computation. On the other hand, many researchers are studying how to physically implement quantum computers based on QTM. Among others, NMR (Nuclear Magnetic Resonance) offers an appealing prospect for implementation of quantum computers because of a number of reasons. But, quantum computations performed on NMR is slightly different from those performed on QTMs. For example, Shor 's factoring algorithm cannot be executed on an NMR quantum computer as it is. In this paper, we first define bulk quantum Turing machine (BQTM for short)as a model of the NMR quantum computation. Then, we show that BQTMs can solve certain instances of NP-complete problems efficiently, and can factor integers in polynomial time.
日本語 - Mathematical Theories of Quantum Computations
西野哲朗
Fourth Annual Symposium on Japanese-American Frontiers of Science (JAFoS), October 10-12, 2001, Tokyo, Japan (日本の JST と米国の NAS が主催)における招待講演, 出版日 2001年10月
英語 - Quantum Recurrent Networks
西野哲朗
Workshop on ERATO Quantum Information Science (EQIS) 2001, September 6-8, 2001, Tokyo Japan における招待講演, 出版日 2001年09月
英語 - Relationships between the computational capabilities of simple recurrent networks and finite automata
J Moriya; T Nishino
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E84A巻, 5号, 掲載ページ 1184-1194, 出版日 2001年05月, 査読付, In the filed of cognitive psychology, simple recurrent networks are used for modeling the natural language processing in the human brain. For example, Elman experimentally showed that the simple recurrent networks can predict the rightmost word in sentential forms of a particular grammar which can generate compound sentences with high probability. Concerning these results, it is natural to ask whether the computational capability of the simple recurrent networks is sufficient to recognize natural languages. In this paper, we assume that the range of ct function computed at each gate of a simple recurrent network is a finite set. This is a quite realistic assumption, because we cannot physically implement a gate whose range is an infinite set. Then, we define equivalence relations between simple recurrent networks and Mealy machines or Moore machines, which are finite automata with output. Then. under our assumption, we show (1) a construction of a Mealy machine which simulates a given simple recurrent network, and (2) a construction of a simple recurrent network which simulates a given Moore machine. From these two constructions, we can conclude that the computational capability of the simple recurrent networks is equal to that of finite automata with output under our assumption.
研究論文(学術雑誌), 英語 - 量子計算量理論
西野哲朗
電子情報通信学会論文誌 D-I, 一般社団法人電子情報通信学会, J84-D-I巻, 1号, 掲載ページ 3-17, 出版日 2001年, 本論文では, 量子計算量理論の主要結果について概観する.最初に, 量子Turing機械の定義を述べ, 次に, 効率の良い万能量子Turing機械の構成法を示す.そのために, 接続, 分岐, 繰返しのような量子Turing機械の構成における基本操作の実行方法を示し, 更に, 計算基底の変換や, ユニタリ変換の実行といった, 量子力学的な基本操作も導入する.また, 量子Turing機械で, 誤り確率限定多項式時間で決定できる言語のクラスBQPは, BPP⊂__=BQP⊂__=PSPACEという関係を満たすことを示す.更に, 量子計算量理論における最近の研究の流れを概観する.通常の量子計算量は, 量子Turing機械上で計算に要するステップ数などに基づいて定義されるが, 最近では, 量子回路計算量, 量子質問量, 量子通信量といった計算量尺度を用いて, 量子計算量の研究が盛んに行われている.そこで, まず, これらの計算量尺度の定義を紹介し, 次に, これら尺度の相互関係, 及び, 定理の証明において用いられる手法について概観する.また, 最近注目を集めているNMR量子計算の理論についても紹介する.
研究論文(学術雑誌), 日本語 - 実時間決定性PDAと等価な拡張単純回帰ネットワークについて
守谷純之介; 西野哲朗
電子情報通信学会コンピュテーション研究会資料,COMP2000-75, 掲載ページ 17-24, 出版日 2001年
日本語 - A characterization of k-th powers Pn,k of paths in terms of k-trees
Koich Yamazaki; Sei'Ichi Tani; Tetsuro Nishino
International Journal of Foundations of Computer Science, 12巻, 4号, 掲載ページ 435-443, 出版日 2001年, 査読付, Let G be a k-tree such that |{v V(G): degG(v) = k}| = 2, n = |V(G)| ≥ 2k + 2, and the maximum degree of G is at most 2k. In this paper, we will show that such a k-tree G is isomorphic to Pn,k. In this way, we give a new characterization of k-th power (i.e. Pn,k) of paths with n vertices in terms of k-trees. © 2001 World Scientific Publishing Company.
研究論文(学術雑誌), 英語 - ニューロイダルネットの計算能力について
西野哲朗
電子情報通信学会論文誌 D-I, J83-D-I巻, 1号, 掲載ページ 36-44, 出版日 2000年
研究論文(学術雑誌), 日本語 - NMR量子計算を用いた因数分解アルゴリズム
渥美賢嗣; 西野哲朗
電子情報通信学会コンピュテーション研究会試料,COMP99-96, 掲載ページ 135-142, 出版日 2000年, 査読付
日本語 - NMR量子計算による数え上げ問題の解法
芝田 浩; 西野哲朗
電子情報通信学会コンピュテーション研究会試料,COMP99-97, 掲載ページ 143-150, 出版日 2000年
日本語 - NMR量子計算の初期設定法について
志摩孝夫; 西野哲朗
電子情報通信学会コンピュテーション研究会試料,COMP99-98, 掲載ページ 151-158, 出版日 2000年
日本語 - Quantum Computation and NP-Complete Problems
Tetsuro Nishino
In: T. Hida and K. Saito(Eds.),Quantum Information, World Scientific, World Scientific, 掲載ページ 125-134, 出版日 2000年, 査読付
研究論文(その他学術会議資料等), 英語 - NMR 量子計算の理論
西野哲朗
量子情報技術研究会資料,QIT2000-3, 出版日 2000年
日本語 - グラフの同型性判定問題に対する量子アルゴリズムの設計に関する研究
伊藤邦明; 西野哲朗
量子情報技術研究会資料,QIT2000-46, 掲載ページ 119-124, 出版日 2000年
日本語 - 連想記憶とプライミング現象に対する回路モデル
長吉亮拓; 築地賢一; 西野哲朗
2000年度人工知能学会全国大会(第14回)論文集, 掲載ページ 483-487, 出版日 2000年
日本語 - ニューロイダルネット上における屈折のモデル化
大坪一紀; 木下暁央; 西野哲朗
2000年度人工知能学会全国大会(第14回)論文集, 掲載ページ 494-497, 出版日 2000年
日本語 - ニューロイダルネット上における最適性理論のモデル化
伊藤太一; 西野哲朗
2000年度人工知能学会全国大会(第14回)論文集, 掲載ページ 498-501, 出版日 2000年
日本語 - 量子コンピュータ/量子計算
西野哲朗
Computer Today, 1999年1月号号, 掲載ページ 14-18, 出版日 1999年01月
日本語 - On the Computational Power of Bounded Error Quantum Turing Machines
T. Nishino
T. Hida and K. Sait(]E86CC[)(Eds.), Quantum Information, World Scientific, World Scientific, 掲載ページ 125-131, 出版日 1999年
英語 - NMR量子計算の理論
西野哲朗
1999年電子情報通信学会総合大会講演論文集(シンポジウム講演),SA-5-4, 掲載ページ 466-467, 出版日 1999年
日本語 - 非線形量子計算の時間量について
金田直樹; 西野哲朗
1999年電子情報通信学会総合大会講演論文集(シンポジウム講演),SA-5-6, 掲載ページ 479-471, 出版日 1999年
日本語 - ニューロイダルネット上における順序情報の生成と学習
辻倉正徳; 田中 繁; 西野哲朗
ニューロコンピューティング研究会試料,NC98-132, 掲載ページ 265-272, 出版日 1999年
日本語 - 効率的量子アルゴリズムの設計について
西野哲朗; 與語一真
人工知能基礎論研究会試料,SIG-FAI-9804, 掲載ページ 103-108, 出版日 1999年
日本語 - ニューロイダルネット上における語彙獲得のモデル化
木下暁央; 西野哲朗
1999年度人工知能学会全国大会(第13回)論文集, 掲載ページ 332-335, 出版日 1999年
日本語 - 最短ベクトル探索問題の効率的量子アルゴリズムの設計について
西野哲朗; 與語一真
量子情報技術研究会試料,QIT99-2, 掲載ページ 7-12, 出版日 1999年
日本語 - ネバンリンナ受賞者紹介P. Shor氏の業績
西野哲朗
数学, 51巻, 2号, 掲載ページ 80-82, 出版日 1999年
日本語 - 量子計算論-Shorのアルゴリズムの意義-
西野哲朗
数理科学, 1998年10月号号, 掲載ページ 21-28, 出版日 1998年10月
日本語 - On the complexity of negation-limited Boolean networks
R Beals; T Nishino; K Tanaka
SIAM JOURNAL ON COMPUTING, SIAM PUBLICATIONS, 27巻, 5号, 掲載ページ 1334-1347, 出版日 1998年10月, A theorem of Markov precisely determines the number r of NEGATION gates necessary and sufficient to compute a system of boolean functions F. For a system of boolean functions on n variables, r less than or equal to b(n) = [log(2)(n + 1)]. We call a circuit using b(n) NEGATION gates negation-limited. We continue recent investigations into negation-limited circuit complexity, giving both upper and lower bounds.
A circuit with inputs x(1),..., x(n) and outputs -x(1),..., -x(n) is called an inverter, for which r = [log(2)(n + 1)]. Fischer has constructed negation-limited inverters of size O(n(2)log n) and depth O(log n). Recently, Tanaka and Nishino have reduced the circuit size to O(n log n) at the expense of increasing the depth to log(2)n. We construct negation-limited inverters of size O(n log n), with depth only O(log n), and we conjecture that this is optimal. We also improve a technique of Valiant for constructing monotone circuits for slice functions (introduced by Berkowitz).
Next, we introduce some lower bound techniques for negation-limited circuits. We provide a 5n + 3 log(n + 1) - c lower bound for the size of a negation-limited inverter. In addition, we show that for two different restricted classes of circuit, negation-limited inverters require superlinear size.
研究論文(学術雑誌), 英語 - 因数分解に関する量子アルゴリズムのシミュレーション
渥美賢嗣; 西野哲朗
電子情報通信学会論文誌A, 一般社団法人電子情報通信学会, J81-A巻, 12号, 掲載ページ 1670-1677, 出版日 1998年, 1994年にShorは, 自然数Nの因数分解を行うために, 任意のχmodNのオーダを多項式時間内の求める量子アルゴリズムを示した[3].しかし, 現在多数の量子ビットをもつ量子コンピュータは存在しないため, そのアルゴリズムが実際のどのような計算結果を出力するかを知る方法がない.このような状況においては, 既存の計算機を用いて, Shorの量子アルゴリズムをシミュレーションし, その振舞いや性質を考察することの意義は大きい.本研究ではShorの因数分解に対する量子アルゴリズムを, パーソナルコンピュータ上でシミュレーションすることにより, Shorのアルゴリズムの振舞いや種々の性質を明らかにする.
研究論文(学術雑誌), 日本語 - ニューロイダルネット上におけるPinkerの言語獲得理論のモデル化
平尾孝史; 木下暁央; 西野哲朗
1998年度人工知能学会全国大会(第12回)論文集, 掲載ページ 396-399, 出版日 1998年
日本語 - 単純回帰ネットワークを模倣するMealy機械の構成法
守谷純之介; 西野哲朗
電子情報通信学会コンピュテーション研究会資料,COMP98-27, 一般社団法人電子情報通信学会, 98巻, 186号, 掲載ページ 51-58, 出版日 1998年, Elmanは, 単純回帰ネットワーク(Simple Recurrent Network)が有限オートマトンを模倣できることを実験的に示た.さらに, 単純回帰ネットワークが, 特定の文脈自由文法から生成された単語列に基づく学習課程を経ることにより, その文法の文形式内の右端の単語を高い確率で予測できることを示した.ところが, 逆に, 有限オートマトンが単純回帰ネットワークを模倣できるか否かは知られていなかった.本論では, まず, 単純回帰ネットワークに対する数学的定義を行い, 単純回帰ネットワークが出力付き有限オートマトンであるMealy機械によって模倣可能であることを構成的に示す.
日本語 - ニューロイダルネットとコネクショニズム-「脳を創る」ための計算機科学からのアプローチ-
西野哲朗
京都大学数理解析研究所講究録,1054, 京都大学, 1054巻, 掲載ページ 1-10, 出版日 1998年
日本語 - 量子計算の理論
西野哲朗
日本物理学会講演概要集,1998年秋の分科会, 53巻, 2号, 掲載ページ 437, 出版日 1998年
日本語 - NP完全問題に対する非線形量子アルゴリズムの線形領域シミュレーション
金田直樹; 西野哲朗
電子情報通信学会コンピュテーション研究会資料,COMP98-41, 掲載ページ 25-32, 出版日 1998年
日本語 - NMR量子計算による関数問題とNP完全問題の解法について
西野哲朗; 芝田 浩; 渥美賢嗣; 志摩孝夫
電子情報通信学会コンピュテーション研究会資料,COMP98-71, 一般社団法人電子情報通信学会, 98巻, 442号, 掲載ページ 65-72, 出版日 1998年, 本論では、NMR(核磁気共鳴)量子計算の理論を導入する。まず最初に、NMR量子計算のモデルとして、bulk量子Turing機械(BQTMと略記する)を定義する。そして、量子計算クラスEQP, BQP, ZBQPに対応するNMR量子計算量のクラスとして、EBQP, BBQP, ZBQPをそれぞれ導入し、EBQP=EQP, BBQP=BQP, ZBQP=ZQPが成立することを示す。この結果は、BQTMが、判定問題を解く場合には、通常のQTMと多項式時間同級であることを示す。さらに、これらの2つのタイプのQTMは、解を1つしか持たない関数問題を解く場合にも、多項式時間同級となることを示す。最後に、BQTMはNP完全問題のある種のインスタンスを効率良く解けることを示す。
日本語 - 量子コンピュータ
三原孝志; 西野哲朗
日本ファジィ学会誌, 10巻, 1号, 掲載ページ 11-20, 出版日 1998年
日本語 - ニューロイダルネットによる脳機能のシミュレーション
西野哲朗
日本の科学者, 33巻, 6号, 掲載ページ 20-24, 出版日 1998年
日本語 - 量子計算論
西野哲朗
情報処理, 39巻, 6号, 掲載ページ 592-595, 出版日 1998年
日本語 - The complexity of threshold circuits for parity functions
SC Sung; T Nishino
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E80D巻, 1号, 掲載ページ 91-93, 出版日 1997年01月, In this paper, we show that a parity function with n variables can be computed by a threshold circuit of depth O((log n)/c) and size O((2(c) log n)/c), for all 1 less than or equal to c less than or equal to [log(n + 1)] - 1. From this construction, we obtain an O(log n/log log n) upper bound for the depth of polylogarithmic size threshold circuits for parity functions. By using the result of Impagliazzo, Paturi and Saks [5], we also show an Omega(log n/log log n) lower bound for the depth of the threshold circuits. This is an answer ot the open question posed in [11].
研究論文(学術雑誌), 英語 - Negation-limited circuit complexity of symmetric functions
K Tanaka; T Nishino; R Beals
INFORMATION PROCESSING LETTERS, ELSEVIER SCIENCE BV, 59巻, 5号, 掲載ページ 273-279, 出版日 1996年09月, A theorem of Markov precisely determines the number r(F) of NEGATION gates necessary and sufficient to compute a system of boolean functions F. For a system of boolean functions on n variables, r(F) less than or equal to inverted right perpedicular log(n + 1) inverted left perpendicular. We call a circuit using the minimum number of NEGATION gates negation-limited. Continuing recent research on negation-limited circuit complexity, we investigate the complexity of negation-limited circuits which compute symmetric functions. First, we shall prove a main technical lemma on functions computed at NEGATION gates in negation-limited circuits computing symmetric functions, Using this lemma, we show a number of lower bounds on the size and depth of negation-limited circuits computing several symmetric functions such as PARITY(n), PARITY(n), MOD(n)(k) and others, For example, a 4n + 3 log(2)(n + 1) - c lower bound is given on the size of circuits computing the PARITY(n) function using r(PARITY(n)) = inverted right perpendicular log(2)(n+ 1) - 1 inverted left perpendicular NEGATION gates. Furthermore, we show nonlinear lower bounds on the size of certain kinds of negation-limited circuits computing symmetric functions.
研究論文(学術雑誌), 英語 - A relationship between the number of negations and the circuit size
K Tanaka; T Nishino
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, IEICE-INST ELECTRON INFO COMMUN ENG, E79D巻, 9号, 掲載ページ 1355-1357, 出版日 1996年09月, We show a relationship between the number of negations In circuits and the size of circuits. More precisely, we construct a Boolean Function H-n, ana show that there exists an integer i, which can range over only two different values, such that the removal of one NEGATION gate causes an exponential growth of the optimal circuit size for H-n.
研究論文(学術雑誌), 英語 - Recognition of Devanagari characters using neural networks
K Keeni; H Shimodaira; T Nishino; Y Tan
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, IEICE-INST ELECTRON INFO COMMUN ENG, E79D巻, 5号, 掲載ページ 523-528, 出版日 1996年05月, Devanagari is the most widely used script in India. Here, a method is introduced for recognizing Devanagari characters using Neural network. The proposed method reduces the number of output unit necessary for a conventional neural network where the classification is based on a winner take all basis. An automatic coding procedure for representing the output layer of the network and a different method for the final classification is also proposed. Along with the automatic coding procedure, a heuristic method for representing the output units by exploiting the structural information of Devanagari character is also demonstrated. Besides, it has been shown by random representation of the output layer that the representation effects the generalization/performance of the network. The proposed automatic representation gave the recognition rate of 98.09% for 44 categories.
研究論文(学術雑誌), 英語 - ON THE NEGATION-LIMITED CIRCUIT COMPLEXITY OF CLIQUE FUNCTIONS
T NISHINO; K TANAKA
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, IEICE-INST ELECTRON INFO COMMUN ENG, E78D巻, 1号, 掲載ページ 86-89, 出版日 1995年01月, A negation-limited circuit is a combinational circuit which includes at most inverted left perpendicularlog(n + 1)inverted right perpendicular NOT gates. We show a relationship between the size of negation-limited circuits computing clique functions and the number of NOT gates in the circuits.
研究論文(学術雑誌), 英語 - ON THE NUMBER OF NEGATIONS NEEDED TO COMPUTE PARITY FUNCTIONS
T NISHINO; J RADHAKRISHNAN
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, IEICE-INST ELECTRON INFO COMMUN ENG, E78D巻, 1号, 掲載ページ 90-91, 出版日 1995年01月, We exactly determine the number of negations needed to compute the parity functions and the complement of the parity functions. We show that with k NOT gates, parity can be computed on at most 2k+1 - 1 variables, and parity complement on at most 2k+1 - 2 variables. The two bounds are shown to be tight.
研究論文(学術雑誌), 英語 - More on the Complexity of Negation-Limited Circuits
BEALS R.
Proceedings of the 27th ACM Symposium on Theory of Computing, Las Vegas, NV, May 29-June 1, 掲載ページ 585-595, 出版日 1995年
英語 - On the complexity of negation-limited boolean networks (Preliminary version)
Keisuke Tanaka; Tetsuro Nishino
Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 129502巻, 掲載ページ 38-47, 出版日 1994年05月23日, A negation-limited circuit is a combinational circuit which includes at most log(n + 1) NOT gates. In this paper, we investigate the complexity of negation-limited circuits. We first study the complexity of inverters as a foundation of negation-limited circuit complexity. For the size of negation-limited inverters, we give a new 0(n(logn)2) upper bound as well as a 5n+31og(n+l)-6 lower bound. Furthermore, we show two superlinear lower bounds 011 the size of certain kinds of negation- limited inverters. Finally, we investigate the negation- limited circuit complexity of Boolean functions, and present (1) several general theorems on the relationship between combinational complexity and negation- limited complexity, (2) new upper bounds on the size of negation-limited circuits for symmetric functions including exactly-k-functions, and (3) a relationship between the circuit size and the number of NOT gates for the case of clique functions.
研究論文(国際会議プロシーディングス), 英語 - The Emptiness Problem for Lexical-Functional Grammars is Undecidable
Tetsuro Nishino
IEICE Transactions on Information and Systems, E77-D巻, 6号, 掲載ページ 720-722, 出版日 1994年
研究論文(学術雑誌), 英語 - A Simulation Result for Simultaneously Bounded AuxPDAs
IEICE Transactions on Information and Systems, E77-D巻, 5号, 掲載ページ 597-600, 出版日 1994年
英語 - RELATING ATTRIBUTE GRAMMARS AND LEXICAL-FUNCTIONAL GRAMMARS
T NISHINO
INFORMATION SCIENCES, ELSEVIER SCIENCE INC, 66巻, 1-2号, 掲載ページ 1-22, 出版日 1992年12月, In this paper, some similarities between attribute grammars (AGs) and lexical-functional grammars (LFGs) are shown from computational theoretic points of view. First we introduce two types of LFGs that are called restricted LFGs (RLFGs) and polynomial LFGs. Then we characterize these LFGs as string-valued AGs (SAGs) or strongly polynomial AGs (SPAGs). To be precise, it is shown that (1) a set of f-descriptions of an RLFG can be characterized as an output set of an SAG, and (2) a language generated by a polynomial RLFG can be characterized as a language generated by an SPAG. Using these characterizations, we estimate the complexity of languages generated by these LFGs.
研究論文(学術雑誌), 英語 - 木構造図式の描画問題
海野浩; 安斎公士; 小倉耕一; 西野哲朗; 中西美智子; 夜久竹夫
情報処理学会論文誌, 一般社団法人情報処理学会, 33巻, 7号, 掲載ページ 879-886, 出版日 1992年, 木構造図式は各頂点が次の四つの属性を持った属性付き木である:すなわち属性は(1)頂点の幅 (2)頂点の深さ,(3)頂点の水平座標と (4)頂点の垂直座標である木構造図式を与えられた美的条件を満たすように配置する問題は"美的描画問題"といわれる.木構造図式に対する プログラム図式を指向した美的条件は 木に対する美的条件を変形することによリ定式化された.その美的条件を満たす配置を与える手法も提案された.本論文でわれわれははじめに,従来の美的条件を満たす配置を与える手法定形式化しO(n^3)時間アルゴリズムを詳細に定める次に上の美的条件に条件をひとつおきかえて新たな美的条件を考えると われわれのアルゴリズムが新たな美的条件を満たす最も狭い配置を与えることを示すその結果美的条件と計算量に関する新たな関係を得る
研究論文(学術雑誌), 日本語 - Mathematical Analysis of Lexical - Functional Grammars - Complexity, Parsability and Learnability -
Tetsuro Nishino
Language Research, 27巻, 1号, 掲載ページ 119-141, 出版日 1991年
研究論文(学術雑誌), 英語 - Attribute Graph Grammars with Applications to Hichart Program Chart Editors
Tetsuro Nishino
Advances in Software Science and Technology, 1巻, 1号, 掲載ページ 89-104, 出版日 1989年
研究論文(学術雑誌), 英語 - CRITAC - AN EXPERIMENTAL SYSTEM FOR JAPANESE TEXT PROOFREADING
K TAKEDA; E SUZUKI; T NISHINO; T FUJISAKI
IBM JOURNAL OF RESEARCH AND DEVELOPMENT, IBM CORP, 32巻, 2号, 掲載ページ 201-216, 出版日 1988年03月
研究論文(学術雑誌), 英語 - 漢字複合語の確率的構造解析
西野哲朗; 藤崎哲之助
情報処理学会論文誌, 29巻, 11号, 掲載ページ 1034-1042, 出版日 1988年
研究論文(学術雑誌), 英語 - Attribute Grammars and Lexical-Functional Grammars
Proceedings of International Computer Science Conference'88, Hong Kong., 掲載ページ 426-433, 出版日 1988年
英語 - The Intrinsically Exponential Complexity of the k-visit Property Problem for Attribute Grammars
NISHINO T.
Topology and Computer Science (Kinokuniya), Kinokuniya, 掲載ページ 473-486, 出版日 1987年
英語
MISC
- 最大クリーク問題の多項式時間的可解性の拡張の更なる改良
中西 裕陽; 富田 悦次; 若月 光夫; 西野 哲朗
NP 完全である最大クリーク問題に対し,"節点数 n≧1 のグラフにおいて,グラフ中の任意の隣接 2 節点 vi,vj∈V, (vi,vj)∈E が min{deg(vi), deg(vj)}≦3.486d lg n (d ≧0: 定数) を満たすならば,最大クリーク問題は O(n2+max{d,1}) 時間で解決可能である." ことを示す.これは,先に発表した結果 (信学論 (D),vol.J97-D,no.6,June 2014) の定量的改良である.This paper presents a further improved extended result for polynomial-time solvability of the maximum clique problem, that is: for any adjacent pair of vertices p and q where the degree of p is less than or equal to that of q in a graph with n vertices, if the degree of p is less than or equal to 3.486d lg n (d≧0: a constant), then the maximum clique problem is solvable in the polynomial time of O(n2+max{d,1}). This result is obtained by more detailed analysis and the corresponding detailed algorithm., 一般社団法人情報処理学会, 出版日 2014年06月06日, 研究報告アルゴリズム(AL), 2014巻, 14号, 掲載ページ 1-8, 日本語, 0913-5685, 110009785574, AN1009593X - 最大クリーク問題の多項式時間的可解性の拡張の更なる改良
中西 裕陽; 富田 悦次; 若月 光夫; 西野 哲朗
NP完全である最大クリーク問題に対し,"節点数n≧1のグラフにおいて,グラフ中の任意の隣接2節点v_i,v_j∈V,(v_i,v_j)∈Eがmin{deg(v_i),deg(v_j)}≦3.486dlgn(d≧0:定数)を満たすならば,最大クリーク問題はO(n^<2+max{d,1}>)時間で解決可能である."ことを示す.これは,先に発表した結果(信学論(D), vol.J97-D, no.6, June 2014)の定量的改良である., 一般社団法人電子情報通信学会, 出版日 2014年06月06日, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 114巻, 80号, 掲載ページ 85-92, 日本語, 110009925280, AN10013152 - 格助詞によるクラスタリングを用いた分布類似度計算の高速化
中山 光樹; 山田 節夫; 西野 哲朗
本論文では,分布類似度計算の前処理として,文脈中に含まれる情報を用いて単語のクラスタリングを行うことで,分布類似度の計算を高速化する手法を提案する.格助詞と動詞を組とした文脈に対して,格助詞の種類に応じてクラスタを構築し,構築したクラスタ内で分布類似度の計算を行う.コーパスを用いて,実験と人手による評価実験を行うことで,従来手法と比べて精度が同等で高速であることを示す.This paper proposes an efficient method for distributional similarity calculation by using case particle's clusters. The proposed method constructs clusters according to the case particles in the context before calculating distributional similarity. Experimental results show that the proposed method is more efficient than the existing method with almost same quality., 一般社団法人情報処理学会, 出版日 2013年09月19日, 研究報告数理モデル化と問題解決(MPS), 2013巻, 14号, 掲載ページ 1-6, 日本語, 0913-5685, 110009606414, AN10505667 - 大貧民プログラムのn-gram統計による特徴抽出とクラスタ分析
綾部孝樹; 大久保誠也; 西野哲朗
本論では,人気の高い不完全情報カードゲームである大貧民をプレイするプログラムの特徴を明らかにする.はじめに,n-gram統計を用いた特徴量の抽出法,ならびに得られた特徴量を用いたクラスタ分析法を提案する.次に,いくつかの実験により,その提案手法が大貧民プログラムを,高い確率で正しくクラスタリングできる事を示す., 一般社団法人情報処理学会, 出版日 2013年05月16日, 研究報告数理モデル化と問題解決(MPS), 2013巻, 2号, 掲載ページ 1-6, 日本語, 0919-6072, 110009579808, AN10505667 - 学習ゲームを用いた発達障害児向け文字学習支援システム
金山 貴泰; 浅野 久美子; 西野 哲朗; 若月 光夫
発達障害児教育においては,児童の学習に関する動機の喚起・維持が困難な場合が多い.この問題を解決するために,近年,発達障害児教育の現場において,ICT(情報通信技術)を用いた教育支援システムの活用が注目されている.本研究では,発達障害児の興味を引くように,学習ゲームの仕組みを取り入れた,文字学習支援システム『おとかな!』を開発した.その際,教員とのディスカッションを通して,本システムに難易度設定,問題設定,学習記録の自動化といった機能も組み込んだ.本システムの有効性を検証するために,開発したシステムを特別支援学校の授業で実際に使用した.その結果,本システムは,発達障害児の興味を引き出し,学習への集中時間を増加させる効果があることがわかった.さらに,ICT教材の機能を活用することで,教材の準備にかかる教員の負担を大幅に軽減できることもわかった.In this study, we developed a learning support system for children with physical or mental disabilities. In order to reduce the burden of supervisors in education of these children. Educating these children is a burden for teachers. Because these children difficult to maintain the motivation for learning Therefore we developed this system to apply learning game for pull these child's interest. Through discussions with teachers, I incorporated the function difficulty settings, question setting, and automatic recording. In order to verify the validity of this system, it experimented in the special support school. As a result, this system which pull these child's interest and concentration time was increased. Furthermore, it turned out that the burden placed on preparation of teaching materials is mitigable by employing the feature of ICT teaching materials efficiently., 一般社団法人情報処理学会, 出版日 2013年05月16日, 研究報告数理モデル化と問題解決(MPS), 2013巻, 8号, 掲載ページ 1-6, 日本語, 0919-6072, 110009579814, AN10505667 - 大貧民における偶然手番感度
西野順二; 西野哲朗
大貧民プレイヤプログラムなど不完全情報ゲームでは他プレイヤの手の情報を推定することが重要と考えられるが,局面によっては推定の必用が無い場合もある.本稿では不完全情報ゲームの性質を計る指標として偶然手番感度を提案し,これを用いて多人数不完全情報ゲームの大貧民の特性を調べることを目的とする.偶然手番感度は,相手手札の可能性を決める偶然手番がある場面での着手の利得に与える影響度であり,情報集合に含まれる局面可能性による利得の振れ幅を数値化したものである.大貧民を縮小した単貧民について,2人から5人に2から5枚を配布し合計12枚の全ての配布パターンについてその完全探索結果から,相手手札の可能性に対して最適着手は変わらず,偶然手番感度が低いことを示した.53枚5人プレイヤにおいても,モンテカルロシミュレーションによる推定利得から偶然手番感度を求める実験によってやはり偶然手番感度が低いことを示した., 出版日 2013年02月25日, 研究報告ゲーム情報学(GI), 2013巻, 5号, 掲載ページ 1-8, 日本語, 110009550129, AA11362144 - Automatic Generation of Diagram Explanation based on an Attribute Graph Grammar
Takaaki Goto; Tetsuro Nishino; Kensei Tsuchida
Unified Modeling Language (UML) has already been used in the analysis, design, and implementation of many systems. Open Source Software (OSS) is often used in software development. However, it is often the case that OSS does not contain adequate documents, so the generation of software documents is important. Documents with diagrams are especially important to understand software, so it is important to generate documents with diagrams. In order to process large-scale diagrams, or many source codes automatically, formal and declarative representation is needed. In this paper, we propose automatic generation of documentation based on an attribute graph grammar.Unified Modeling Language (UML) has already been used in the analysis, design, and implementation of many systems. Open Source Software (OSS) is often used in software development. However, it is often the case that OSS does not contain adequate documents, so the generation of software documents is important. Documents with diagrams are especially important to understand software, so it is important to generate documents with diagrams. In order to process large-scale diagrams, or many source codes automatically, formal and declarative representation is needed. In this paper, we propose automatic generation of documentation based on an attribute graph grammar., 出版日 2012年07月09日, 研究報告数理モデル化と問題解決(MPS), 2012巻, 9号, 掲載ページ 1-6, 英語, 110009421225, AN10505667 - コンピュータ大貧民に対する差分学習法の応用
小沼啓; 本多武尊; 保木邦仁; 西野哲朗
出版日 2012年04月15日, 情報処理学会研究報告(CD-ROM), 2011巻, 6号, 掲載ページ ROMBUNNO.GI-27,NO.1, 日本語, 2186-2583, 201202214845735767 - 脳・神経系汎用シミュレータGENESISのGPU実装による高速化
岩佐歩; 中山智章; 本多武尊; 山崎匡; 西野哲朗
出版日 2012年01月17日, ハイパフォーマンスコンピューティングと計算科学シンポジウム論文集, 2012巻, 掲載ページ 72-72, 日本語, 170000069157 - Information-theoretic Analysis for Understanding the Behavior of Song Learning by the Bengalese Finch
KhanMd.MahfuzusSalam; Tetsuro Nishino; Kazutoshi Sasahara; Miki Takahasi; Kazuo Okanoya
Songbirds have been actively studied for their complex brain mechanism of sensor-motor integration during song learning. Male Bengalese finches learn singing by imitating external models to produce songs. In general, birdsong which is string of sounds is represented by a sequence of letters called song notes. In this study, we focus on information-theoretic analysis of these sequential data to explore the complexity and diversity of birdsong, and learning process throughout song development. We design and develop the analysis tool which has many features to do analysis for the sequential data. For experiment, we employ thirteen male Bengalese finches, each with different bouts of song data. By applying ethological data mining to these data, we discover that the finches follow two types of song learning mechanism: practice mode and adopt mode. In addition, over the analysis we find that it is possible to visualize the song features, e.g., traditional transmission, by contour surface diagram of the transition matrix. Furthermore, we can easily identify the families from these contour surface diagrams, which is a very challenging task in general. Our obtained results indicate that analysis based on data mining is a versatile technique to explore new aspects related to behavioral science.Songbirds have been actively studied for their complex brain mechanism of sensor-motor integration during song learning. Male Bengalese finches learn singing by imitating external models to produce songs. In general, birdsong which is string of sounds is represented by a sequence of letters called song notes. In this study, we focus on information-theoretic analysis of these sequential data to explore the complexity and diversity of birdsong, and learning process throughout song development. We design and develop the analysis tool which has many features to do analysis for the sequential data. For experiment, we employ thirteen male Bengalese finches, each with different bouts of song data. By applying ethological data mining to these data, we discover that the finches follow two types of song learning mechanism: practice mode and adopt mode. In addition, over the analysis we find that it is possible to visualize the song features, e.g., traditional transmission, by contour surface diagram of the transition matrix. Furthermore, we can easily identify the families from these contour surface diagrams, which is a very challenging task in general. Our obtained results indicate that analysis based on data mining is a versatile technique to explore new aspects related to behavioral science., 出版日 2011年07月20日, 情報処理学会論文誌数理モデル化と応用(TOM), 4巻, 3号, 掲載ページ 49-58, 英語, 1882-7780, 170000066487, AA11464803 - Information-Theoretic Analysis for Understanding the Behavior of Song Learning by the Bengalese Finch
KhanMd.MahfuzusSalam; Tetsuro Nishino; Kazutoshi Sasahara; Miki Takahasi; Kazuo Okanoya
Songbirds have been actively studied for their complex brain mechanism of sensor-motor integration during song learning. Male Bengalese finches learn singing by imitating external models. Birdsongs are strings of sounds represented by a sequence of letters called song notes. In this study, we focused on information-theoretic analysis of these sequential data to explore the complexity and diversity of birdsong throughout song development. We present ethological data mining results for birdsong, which showed that there are 2 types of song development: linear and non-linear. We found that all male birds in the early stages of development sing complex songs, which are gradually crystallized by the elimination of extra transitions. In contrast, this is not true in the case of non-linear song development, wherein there are no practice modes, and all activity counts toward selecting, constructing, and maintaining behavioral outcomes. We also found that contour surface diagrams of the transition matrix can be a good visual representation to distinguish song features. Our results indicate that information-theoretic analysis of behavioral sequences is important for the discovery of new aspects related to behavioral science.Songbirds have been actively studied for their complex brain mechanism of sensor-motor integration during song learning. Male Bengalese finches learn singing by imitating external models. Birdsongs are strings of sounds represented by a sequence of letters called song notes. In this study, we focused on information-theoretic analysis of these sequential data to explore the complexity and diversity of birdsong throughout song development. We present ethological data mining results for birdsong, which showed that there are 2 types of song development: linear and non-linear. We found that all male birds in the early stages of development sing complex songs, which are gradually crystallized by the elimination of extra transitions. In contrast, this is not true in the case of non-linear song development, wherein there are no practice modes, and all activity counts toward selecting, constructing, and maintaining behavioral outcomes. We also found that contour surface diagrams of the transition matrix can be a good visual representation to distinguish song features. Our results indicate that information-theoretic analysis of behavioral sequences is important for the discovery of new aspects related to behavioral science., 出版日 2010年12月09日, 研究報告バイオ情報学(BIO), 2010巻, 8号, 掲載ページ 1-6, 英語, 110007990862, AA12055912 - 小脳スパイキングネットワークモデルにおける条件刺激強度依存性タイミング制御
本多武尊; 山崎匡; 田中繁; 西野哲朗
出版日 2010年04月15日, 情報処理学会論文誌トランザクション(CD-ROM), 2009巻, 2号, 掲載ページ SURIMODERU.VOL.3,NO.2,1-10, 日本語, 1882-7772, 201002201570445810 - FPGA上に実装した小脳ネットワークモデルにおけるタイミングメカニズムの研究
松野香菜子; 本多武尊; 眞鍋秀聡; 田中繁; 西野哲朗
出版日 2010年01月11日, 電子情報通信学会技術研究報告, 109巻, 363(NC2009 71-86)号, 掲載ページ 7-12, 日本語, 0913-5685, 201002258829748304 - Phase diagram of cerebellar granular layer dynamics: A model study
Takeru Honda; Tadashi Yamazaki; Shigeru Tanaka; Tetsuro Nishino
ELSEVIER IRELAND LTD, 出版日 2010年, NEUROSCIENCE RESEARCH, 68巻, 掲載ページ E211-E212, 英語, 研究発表ペーパー・要旨(国際会議), 0168-0102, WOS:000208443701320 - 小脳スパイキングネットワークモデルにおける条件刺激強度依存性タイミング制御
本多武尊; 山崎匡; 田中繁; 西野哲朗
出版日 2009年10月15日, 情報処理学会研究報告(CD-ROM), 2009巻, 3号, 掲載ページ ROMBUNNO.MPS-75,28, 日本語, 2186-2583, 200902250418852680 - 小脳顆粒層のスパイキングネットワークモデルの研究:条件刺激強度依存性タイミング制御
本多武尊; 山崎匡; 田中繁; 西野哲朗
出版日 2009年09月24日, 日本神経回路学会全国大会講演論文集, 19th巻, 掲載ページ 64-65, 日本語, 200902261700055795 - 小脳スパイキングネットワークモデルにおける条件刺激強度依存性タイミング制御
本多 武尊; 山崎 匡; 田中 繁; 西野 哲朗
我々がこれまで構築してきた小脳顆粒層の大規模スパイキングネットワークモデルは,苔状線維刺激呈示からの時間経過を表現する.本研究では,時間経過表現が苔状線維刺激の強度によって制御されるかどうかを調べた.瞬目反射の条件付けの計算機シミュレーションを行い,条件刺激と侵害刺激のペアを繰り返し与えると,プルキンエ細胞が侵害刺激呈示のタイミングの直前で発火を停止するようになることを確認した.その後条件刺激の強度を上げると,プルキンエ細胞の発火停止のタイミングがより早まることを示した.この結果は,条件反応のタイミングを決定するプルキンエ細胞の発火停止のタイミングが条件刺激強度に依存して変化することを示唆する.We have been developing a large-scale spiking network model of the cerebellar granular layer that represents the passage of time (POT) from the mossy fibre (MF) stimulus onset. In this study, we examined whether the POT representation can be controlled by changing the strength of the MF stimulus. We conducted simulations of the delay eyeblink conditioning, in which pairing of a sustained conditioned stimulus (CS) conveyed by MFs with a delayed unconditioned stimulus (US) showed that the Purkinje cell (PC) learned to pause slightly earlier than the onset of the US. When we increased the CS strength, the PC pause shifted earlier. This result suggests that the timing of the conditioned response determined by that of PC pause is adaptively changed by the CS strength., 情報処理学会, 出版日 2009年09月03日, 研究報告数理モデル化と問題解決(MPS), 2009巻, 28号, 掲載ページ 1-6, 日本語, 0919-6072, 110007993844, AN10505667 - Development of Web Counseling System”,Proceedings of the 12th International Conference on Network-Based Information Systems
加藤 千恵子; Shiono,Y; Takaaki Goto; Tetsuro Nishino; Kensei Tsuchida
出版日 2009年08月, Proceedings of the 12th International Conference on Network-Based Information Systems, 掲載ページ 370-375 - 第3回UECコンピュータ大貧民大会(UECda-2008)の報告
大久保 誠也; 本多 武尊; 眞鍋 秀聡; 飯塚 拓郎; Khan Md.MahfuzusSalam; 常田 宏和; 儀間 武晃; 鈴木 智也; 田中 愛実; 松野 香菜子; 若月 光夫; 西野 哲朗
本稿では,2008 年11月22日にUEC(電気通信大学)で開催された,第3回UECコンピュータ大貧民大会(UECda-2008)の概要を報告する。大貧民は,日本で広く行なわれているトランプ・ゲームのひとつである。本大会は大貧民をプレイするコンピュータ・プログラムを対戦させる大会である。以下では,本大会の概要,本大会で採用した大貧民のルール,大会規模,使用したプログラム,および決勝戦の結果について述べる。In this talk we give a summary report of the Third UEC computer DAIHINMIN championship (UECda-2008) held at UEC (The University of Electronic-Communications) on November 22 2008. DAIHINMIN is one of the most popular card game played in Japan. In this championship computer DAIHINMIN engines compete against each other. We present the outline of the championship,the adopted rules,number of participants,used programs,and the result of the final match., 一般社団法人情報処理学会, 出版日 2009年03月02日, 研究報告ゲーム情報学(GI), 2009巻, 27号, 掲載ページ 17-24, 日本語, 0919-6072, 110007162375, AA11362144 - GroverのアルゴリズムのシミュレーションにおけるGPGPUの利用について
芝田浩; 鈴木智也; 大久保誠也; 西野哲朗
出版日 2009年, 電子情報通信学会 第21回量子情報技術研究会資料, 掲載ページ QIT2009-58 pp.72-77 - 小脳顆粒層のスパイキングネットワークモデルにおける状態遷移とタイミングメカニズムに関する研究
本多武尊; 山崎匡; 田中繁; 西野哲朗
出版日 2008年01月08日, 電子情報通信学会技術研究報告, 107巻, 413(NC2007 87-111)号, 掲載ページ 49-54, 日本語, 0913-5685, 200902280775629350 - GPGPUによるGroverのアルゴリズムのシミュレーション
芝田浩; 西野哲朗; 大久保誠也; 鈴木智也
出版日 2008年, 情報処理学会アルゴリズム研究会資料, 掲載ページ AL-120-5, pp.22-40 - 第1回UECコンピュータ大貧民大会(UECda‐2006)の報告
大久保誠也; 小林正人; 本多武尊; 眞鍋秀聡; 青木輝人; 柿下容弓; 小松原頌之; 西野哲朗
出版日 2007年03月05日, 情報処理学会研究報告, 2007巻, 20(GI-17)号, 掲載ページ 25-32, 日本語, 0919-6072, 200902269683946576 - NMR量子計算の定式化
西野哲朗; 志摩孝夫; 芝田浩
出版日 1998年, 電子情報通信学会コンピュテーション研究会資料, 掲載ページ COMP97-114, pp.63-70
書籍等出版物
- デザイン思考に基づく新しいソフトウェア開発手法 EPISODE
西野哲朗
学術書, 日本語, 単著, コロナ社, 出版日 2022年03月25日 - 量子計算
西野哲朗; 岡本龍明; 三原孝志
学術書, 日本語, 共著, 近代科学社, 出版日 2015年10月13日 - 情報工学のための離散数学入門
西野哲朗; 若月光夫
学術書, 日本語, 共著, 第4章~第7章, 数理工学社, 出版日 2015年08月25日, ISBN 9784864810326 - 応用オートマトン工学
西野哲朗; 若月光夫; 後藤隆彰
日本語, 共著, 第3章 文法学習,第4章 画像圧縮, コロナ社, 出版日 2012年02月 - P = NP ? 問題へのアプローチ
西野哲朗
日本語, 編者(編著者), 日本評論社, 出版日 2009年08月 - Grammatical Inference: Algorithms and Applications, 8th International Colloquium, ICGI 2006, Tokyo, Japan, September 2006, Proceedings, LNAI 4201
Y. Sakakibara; S. Kobayashi; K. Sato; T. Nishino; E. Tomita
英語, 編者(編著者), Springer, 出版日 2006年 - 量子コンピュータと量子暗号
西野哲朗
日本語, 岩波書店,物理の世界 59, 出版日 2002年 - 量子コンピュータの理論
西野哲朗
日本語, 編者(編著者), 培風館, 出版日 2002年 - 量子コンピューティング
C. P. ウィリアムズ; S. H; クリアウォータ著; 西野哲朗; 荒井 隆; 渡邊 昇訳
日本語, 編者(編著者), シュプリンガー・フェアラーク東京, 出版日 2000年 - 中国人郵便配達問題=コンピュータサイエンス最大の難関
西野哲朗
日本語, 講談社, 出版日 1999年 - 形式言語の理論
有川節夫監修; 西野哲朗; 石坂裕毅著
日本語, 編者(編著者), 丸善, 出版日 1999年 - 量子コンピュータ入門
西野哲朗
日本語, 編者(編著者), 東京電機大学出版局, 出版日 1997年 - 属性文法入門
西野哲朗
日本語, 編者(編著者), 共立出版, 出版日 1996年 - 形式言語理論入門
アービブ・クフォーリ・モル著; 西野哲朗訳
日本語, 編者(編著者), 東京電機大学出版局, 出版日 1995年 - 計算量理論概説
足立暁生; 西野哲朗
英語, 編者(編著者), 朝倉書店, 出版日 1988年
講演・口頭発表等
- 量子アニーリングマシンの実行時エラーについて
山川拓人; 大久保誠也; 西野哲朗
口頭発表(一般), 日本語, 電子情報通信学会第43回量子情報技術研究会, 国内会議
発表日 2020年 - コンピュータ大貧民におけるレーティング手法について
五ヶ谷純平; 大久保誠也; 若月光夫; 西野哲朗
口頭発表(一般), 日本語, 情報処理学会研究報告. GI(ゲーム情報学), 国内会議
発表日 2020年 - 大貧民におけるプレイヤーの提出手の傾向に関する研究
武内大和; 大久保誠也; 若月光夫; 西野哲朗
口頭発表(一般), 日本語, 情報処理学会研究報告, 情報処理学会ゲーム情報学研究会, 東京, 国内会議
発表日 2019年 - コンピュータ大貧民におけるローカルルールの効果に関する研究
門裕太; 大久保誠也; 若月光夫; 西野哲朗
口頭発表(一般), 日本語, 情報処理学会研究報告, 情報処理学会ゲーム情報学研究会, 東京, 国内会議
発表日 2019年 - 大貧民におけるモンテカルロ法の報酬値に関する研究
土橋康希; 大久保誠也; 若月光夫; 西野哲朗
口頭発表(一般), 日本語, 情報処理学会研究報告, 情報処理学会ゲーム情報学研究会, 東京, 国内会議
発表日 2019年 - コンピュータ大貧民における提出手の影響に関する研究
三石亮; 大久保誠也; 若月光夫; 西野哲朗
口頭発表(一般), 日本語, 情報処理学会研究報告, 情報処理学会ゲーム情報学研究会, 国内会議
発表日 2019年
担当経験のある科目_授業
- 3大学協働基礎ゼミ
The University of Electro-Communications - 3大学協働基礎ゼミ
電気通信大学 - 国際科学技術コミュニケーション論
The University of Electro-Communications - 形式言語理論
電気通信大学 - 形式言語理論
The University of Electro-Communications - 形式言語理論
電気通信大学 - 計算機科学特論
The University of Electro-Communications - 実践ソフトウェア開発概論 III
電気通信大学 - 国際科学技術コミュニケーション論
電気通信大学 - 国際科学技術コミュニケーション論
電気通信大学 - 実践ソフトウェア開発基礎論
The University of Electro-Communications - 実践ソフトウェア開発概論 III
The University of Electro-Communications - 実践ソフトウェア開発概論 III
電気通信大学 - 実践ソフトウェア開発基礎論
電気通信大学 - 実践ソフトウェア開発基礎論
電気通信大学 - 計算機科学特論
電気通信大学 - 計算機科学特論
電気通信大学 - 計算機工学
電気通信大学 - 計算機工学
電気通信大学
共同研究・競争的資金等の研究課題
- 効率的な最大および極大クリーク抽出アルゴリズムの開発と応用
富田 悦次; 若月 光夫; 西野 哲朗; 伊藤 大雄
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 最大クリーク厳密解抽出の分枝限定アルゴリズムに対するこれまでの研究により,最大クリークの近似解が非常に有効に活用出来ることを明らかにしてきている.その近似精度が良くなれば分枝限定はより有効に働く.しかし,近似解抽出のために時間を要すると,総実行時間としては必ずしも短縮とはならず,近似精度と時間との兼ね合いが重要となる.そこで先ず,最大クリーク近似解の抽出を一層高速化し,その上で精度を向上させることにより,総合的に最大クリーク厳密解抽出を効率化した. 続いて,分枝限定のために近似彩色だけでなくMaxSATも用いることにより分枝限定がより強力化されることをこれまでに確認してきたが,MaxSATあるいはその簡略形実行のためのオーバーヘッドの大きさが最大クリーク厳密解抽出総実行時間短縮の妨げとなっていた.これに対しては,MaxSATの簡略形と従来提唱してきていた再番号付け(再彩色)との類似性に着目して両者を融合させることにより,これまでよりも少ないオーバーヘッドによって,有効な分枝限定効果を発揮出来るようにした.さらに,分枝限定アルゴリズムの内部動作は入力グラフの特徴に応じて効率が左右されるため,出来る限り効率がより発揮されるようにと内部動作を適応的に切り替えるようにした. 以上を総合することにより,最大クリーク厳密解抽出のための従来の分枝限定アルゴリズムを有意に高速化することに成功した. このような最大クリーク厳密解抽出アルゴリズムは,容易に最大クリーク全列挙アルゴリズムへと拡張出来る.これにより,符号理論における最良な多元単一削除訂正符号の構成に関しての新たな知見を得ることが出来た. 極大クリーク全列挙問題についてもさらに理論的,実験的に検討を続け,有効な進展結果を得た., 17K00006
研究期間 2017年04月01日 - 2022年03月31日 - データマイニング手法を用いた多人数不完全情報ゲームの特徴抽出
西野 哲朗
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), コンピュータ大貧民においては、日本で人気のあるカードゲームの大貧民をプログラム同士がプレイする。コンピュータ大貧民において強いプログラムはモンテカルロ法のような機械学習手法を使用しているので、プログラムの挙動を予想するのは難しい。本研究では、プレイヤープログラムの特徴を決定木分析手法を用いて抽出する。プログラムの特徴は、3つの観点から決定木を生成することにより抽出される。我々の手法の有効性を示すために、計算機実験を行った。我々の手法を挙動が明確な3つのプログラムに対して適用した。その結果、抽出された特徴は、プログラムの実際の挙動に照らして妥当であることがわかった。, 17K00297
研究期間 2017年04月01日 - 2020年03月31日 - IoT図書館を活用した映像とセンサデータに基づく行動分析
西野哲朗
コニカミノルタ(株), 共同研究, 研究代表者
研究期間 2018年07月01日 - 2019年03月31日 - 最大および極大クリーク抽出アルゴリズムの高効率化と応用
富田 悦次; 若月 光夫; 西野 哲朗; 伊藤 大雄
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 最大クリーク抽出のための分枝限定アルゴリズムに対し,近似最大クリーク抽出アルゴリズムを効果的に組合せ,さらに節点整列と近似彩色を適切に適用することにより,実働上一層の高効率化を達成した.また理論的には,最大クリーク問題が多項式時間的高速に可解となる,よりゆるやかな条件およびアルゴリズムを与えた. 極大クリーク全列挙アルゴリズムについては,それを疑似極大クリークの全列挙までを扱えるように拡張し,ネットワーク解析への応用に対して有効性が確認された., 25330009
研究期間 2013年04月01日 - 2018年03月31日 - ミスを犯す人間らしいゲームAIの研究
伊藤 毅志; 保木 邦仁; 西野 哲朗; 棟方 渚; 片寄 晴弘; 池田 心
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(B), 本研究では、ゲームにおける人間のミスに着目し、人間らしいミスを犯すゲームAIの構築を目指し、以下の研究成果を得た。 1)ゲームにおける人間の犯すミスの原因に着目した分類。2)人間の生物学的成約を考慮したモデルを持ったゲームAIの構築。3)ゲームにおける技量を自動的に調整して良い勝負を演出できるゲームAIの提案と評価。4)人間の思考の特徴である「流れ」を持たせ、人間らしいプレイを実現するゲームAIの提案。 これらの研究の成果は、人間と対戦するゲームAIに「強さ」という方向性以外の新しい評価基準をもたらし、多様なゲームAIの指針となると考えられる。, 25280130
研究期間 2013年04月01日 - 2016年03月31日 - 形式言語の効率的学習アルゴリズムの開発及びその応用システムの構築
若月 光夫; 富田 悦次; 西野 哲朗
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 決定性プッシュダウン変換器のスタック記号を1種類に限定した決定性限定1カウンタ変換器について,それが最終状態受理式の場合,より一般的なε-推移を持つ場合についてもその等価性判定及び包含性判定が多項式時間で行えることを明らかにした.また,実時間最終状態受理式決定性限定1カウンタ変換器に対して,所属性質問及び等価性質問を用いた多項式時間の学習アルゴリズムを開発した.更に,正則言語の部分クラスに対する正例からの極限同定を組み込んだジュウシマツの歌構造解析ツールEUREKAを利用することによって,コンピュータ上でトランプゲームの大貧民の対戦を行うプログラムの挙動の規則性が抽出可能なことを示した., 23500011
研究期間 2011年04月28日 - 2015年03月31日 - 電気通信大学 データアントレプレナープログラム
田村元紀
住友電工グループ社会貢献基金
研究期間 2015年 - 計算論的学習理論に基づく脳機能のシミュレーション
西野 哲朗; 田中 繁; 山崎 匡; 保木 邦仁
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(B), 本研究では、計算論的学習理論を基盤として、運動、思考、記憶といった脳機能に関する以下の事例研究を行う。運動:ロボット動作の規則を状態遷移機械として学習し、得られた状態遷移機械によってロボット動作をシミュレーションする。記憶:脳のワーキングメモリのニューラルネットモデルを構成し、現実に即した動作を行わせる。思考:カードゲームのプレイの戦略をモンテカルロ法によって学習し、報酬を最大化するアルゴリズムによってプレイする。これらの方法論の性質、効果を比較検討し、相互補完させることで、計算論的学習理論に基づく脳機能シミュレーションの方法論を確立する。, 23300055
研究期間 2011年04月01日 - 2014年03月31日 - 効率的な最大クリーク抽出アルゴリズムの開発と理論的・実験的評価および応用
富田 悦次; 若月 光夫; 高橋 治久; 西野 哲朗
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 一般グラフの最大クリーク問題を多項式時間的可解とする条件とアルゴリズムを開発し,評価結果を示した.本アルゴリズムは,当条件にかかわらず,解自体は常に正しく出力する.また,一般の場合に対してこれまで新たに開発した最大クリーク抽出アルゴリズムの動作を内部にわたって詳細に実験的評価を行い,その高効率性を明らかにした.更に,これらのアルゴリズムを基として,バイオインフォマティクス等の問題に対しての有効な応用を示した., 22500009
研究期間 2010年 - 2012年 - 形式言語に対する例からの学習を行う効率的アルゴリズムの開発・応用
若月 光夫; 富田 悦次; 西野 哲朗
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 決定性プッシュダウン変換器のスタック記号を1 種類に限定した決定性限定ワンカウンタ変換器について,それが空スタック受理式及び実時間最終状態受理式の場合,その等価性判定が多項式時間で行えることを証明した.また,決定性限定ワンカウンタオートマトンのある部分クラス等が,正例から多項式時間で極限同定可能なことを証明した.更に,正則言語の部分クラスに対する正例からの極限同定を利用した,ジュウシマツの歌文法の解析手法を改良し,自動化を図った., 20500007
研究期間 2008年 - 2010年 - 計算論的手法を用いた鳥の歌文法獲得過程の解明
西野 哲朗; 富田 悦次; 岡ノ 谷一夫; 田中 繁; 山崎 匡
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(B), 歌鳥は、歌の学習における脳の複雑なメカニズムに対する良いモデルとして、活発に研究されてきた。雄のジュウシマツは、外部モデルを模倣することにより歌を学習する。記号列として表現される音の系列である。我々は、計算論的手法を用いて、このような歌の音素列からジュウシマツの歌文法を自動抽出するシステムを構築し、歌文法の発達過程のモデル化とその実データによる検証を行った。我々の実験結果は、このような動作系列に関する実験が、新知識の発見には重要であることを示唆している。, 20300056
研究期間 2008年 - 2010年 - 最大クリーク抽出アルゴリズムの効率化・拡張と計算量評価および応用
富田 悦次; 高橋 治久; 西野 哲朗; 若月 光夫; 垂井 淳
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 最大クリークを抽出する新しいアルゴリズムMCSを開発し,格段に高速であることを明らかにした.これにより,従来では100日以上かかっても解けなかった幾つかの問題を100秒以内で解くことに成功した.最大クリーク問題が多項式時間的に可解となる基本的結果も確立した.また,最大クリーク抽出アルゴリズムがハイパーグラフにおいても効率的に稼働する様に拡張した.更に,これらのアルゴリズムをデータマイニングなどの実問題に応用して有効な結果を得た., 19500010
研究期間 2007年 - 2009年 - 暗号プリミティブの安全性検証の自動化への展開
太田 和夫; 西野 哲朗; 崎山 一男; 國廣 昇; 國廣 昇
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 暗号プロトコルの安全性自動検証手法APSG,およびT-PIOAの改良と事例研究の拡張を行い,各手法の性能を評価するとともに実用性を向上させた.また,低資源向き認証プロトコルGPS方式とHB-PUF方式の安全性解析を行い,既存方式の問題点を指摘するとともに,改良方式を提案した., 19500009
研究期間 2007年 - 2009年 - 計算論的手法を用いた鳥の歌文法の研究
西野 哲朗; 笹原 和俊; 高橋 美樹
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), ある種の鳥は、「歌」や「さえずり」と呼ばれる、複数の音節からなる比較的長い音声を発する。これらの鳥の歌の発達過程と、人の幼児の音声言語の発達過程には、脳科学的な共通点が多く、また、人間の脳では行えない生体実験も、鳥では可能であるといった理由から、近年、この方面の研究が盛んに行われている。そのような鳥の歌の研究のなかでも、ジュウシマツを使った研究においては大変興味深い成果が得られている。そこで本研究では、この方面の研究をさらに推進するために、計算論的手法を用いて、歌の音素列からジュウシマツの歌文法を自動抽出し、その構造を解析するための方法論を確立することを目標とした。 そのために、本研究では、チャンクと呼ばれる、歌のなかでひと塊で歌われる音素の集合に着目し、計算論的学習理論の手法を用いてジュウシマツの歌文法の自動抽出を行う。具体的には、チャンクおよび歌文法を自動的に抽出するために、音素列を入力として、チャンク単位で状態遷移を行うk可逆オートマトンを生成する歌文法の自動抽出システムを実現した。また、このシステムを用いて実際のジュウシマツの歌文法を抽出し、その構造を解析するために、以下のことを実現した。 1.音素の自動抽出:ジュウシマツのソナグラムからの、音素の切り出しを自動化した。具体的には、Wiener entropyや、frequency moduration等の特徴量を用いた音素の切り出し法や、音素のクラスタリング手法を確立し、その結果を用いて、音素の自動抽出プログラムを完成させた。 2.歌に含まれるノイズの除去:音素間の状態遷移確率を計算し、ある設定値以下の遷移をノイズとして削除した。また、音素間の遷移だけでなく、データの末尾であることも遷移の一つと考えることにより、歌を途中で止めてしまったというノイズにも対応できるようにした。, 18500109
研究期間 2006年 - 2007年 - 効率的な組合せ最適化アルゴリズムの開発と応用
富田 悦次; 高橋 治久; 西野 哲朗; 小林 聡; 堀田 一弘; 若月 光夫
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(B), 組合せ最適化問題の中でも,特に典型的で重要な問題である最大クリーク抽出問題について,分枝限定アルゴリズムを基本として,その効率化を進めた.ここでは,先ず節点の探索順序が非常に重要であることを明らかにし,効率的な探索順序を実現した.更に,分枝限定の効率化の中心課題となる,最大クリークの上界を与えるための新らしい巧妙な近似彩色手法を開発し,それと前記の適切な節点探索順序とを組み合わせることにより,小さい計算量で探索領域を従来よりも大幅に減少させ,従来よりも非常に高効率な最大クリーク抽出アルゴリズムを得ることに成功した. 上記の方法は,節点や枝に重みのあるグラフへも拡張して,重みが最大のクリーク,あるいはハイパーグラフ中の最大ハイパークリーク抽出アルゴリズムの効率化も達成した.これにより,量子論理回路設計,DNA配列設計のための基礎を一段と発展させた. 更に上記に伴い,極大なクリークを全列挙する問題に対して,ある基準において理論的計算量の最適性を保証するアルゴリズムを確立し,それが実際の実行上においても従来の他のアルゴリズムよりも格段に効率的であることを明らかにした.またそれを,特に重要部分である最大に近い極大クリークだけを効率良く抽出するアルゴリズムに発展させると共に,データマイニングなどにおいて重要となる2部グラフの場合に特化したアルゴリズムも提唱し,その効率性を示した. これらのアルゴリズムを活用することにより,タンパク質側鎖パッキング,タンパク質スレッディングなどのバイオインフォマティクスの実問題に対して良好な成果を得た. 計算論的学習理論の問題においては,質問による効率的学習法や,正の例から極限同定可能とする言語クラスを統一的に扱う方法などを明らかにした., 16300001
研究期間 2004年 - 2006年 - 量子アルゴリズムに対する公開鍵暗号及び秘密鍵暗号の安全性評価
太田 和夫; 西野 哲朗; 國廣 昇
日本学術振興会, 科学研究費助成事業, 電気通信大学, 特定領域研究, 本研究の主題は,量子計算機の実現が公開鍵暗号及び,秘密鍵暗号にどのような影響を及ぼすかを明らかにすることである.そこで,本年度は最短ベクトル問題の困難さに安全性の根拠をおいた公開鍵暗号系に対する安全性評価を行なった. 最短ベクトル問題に対しては,古典・量子を問わず,多くの研究が行われている.この問題に対する量子アルゴリズムとして,提案されているほとんどのものは近似アルゴリズムであり,真に最短のベクトルを探索するアルゴリズムは考案されていない.そこで,古典アルゴリズムと量子アルゴリズムを組み合わせることで真の最短ベクトルを探すアルゴリズムを提案した. 提案アルゴリズムは次の2つのステップからなっている.最初に,最短ベクトルの探索範囲を古典計算機上で決定する.そして,固定した探索範囲内から,真の最短ベクトルをDurrとHoyerの最小値探索量子アルゴリズムを用いて探索する. 量子計算機を用いて最小値の探索を行う際の計算量は,探索空間のサイズに依存する.そのため,探索範囲をより限定するほど,最短ベクトルを高速に発見することができる.探索範囲の素朴な決定法として,入力した基底の中の最短ベクトルの長さを利用することが出来るが,より小さい探索範囲を決定する方法として,我々は,LLL簡約基底の最短ベクトルの長さを用いることを提案した.LLL簡約基底を計算するアルゴリズムは,パラメータδによって,計算時間と出力ベクトルの長さとのtrade offが制御される. 我々は,LLL簡約基底計算アルゴリズムのパラメータδを用いて,提案アルゴリズム全体の計算量を詳細に評価し,計算量を最小にする値を理論的に評価した.その結果,最適となるδと,その際の計算量が明らかとなった. 数値実験によると,提案方式は,前述した素朴な方法よりも一般に高速である.しかしながら,現時点では,最良の古典アルゴリズムの計算量を上回ることはできていない., 16016235
研究期間 2004年 - 2005年 - 最適性理論に基づく格理論・リンキング理論の構築とそのニューラルネット上への実現
中村 渉; 西野 哲朗; 坂本 真樹; 佐藤 滋; 堀江 薫
日本学術振興会, 科学研究費助成事業, 基盤研究(C), 今年度は、昨年度にニューラルネット上に実現した対格型格組織・能格型格組織を実現する、学習アルゴリズムとして誤差逆伝播法を採用した多層パーセプトロンモデルを、大脳皮質の学習方式であるヘッブ学習則に移し替える基礎作業として、量子ニューラルネットワークの計算論的な吟味・検討を行った論文を発表した(Matsumoto, Okubo, and Nishino 2004)。量子コンピューターは、量子力学の世界における波動関数の重ね焼きを利用する(西野1999)ため、膨大な計算量の並列計算を要求する人間の言語活動のモデル化にも有用であると思われる。この論文は、量子コンピューターの強力な計算力を、言語獲得を実現するニューロイダル・ネットへ適用する可能性を検討したものである。 また、目標として掲げた、言語獲得の「動詞-島(Verb-Island)」段階以降のシミュレーションについては今年度中の達成は残念ながら断念せざるを得ない状態である。成人の文法に見いだされる句構造(統語範疇に依存)を前提にした状態で、対格型のリンキング(他動詞文における文法関係の付与)を最適性理論に基づいて導く研究論文を目下書き進めている所である(中村印刷中も参照)。具体的には、Dowty(1995)やAckerman and Moore(2003)が展開したプロトロール理論に基づき、相対的な重みづけを受けた意味特徴の束として文法関係を導くことを構想している。 最後に、今年度は、横山・内田・中村・川島他(2004)において、第一言語(母語)と第二言語の相違を踏まえて、文を理解するプロセスを脳機能画像法(fMRI)によって検証した。, 14510616
研究期間 2002年 - 2004年 - 量子アルゴリズムに対する公開鍵及び共通鍵暗号の安全性評価
太田 和夫; 國廣 昇; 西野 哲朗
日本学術振興会, 科学研究費助成事業, 電気通信大学, 特定領域研究, 平成15年度の主な成果は以下の通り. 1.量子アルゴリズムに対する公開鍵暗号に対する安全性 Shorのアルゴリズムにより,素因数分解が多項式時間で完了することは明らかになっている.しかしながら,量子計算機固有の問題,すなわち,原理的に可逆計算でなければならないこと,一回の演算時間が古典計算機より遅いこと,などの理由により,必ずしも,意味のある時間で素因数分解が完了するかどうかは明らかではない.本研究では,Shorのアルゴリズムをいくつかの手法により,量子回路で記述し,実際に必要となるgate数,qubit数を厳密に求め,必要となる計算時間を評価した.その結果,演算時間の遅いデバイスを用いた場合や,qubitを節約する回路を用いた場合には,現実的な時間で素因数分解が完了しないことを示した.具体的には,古典計算機よりも,量子計算機が真に有効であるためには,1592qubit以上で,演算時間が70μ秒以内,もしくは,1064qubitで,演算時間が16μ秒以内の量子計算機が実現しなくてはならないこと明らかにした. 2.NMR量子計算機に対する共通鍵暗号の安全性評価 平成13,14年度に引き続き,量子計算機に対する共通鍵暗号の安全性評価を行った.本年度は,GroverのアルゴリズムのNMR量子計算機への適用可能性に関して考察を行なった.さまざまな物理的条件(すなわち,可能な観測誤差)に対して評価を行ない,従来の量子計算機よりも高速に,暗号化鍵の探索が行なえることを確認した.具体的には,58bit鍵の探索において,測定誤差が1/256であるとき,従来の方式よりも12.5倍高速実行可能であることを数値実験により確認した., 15017236
研究期間 2003年 - 2003年 - 例からの学習を行う効率的アルゴリズムの開発
富田 悦次; 若月 光夫; 西野 哲朗; 小林 聡
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 単純決定性言語の学習問題の一形式として,目的言語の主要部分である代表サンプルと名付けた例の部分集合が与えられていれば,学習者からは所属性質問を繰り返すことだけにより,多項式的に目的言語を厳密学習出来る効率的アルゴリズムを確立した.ここで,単純決定性言語は多項式的に等価性判定することが出来るとの以前の成果を巧妙に利用している. 決定性プッシュダウンオートマトンの学習に関しては,実時間空スタック受理式1カウンターオートマトンで,推移規則が各入力記号に対して一個のみ存在するモデルについて,それを明確に特徴付ける特徴サンプルを多項式サイズにおいて明確に規定する方法を確立し,それを基本として,正の例だけから更新時間・更新回数共に多項式的な極限同定学習アルゴリズムを達成した. ブール関数の内でAC^0と呼ばれるクラスに対し,その入出力例にノイズが加わった場合においても近似学習を達成するアルゴリズムを考案した.ここでは,先ずノイズ率あるいはその上界が既知であることを前提とした場合を考え,更に,そのノイズ率自身を推定することにも成功し,これにより,同ブール関数のクラスを,ノイズ率が未知のノイズ付例からでも,準多項式的に学習達成するアルゴリズムを確立した. 正則言語のある部分クラスについて,それの正の例だけから極限同定を行う学習アルゴリズムを考案し,更に,上記言語クラスを含む正則言語の幾つかの部分クラスに対して,正の例から極限同定を可能とする統一的手法を提示した. 更に,学習における概念のクラスタ化を行う,グラフ中の最大クリーク抽出に関して非常に効率的なアルゴリズムを確立し,一般化することにより,それをバイオインフォマティクス,画像処理などの幾つかの実問題に応用して有効な成果を得た., 13680435
研究期間 2001年 - 2003年 - 量子アルゴリズムに対する共通鍵暗号の安全性評価
太田 和夫; 國廣 昇; 西野 哲朗
日本学術振興会, 科学研究費助成事業, 電気通信大学, 特定領域研究, 平成14年度の主な成果は以下の通り. 1.NMR量子計算機に対する共通鍵暗号の安全性評価 公開された暗号化アルゴリズムE,平文m_0及び暗号文c_0が与えられた時,c_0=E(k_0,m_0)の関係をみたす秘密鍵K_0を見つける既知平文攻撃のシナリオにおける,共通鍵暗号の安全性の評価を行った.平成13年度にNMR量子計算機を一般化した,Bulk Quantum Turing Machine(BQTM)による数え上げ技法を応用した新しい共通鍵暗号解読アルゴリズムの提案を行ったが,今年度は,数値実験により,本提案アルゴリズムの有効性に関して詳細に検討を行った.その結果,NMR量子計算機の観測精度Lと秘密鍵の長さnが,L>(3n+2)/4となる場合には,提案方式が従来の結果(Groverのアルゴリズムの適用)を上回ることを明らかにした.現在の状況では,この条件式は,数値実験により求めたいくつかの仮定に基づいているため,今後の研究課題として,この仮定の理論的な証明が残されている.また,今後,暗号化関数の内部構造を利用した新たな攻撃法に関する研究を行う予定である. 2.量子アルゴリズムに対する公開鍵暗号の安全性 共通鍵暗号に対してだけでなく,量子アルゴリズムに対する公開鍵暗号の安全性評価も開始した.Shorの素因数分解アルゴリズムにおいて,もっとも計算時間が必要であり,難しい制御が必要なのは,べき乗剰余演算であると言われている.このべき乗剰余演算を行う量子回路の構成に関して,いくつかの成果を出した.例えば,Montgomery Reductionや右向きBinary Methodを量子回路に導入すれば,効率的にべき乗剰余演算を行えることを明らかにした.今後の課題として,さらなる効率的な量子回路の探索および,物理デバイスに応じた回路の探索を考えている., 14019040
研究期間 2002年 - 2002年 - 量子アルゴリズムに対する共通鍵暗号の安全性評価
太田 和夫; 西野 哲郎
日本学術振興会, 科学研究費助成事業, 電気通信大学, 特定領域研究(C), 平成13年度の主な成果は以下の通り. 1.鍵の総当り攻撃のファイル探索問題への帰着 公開された暗号アルゴリズムE,平分m_0および暗号文c_0が与えられたとき,c_0=E(k_0,m_0)の関係をみたす秘密鍵k_0を見つける既知平文攻撃のシナリオでの鍵の総当り攻撃を,ファイル探索問題に帰着させる変換(攻撃法)を提案した.その変換が従来の結果(Groverのアルゴリズムを素朴に適用する場合)よりも有利となる条件を洗い出した. マシン実験を用いて案際に使用されている暗号系において,その条件が成立つかを調べたところ,成立しないことが判明した.よって,ここで提案した変換では安全性の心配はないことを確認した. 2.中間一致攻撃型の暗号解読の実現可能性について Chiらが提案しているファイル探索問題の高速化技法(http://xxx.lanl.gov/archive/quant-ph/9707011)の妥当性を評価して,彼等の主張に誤り(存在を仮定しているオラクル関数に問題点)があることを発見した.よって,中間一致攻撃型の暗号解読は,現在のところ,それほどの脅威ではないと思われる. 3.NMR計算機に対する共通鍵暗号の安全性 NMR計算機等を一般化した,Bulk Quantum Turing Machine (BQTM)による数え上げ(counting problem)技法にを応用した新しい共通鍵解読アルゴリズムを提案した. 提案アルゴリズムでは,ブール関数F^<(d)>_rを導入することで,暗号アルゴリズムEを実現するオラクルの呼び出し回数とNMR計算機の観測の精度との間にトレードオフが成立つことを示した.妥当な仮定のもとで計算の複雑度を予想し,小規模な実験を行ったところ,従来の結果をしのぐ可能性があること分かった. 現在,このアプローチの有効性を調べるために,マシン実験を継続している., 13224039
研究期間 2001年 - 2001年 - 大脳における機能的結合問題の工学モデルとその応用に関する研究
高橋 治久; 若月 光夫; 西野 哲朗; 富田 悦次
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 高等生物において,外界からの情報が脳内で解析的に処理された後,いかにそれらが統合されるかを説明する問題をバインディング問題とよぶ.本研究では,バインディングを説明できるニューラルモデルの構築と応用を目指して研究を行った.従来のモデルでは,バインディングを説明するためのスパイクの同期あるいは相関を表すことができない.そこで,本研究では従来のアナログニューラルモデルの自然な拡張で,スパイクの相関や同期を位相として表現できる位相ニューラルモデルを開発し,その正当性と学習アルゴリズムを提案した.提案した位相ニューラルモデルは,振動モデルと,コバリアンスモデルの二つであり,これらに対し,Hebb学習則の提案とボルツマン学習規則を導出し,その計算機シミュレーション実験と応用を行った.まず,Hebb規則では,コバリアンスを考慮した本来の意味での学習則が初めて簡単な数理モデルに組み込めた.シミュレーション実験では,これが収束することを確認し,文字認識への応用を行った.さらに,ボルツマンマシンの学習規則が位相モデルに自然に拡張できることを示し,学習規則を導いた.とくにコバリアンス位相モデルは,従来のミーンフィールドモデルの拡張であり,相関も考慮しているため精度良く確率モデルの近似が行われる.計算機シミュレーションの結果,ミーンフィールドモデルでは収束しない多くの問題が,位相コバリアンスモデルでは収束することが示された.本研究では更に,学習の汎化性能を解析しいくつかの基本的な結果を,得ることができた.またバインディングに関して理論的モデルを構築した結果得られた知見を,音声認識と脳波識別に応用し従来のものより格段に性能の良い識別機を提案した., 10650353
研究期間 1998年 - 2000年 - 順序情報の生成・学習を説明する計算論的神経回路モデル
田中 繁; 西野 哲朗
日本学術振興会, 科学研究費助成事業, 理化学研究所, 特定領域研究(A), 今年度は、基底核を表す部分ネットについて、前年度のものよりも詳細な解剖学的構造を考慮に入れて精緻化を図り、基底核のindirect pathwayをモデルに組み込んだ。すなわち、indirect pathwayの回路としては、解剖学的に確認されている(1)線条体熬W蒼球外節燻居-下核熬W蒼球内節と(2)線条体熬W蒼球外節熬W蒼球内節を採用した。さらに、淡蒼球内節においては、indirect pathwayはdirect pathwayに比べて神経投射の選択性は弱いと仮定した。 本モデルによって、ドーパミンの代謝異常による運動障害のシミュレーションが可能になり、病理学的所見を再現することができたと考えている。 例えば、Hyperkinesiaにおいては、我々のモデルによると、線条体でのドーパミン過剰はdirect pathwayの活動亢進によって淡蒼球内節のmovement-related neuronsのトニックな活動を強く抑制する一方で、線条体からindirect pathwayへの出力はドーパミンによって抑圧されるので結果的には淡蒼球外節の出力は脱抑制によって亢進し、(1),(2)の経路を経て淡蒼球内節の活動を強く抑制する。これによって視床ニューロンの脱抑制を介して大脳皮質にポジティブフィードバックが掛かり、ある種の運動要素をコードしたニューロン活動がビルドアップされる。しかしながらindirect pathwayの方がdirect pathwayよりも神経結合の特異性が弱いと仮定しているために、ある運動要素をコードしているmovement-related neuronsの活動が変化している時に別の運動要素をコードしているmovement-related neuronsの活動が変化してしまい、ひとつの運動に留まることができなくなると解釈できる。これによってハンチントン舞踏病に見られるような不随運動が説明できるものと考える。, 11145243
研究期間 1999年 - 1999年 - 量子コンピュータによる効率的計算の研究
西野 哲朗
日本学術振興会, 科学研究費助成事業, 電気通信大学, 奨励研究(A), 本研究では、巡回セールスマン問題のような極めて難しい組合せ最適化問題に、状態の重ね合わせ等の、量子計算のメカニズムがどのように応用しうるかについて検討を重ねてきた。 多項式時間アルゴリズムが知られていない問題が、量子チューリング機械を用いれば、少ない誤り確率で効率良く解けることを証明することは、量子チューリング機械の計算能力を明らかにする上で非常に重要である。そのような結果が証明できれば、少なくとも、量子並列化機能にによって得られた余分な計算能力を、古典的計算によって達成するのが難しいことが示されたことになる。ところで、ショアが対象とした因数分解の問題は、多項式時間では解けず、しかもNP完全でもないだろうと予想されている。そこで本研究では、量子チューリング機械上で、NP完全な組合せ最適化問題を少ない誤り率で効率良く解けるか否かについて検討を行なった。 本研究において申請者は、量子チューリング機械を用いたSAT(論理式の充足可能性判定問題)の解法について研究を行ない、以下のような結果を得た。 仮定 A: 様相の重ね合わせのなかに、ある特定の様相Cが存在することを観測したときに、Cがその重ね合わせ内に存在していれば、そのことを確率1でCの入力サイズに関する多項式時間で観測することができる。 定理 仮定Aのもとでは、SATを多項式時間で解く量子チューリング機械が存在する。, 07780244
研究期間 1995年 - 1995年 - 軟X線を用いた脳定位手術装置の開発
林 〓治; 本間 秀明; 仲光 邦明; 西野 哲朗; 夜久 竹夫
日本学術振興会, 科学研究費助成事業, (財)東京都神経科学総合研究所, 試験研究, 初年度・次年度に『軟X線脳定位手術装置』の機械部分およびコンピュ-タプログラムの設計・作製を行なった。最終年度(平成元年度)は、実際に装置を稼働し、問題点を洗い出して、その改良を行なった。ハ-ドウェアおよびソフトウェアの基本設計は林班長が行なった。X線発生装置/撮影装置を含む機械部分の作製は本間班員を中心として、また座標設定のためのコンピュ-タプログラムの作製は夜久班員を中心として作業が進められた。 装置の本体は軟X線発生装置・X線カメラ・動物固定台・動物固定台移動機構・画像処理機構が巾2000x高1700x奥行1150(mm)のX線防御のための鉄製筐体に収められ、筐体外部から動物・電極・X線カメラ等の位置を電気または油圧の動力を用いて遠隔操作ができるようになっている。X線源とX線カメラを結ぶ光軸を固定し、動物固定台上に保定した実験動物を移動機構によって最適の位置に移動する。さらに、固定台を90°回転させることによって動物の頭部を正面・側面の2方向からX線による透視を行なうことができる。動物頭部のX線画像は実物の約28倍に拡大してモニタ-上で観察する。動物の位置調整は、このX線画像を観察しながら遠撮操作で行なうために、高い精度で行なうことができる。 座標設定のためのソフトウェアによって頭部原点と目標点(電極)の位置を設定し、この座標をX線画像と同一の画面上にス-パ-インポ-ズして表示した。原点位置・目標点位置および座標軸の目盛はキ-ボ-ド操作によって自由に設定できるようにした。また、動物頭部の透視方向に合せて正面画像用・側面画像用のそれぞれの座標軸が表示されるようにプログラムを組んだ。これによって、脳内の構造が容易に計測できるようになった。, 62840023
研究期間 1987年 - 1989年