(57)【要約】【課題】曖昧性を解消した有限状態木オートマトンを生成することができるようにする。【解決手段】（１）Ａ’の初期状態を登録し、（２）Ａ’の状態（ｐ，ｓ）の各々について、（２−１）状態ｐが、Ａの終了状態であって、状態（ｐ，ｓ）と同値関係にある状態が、Ａ’の終了状態として登録されていない場合、状態（ｐ，ｓ）を、Ａ’の終了状態として登録し、（２−２）Ａにおける、状態ｐを含む状態ｐ１，・・・，ｐｋの組み合わせを始点とする辺の各々に対し、（２−２−１）状態の組み合わせを作成し、（２−２−２）作成された組み合わせの各々について、（２−２−２−１）状態（ｑ、ｔ）を作成すると共に辺を生成し、（２−２−２−２）生成された辺が、曖昧性を作らない場合に、Ａ’の辺として登録し、状態（ｑ、ｔ）が、Ａ’に登録されている状態の集合に含まれない場合に、状態（ｑ、ｔ）を、Ａ’の状態として登録する。【選択図】図３
2016048462.tif 000002
【特許請求の範囲】
【請求項１】
入力された有限状態木オートマンＡの曖昧性を解消した有限状態木オートマトンＡ’であって、前記有限状態木オートマンＡの状態ｐと状態集合ｓとのペアに対する状態（ｐ，ｓ）を有する有限状態木オートマトンＡ’を生成する曖昧性解消装置であって、
入力された有限状態木オートマンＡを受け付ける入力部と、
（１）前記有限状態木オートマンＡの初期状態ｉと前記初期状態ｉからなる状態集合とのペアに対する、前記有限状態木オートマンＡ’の初期状態（ｉ，｛ｉ｝）を登録し、
（２）前記有限状態木オートマンＡ’に登録されている状態（ｐ，ｓ）の各々について、
（２−１）前記状態ｐが、前記有限状態木オートマンＡの終了状態であって、前記状態（ｐ，ｓ）と同値関係にある状態が、前記有限状態木オートマンＡ’の終了状態として登録されていない場合、前記状態（ｐ，ｓ）を、前記有限状態木オートマンＡ’の終了状態として登録し、
（２−２）前記有限状態木オートマンＡにおける、状態ｐを含む状態ｐ１，・・・，ｐｋの組み合わせを始点とする辺の各々に対し、
（２−２−１）前記状態（ｐ，ｓ）を含む、状態（ｐ１、ｓ１），・・・，状態（ｐｋ、ｓｋ）の組み合わせを各々作成し、
（２−２−２）前記作成された組み合わせの各々について、
（２−２−２−１）前記組み合わせの状態（ｐ１、ｓ１），・・・，状態（ｐｋ、ｓｋ）を始点とする辺から遷移する新たな状態（ｑ、ｔ）を作成すると共に、前記組み合わせの状態（ｐ１、ｓ１），・・・，状態（ｐｋ、ｓｋ）を始点とする辺を生成し、
（２−２−２−２）前記生成された辺が、前記有限状態木オートマンＡ’に登録されている辺に対して、曖昧性を作らない場合に、前記生成された辺を、前記有限状態木オートマンＡ’の辺として登録し、前記作成された新たな状態（ｑ、ｔ）が、前記有限状態木オートマンＡ’に登録されている状態の集合に含まれない場合に、前記新たな状態（ｑ、ｔ）を、前記有限状態木オートマンＡ’の状態として登録する曖昧性解消部と、
前記有限状態木オートマンＡ’を出力する出力部と、
を含む曖昧性解消装置。
【請求項２】
入力部、曖昧性解消部、及び出力部を含み、入力された有限状態木オートマンＡの曖昧性を解消した有限状態木オートマトンＡ’であって、前記有限状態木オートマンＡの状態ｐと状態集合ｓとのペアに対する状態（ｐ，ｓ）を有する有限状態木オートマトンＡ’を生成する曖昧性解消装置における曖昧性解消方法であって、
前記入力部が、入力された有限状態木オートマンＡを受け付けるステップと、
前記曖昧性解消部が、
（１）前記有限状態木オートマンＡの初期状態ｉと前記初期状態ｉからなる状態集合とのペアに対する、前記有限状態木オートマンＡ’の初期状態（ｉ，｛ｉ｝）を登録し、
（２）前記有限状態木オートマンＡ’に登録されている状態（ｐ，ｓ）の各々について、
（２−１）前記状態ｐが、前記有限状態木オートマンＡの終了状態であって、前記状態（ｐ，ｓ）と同値関係にある状態が、前記有限状態木オートマンＡ’の終了状態として登録されていない場合、前記状態（ｐ，ｓ）を、前記有限状態木オートマンＡ’の終了状態として登録し、
（２−２）前記有限状態木オートマンＡにおける、状態ｐを含む状態ｐ１，・・・，ｐｋの組み合わせを始点とする辺の各々に対し、
（２−２−１）前記状態（ｐ，ｓ）を含む、状態（ｐ１、ｓ１），・・・，状態（ｐｋ、ｓｋ）の組み合わせを各々作成し、
（２−２−２）前記作成された組み合わせの各々について、
（２−２−２−１）前記組み合わせの状態（ｐ１、ｓ１），・・・，状態（ｐｋ、ｓｋ）を始点とする辺から遷移する新たな状態（ｑ、ｔ）を作成すると共に、前記組み合わせの状態（ｐ１、ｓ１），・・・，状態（ｐｋ、ｓｋ）を始点とする辺を生成し、
（２−２−２−２）前記生成された辺が、前記有限状態木オートマンＡ’に登録されている辺に対して、曖昧性を作らない場合に、前記生成された辺を、前記有限状態木オートマンＡ’の辺として登録し、前記作成された新たな状態（ｑ、ｔ）が、前記有限状態木オートマンＡ’に登録されている状態の集合に含まれない場合に、前記新たな状態（ｑ、ｔ）を、前記有限状態木オートマンＡ’の状態として登録するステップと、
前記出力部が、前記有限状態木オートマンＡ’を出力するステップと、
を含む曖昧性解消方法。
【請求項３】
入力された有限状態木オートマンＡの曖昧性を解消した有限状態木オートマトンＡ’であって、前記有限状態木オートマンＡの状態ｐと状態集合ｓとのペアに対する状態（ｐ，ｓ）を有する有限状態木オートマトンＡ’を生成するためのプログラムであって、
コンピュータを、
入力された有限状態木オートマンＡを受け付ける入力部、
（１）前記有限状態木オートマンＡの初期状態ｉと前記初期状態ｉからなる状態集合とのペアに対する、前記有限状態木オートマンＡ’の初期状態（ｉ，｛ｉ｝）を登録し、
（２）前記有限状態木オートマンＡ’に登録されている状態（ｐ，ｓ）の各々について、
（２−１）前記状態ｐが、前記有限状態木オートマンＡの終了状態であって、前記状態（ｐ，ｓ）と同値関係にある状態が、前記有限状態木オートマンＡ’の終了状態として登録されていない場合、前記状態（ｐ，ｓ）を、前記有限状態木オートマンＡ’の終了状態として登録し、
（２−２）前記有限状態木オートマンＡにおける、状態ｐを含む状態ｐ１，・・・，ｐｋの組み合わせを始点とする辺の各々に対し、
（２−２−１）前記状態（ｐ，ｓ）を含む、状態（ｐ１、ｓ１），・・・，状態（ｐｋ、ｓｋ）の組み合わせを各々作成し、
（２−２−２）前記作成された組み合わせの各々について、
（２−２−２−１）前記組み合わせの状態（ｐ１、ｓ１），・・・，状態（ｐｋ、ｓｋ）を始点とする辺から遷移する新たな状態（ｑ、ｔ）を作成すると共に、前記組み合わせの状態（ｐ１、ｓ１），・・・，状態（ｐｋ、ｓｋ）を始点とする辺を生成し、
（２−２−２−２）前記生成された辺が、前記有限状態木オートマンＡ’に登録されている辺に対して、曖昧性を作らない場合に、前記生成された辺を、前記有限状態木オートマンＡ’の辺として登録し、前記作成された新たな状態（ｑ、ｔ）が、前記有限状態木オートマンＡ’に登録されている状態の集合に含まれない場合に、前記新たな状態（ｑ、ｔ）を、前記有限状態木オートマンＡ’の状態として登録する曖昧性解消部、及び
前記有限状態木オートマンＡ’を出力する出力部
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、曖昧性解消装置、方法、及びプログラムに係り、特に、曖昧性を解消した有限状態木オートマトンを生成する曖昧性解消装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
非特許文献１では、有限状態オートマトン(Finite State Automaton; FSA) の曖昧性を解消する演算が提案されている。ＦＳＡが曖昧性を持つとは、同じ入力を受理できる２つ以上の異なる経路が存在するときをいう。ＦＳＡが曖昧性を持つと、オートマトンの動作は非効率的となる。非特許文献１のアルゴリズムでは、同じ記号列を読み込んで到達できる状態同士を関係Ｒとして定義し、そこから先の遷移で合流がある場合、それらのうちどちらか一方の遷移を封鎖して曖昧性を解消する。
【０００３】
一方、ＦＳＡを一般化した有限状態木オートマトン(Finite State Tree Automaton; FTA) と呼ばれるものがある。ＦＴＡでは文字列ではなく、木を入力として受け取ることができる。ＦＳＡと同様に、ＦＴＡにも曖昧性の問題は存在する。従来、ＦＴＡにおいて、曖昧性を解消する方法に決定化（例えば、非特許文献２を参照。）と呼ばれる演算がある。決定化はある状態から同じ記号での遷移を排除する演算であり、その結果として、曖昧性を解消することができる。しかし、決定化によってできるＦＴＡの状態数は、元のＦＴＡの状態数Ｎに対して、２Ｎになることが知られている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Mehryar Mohri., “A disambiguation algorithm for finite automata and functional transducers.”, In Implementation and Application of Automata, Springer, 2012, p.265‐277
【非特許文献２】Jonathan May and Kevin Knight., “A better n-best list: Practical determinization of weighted finite tree automata.”, In In Proceedings of the HLT-NAACL, Association for Computational Linguistics, 2006, p.351‐358.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上記非特許文献１の曖昧性解消演算アルゴリズムでは、その適用範囲が有限状態オートマトン（ＦＳＡ）だけに限定されていた。
【０００６】
本発明では、上記事情に鑑みて成されたものであり、曖昧性を解消した有限状態木オートマトンを生成することできる曖昧性解消装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するために、本発明に係る曖昧性解消装置は、入力された有限状態木オートマンＡの曖昧性を解消した有限状態木オートマトンＡ’であって、前記有限状態木オートマンＡの状態ｐと状態集合ｓとのペアに対する状態（ｐ，ｓ）を有する有限状態木オートマトンＡ’を生成する曖昧性解消装置であって、入力された有限状態木オートマンＡを受け付ける入力部と、（１）前記有限状態木オートマンＡの初期状態ｉと前記初期状態ｉからなる状態集合とのペアに対する、前記有限状態木オートマンＡ’の初期状態（ｉ，｛ｉ｝）を登録し、（２）前記有限状態木オートマンＡ’に登録されている状態（ｐ，ｓ）の各々について、（２−１）前記状態ｐが、前記有限状態木オートマンＡの終了状態であって、前記状態（ｐ，ｓ）と同値関係にある状態が、前記有限状態木オートマンＡ‘の終了状態として登録されていない場合、前記状態（ｐ，ｓ）を、前記有限状態木オートマンＡ’の終了状態として登録し、（２−２）前記有限状態木オートマンＡにおける、状態ｐを含む状態ｐ１，・・・，ｐｋの組み合わせを始点とする辺の各々に対し、（２−２−１）前記状態（ｐ，ｓ）を含む、状態（ｐ１、ｓ１），・・・，状態（ｐｋ、ｓｋ）の組み合わせを各々作成し、（２−２−２）前記作成された組み合わせの各々について、（２−２−２−１）前記組み合わせの状態（ｐ１、ｓ１），・・・，状態（ｐｋ、ｓｋ）を始点とする辺から遷移する新たな状態（ｑ、ｔ）を作成すると共に、前記組み合わせの状態（ｐ１、ｓ１），・・・，状態（ｐｋ、ｓｋ）を始点とする辺を生成し、（２−２−２−２）前記生成された辺が、前記有限状態木オートマンＡ’に登録されている辺に対して、曖昧性を作らない場合に、前記生成された辺を、前記有限状態木オートマンＡ’の辺として登録し、前記作成された新たな状態（ｑ、ｔ）が、前記有限状態木オートマンＡ’に登録されている状態の集合に含まれない場合に、前記新たな状態（ｑ、ｔ）を、前記有限状態木オートマンＡ’の状態として登録する曖昧性解消部と、前記有限状態木オートマンＡ’を出力する出力部と、を含んで構成されている。
【０００８】
本発明に係る曖昧性解消方法は、入力部、曖昧性解消部、及び出力部を含み、入力された有限状態木オートマンＡの曖昧性を解消した有限状態木オートマトンＡ’であって、前記有限状態木オートマンＡの状態ｐと状態集合ｓとのペアに対する状態（ｐ，ｓ）を有する有限状態木オートマトンＡ’を生成する曖昧性解消装置における曖昧性解消方法であって、前記入力部が、入力された有限状態木オートマンＡを受け付けるステップと、前記曖昧性解消部が、（１）前記有限状態木オートマンＡの初期状態ｉと前記初期状態ｉからなる状態集合とのペアに対する、前記有限状態木オートマンＡ’の初期状態（ｉ，｛ｉ｝）を登録し、（２）前記有限状態木オートマンＡ’に登録されている状態（ｐ，ｓ）の各々について、（２−１）前記状態ｐが、前記有限状態木オートマンＡの終了状態であって、前記状態（ｐ，ｓ）と同値関係にある状態が、前記有限状態木オートマンＡ’の終了状態として登録されていない場合、前記状態（ｐ，ｓ）を、前記有限状態木オートマンＡ’の終了状態として登録し、（２−２）前記有限状態木オートマンＡにおける、状態ｐを含む状態ｐ１，・・・，ｐｋの組み合わせを始点とする辺の各々に対し、（２−２−１）前記状態（ｐ，ｓ）を含む、状態（ｐ１、ｓ１），・・・，状態（ｐｋ、ｓｋ）の組み合わせを各々作成し、（２−２−２）前記作成された組み合わせの各々について、（２−２−２−１）前記組み合わせの状態（ｐ１、ｓ１），・・・，状態（ｐｋ、ｓｋ）を始点とする辺から遷移する新たな状態（ｑ、ｔ）を作成すると共に、前記組み合わせの状態（ｐ１、ｓ１），・・・，状態（ｐｋ、ｓｋ）を始点とする辺を生成し、（２−２−２−２）前記生成された辺が、前記有限状態木オートマンＡ’に登録されている辺に対して、曖昧性を作らない場合に、前記生成された辺を、前記有限状態木オートマンＡ’の辺として登録し、前記作成された新たな状態（ｑ、ｔ）が、前記有限状態木オートマンＡ’に登録されている状態の集合に含まれない場合に、前記新たな状態（ｑ、ｔ）を、前記有限状態木オートマンＡ’の状態として登録するステップと、前記出力部が、前記有限状態木オートマンＡ’を出力するステップと、を含む。
【０００９】
また、本発明のプログラムは、入力された有限状態木オートマンＡの曖昧性を解消した有限状態木オートマトンＡ’であって、前記有限状態木オートマンＡの状態ｐと状態集合ｓとのペアに対する状態（ｐ，ｓ）を有する有限状態木オートマトンＡ’を生成するためのプログラムであって、コンピュータを、入力された有限状態木オートマンＡを受け付ける入力部、（１）前記有限状態木オートマンＡの初期状態ｉと前記初期状態ｉからなる状態集合とのペアに対する、前記有限状態木オートマンＡ’の初期状態（ｉ，｛ｉ｝）を登録し、（２）前記有限状態木オートマンＡ’に登録されている状態（ｐ，ｓ）の各々について、（２−１）前記状態ｐが、前記有限状態木オートマンＡの終了状態であって、前記状態（ｐ，ｓ）と同値関係にある状態が、前記有限状態木オートマンＡ’の終了状態として登録されていない場合、前記状態（ｐ，ｓ）を、前記有限状態木オートマンＡ’の終了状態として登録し、（２−２）前記有限状態木オートマンＡにおける、状態ｐを含む状態ｐ１，・・・，ｐｋの組み合わせを始点とする辺の各々に対し、（２−２−１）前記状態（ｐ，ｓ）を含む、状態（ｐ１、ｓ１），・・・，状態（ｐｋ、ｓｋ）の組み合わせを各々作成し、（２−２−２）前記作成された組み合わせの各々について、（２−２−２−１）前記組み合わせの状態（ｐ１、ｓ１），・・・，状態（ｐｋ、ｓｋ）を始点とする辺から遷移する新たな状態（ｑ、ｔ）を作成すると共に、前記組み合わせの状態（ｐ１、ｓ１），・・・，状態（ｐｋ、ｓｋ）を始点とする辺を生成し、（２−２−２−２）前記生成された辺が、前記有限状態木オートマンＡ’に登録されている辺に対して、曖昧性を作らない場合に、前記生成された辺を、前記有限状態木オートマンＡ’の辺として登録し、前記作成された新たな状態（ｑ、ｔ）が、前記有限状態木オートマンＡ’に登録されている状態の集合に含まれない場合に、前記新たな状態（ｑ、ｔ）を、前記有限状態木オートマンＡ’の状態として登録する曖昧性解消部、及び前記有限状態木オートマンＡ’を出力する出力部として機能させるためのプログラムである。
【発明の効果】
【００１０】
以上説明したように、本発明の曖昧性解消装置、方法、及びプログラムによれば、有限状態木オートマンＡ’に登録されている状態（ｐ，ｓ）の各々について、有限状態木オートマンＡにおける、状態ｐを含む状態ｐ１，・・・，ｐｋの組み合わせを始点とする辺の各々に対し、状態（ｐ，ｓ）を含む、状態（ｐ１、ｓ１），・・・，状態（ｐｋ、ｓｋ）の組み合わせを各々作成し、作成された組み合わせの各々について、（２−２−２−１）組み合わせの状態（ｐ１、ｓ１），・・・，状態（ｐｋ、ｓｋ）を始点とする辺から遷移する新たな状態（ｑ、ｔ）を作成すると共に、前記組み合わせの状態（ｐ１、ｓ１），・・・，状態（ｐｋ、ｓｋ）を始点とする辺を生成し、（２−２−２−２）生成された辺が、有限状態木オートマンＡ’に登録されている辺に対して、曖昧性を作らない場合に、生成された辺を、有限状態木オートマンＡ’の辺として登録し、作成された新たな状態（ｑ、ｔ）が、有限状態木オートマンＡ’に登録されている状態の集合に含まれない場合に、新たな状態（ｑ、ｔ）を、有限状態木オートマンＡ’の状態として登録することにより、曖昧性を解消した有限状態木オートマトンＡ’を生成することができる、という効果が得られる。
【図面の簡単な説明】
【００１１】
【図１】有限状態木オートマンと有限状態木オートマンに入力される木との例を示す図である。
【図２】本発明の実施の形態に係る曖昧性解消装置の機能的構成を示すブロック図である。
【図３】本発明の実施の形態に係る一般化曖昧性解消演算アルゴリズムの疑似コードを示す図である。
【図４】本発明の実施の形態に係る曖昧性解消装置における曖昧性解消処理ルーチンを示すフローチャート図である。
【図５】本発明の実施の形態に係る曖昧性解消装置における曖昧性解消処理ルーチンを示すフローチャート図である。
【図６】有限状態木オートマンＡの曖昧性を解消した有限状態木オートマトンＡ’の例を示す図である。
【発明を実施するための形態】
【００１２】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１３】
＜本発明の実施の形態の概要＞
本発明の実施の形態では、上記非特許文献１に記載の曖昧性解消演算アルゴリズムを、有限状態木オートマトン（ＦＴＡ）へも適用可能な形に一般化する。本発明の実施の形態における一般化曖昧性解消演算アルゴリズムは、有限状態木オートマトン（ＦＴＡ）から同じ木構造を排除するためのアルゴリズムである。提案するアルゴリズムは、通常のＦＳＡへも適用可能であるため、上記非特許文献１に記載の従来のアルゴリズムよりも適用範囲が広い。
【００１４】
図１（Ａ）に有限状態木オートマトン（ＦＴＡ）の例を示す。図１（Ａ）の状態１と状態２とから、状態４への遷移、状態１と状態３とから状態４への遷移のように、複数の状態で構成された始点から次の状態への遷移が許されるため、ＦＴＡでは木構造を表現することができる。図１（Ａ）のＦＴＡでは、図１（Ｂ）に示すような木構造を受理することができる。図１（Ａ）のＦＴＡには、図１（Ｂ）の左側の木構造Ｄ（Ａ Ｂ）を受理できる経路が次のように２つ存在している。
【００１５】
Ａ（０）→１，Ｂ（０）→２，Ｄ（１，２）→４
Ａ（０）→１，Ｂ（０）→３，Ｄ（１，３）→４
【００１６】
よって、上記図１（Ａ）に示すＦＴＡは曖昧性を持つことがわかる。提案するアルゴリズムは、異なる経路は必ず異なる木構造を受理することが保証されるように変換を行う。また、変換後のＦＴＡは、変換前のＦＴＡで受理することができる全ての木構造を受理することができる（等価な表現能力を保持している）。また、変換後のＦＴＡの状態数は、元のＦＴＡの状態数Ｎに対して、最悪の場合でも、
【００１７】
【数１】
2016048462.tif 000003
【００１８】
に抑えられる。
【００１９】
次に、本発明の実施の形態に係る曖昧性解消装置の構成について説明する。なお、本発明の実施の形態では、入力された有限状態木オートマンＡの曖昧性を解消した有限状態木オートマトンＡ’であって、有限状態木オートマンＡの状態ｐと状態集合ｓとのペアに対する状態（ｐ，ｓ）を有する有限状態木オートマトンＡ’を生成する曖昧性解消装置に、本発明を適用させた場合を例に説明する。
【００２０】
＜曖昧性解消装置の構成＞
本発明の実施の形態に係る曖昧性解消装置について説明する。図２に示すように、本発明の実施の形態に係る曖昧性解消装置１００は、ＣＰＵと、ＲＡＭと、後述する曖昧性解消処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この曖昧性解消装置１００は、機能的には図２に示すように入力部１０と、曖昧性解消部２０と、出力部３０とを備えている。
【００２１】
入力部１０は、有限状態木オートマトン（ＦＴＡ）Ａを受け付ける。なお、本実施の形態では、有限状態木オートマトンＡ＝（Σ，Ｑ，ｉ，Ｆ，Ｅ）を以下のように定義する。
【００２２】
Σはランク付きアルファベットであり、Ｑは状態の有限集合であり、ｉ∈Ｑは初期状態であり、Ｆ⊆Ｑは終了状態の集合であり、Ｅ⊆Ｑ×・・・×Ｑ×Σ（ｋ）×Ｑはｋ個の状態から成るベクトルを入力にして次の状態へと遷移する辺の集合である。また、辺はσ（ｑ１，...，ｑｋ）→ｑ（ｑ，ｑ１，...，ｑｋ∈Ｑ，σ∈Σ（ｋ））として書く。
【００２３】
例えば、上記図１（Ａ）に示すオートマトンは、次の要素から構成される。
【００２４】
Σ＝｛Ａ（１），Ｂ（１），Ｃ（１），Ｄ（２）｝，
Ｑ＝｛０，１，２，３，４｝
ｉ＝０，
Ｆ＝｛４｝，
Ｅ＝｛Ａ（０）→１，Ｂ（０）→２，Ｃ（０）→３，Ｂ（０）→３，Ｄ（１，２）→４，Ｄ（１，３）→４｝
【００２５】
曖昧性解消部２０は、入力部１０によって受け付けた有限状態木オートマンＡから、有限状態木オートマンＡの曖昧性を解消した有限状態木オートマトンＡ’であって、有限状態木オートマンＡの状態ｐと状態集合ｓとのペアに対する状態（ｐ，ｓ）を有する有限状態木オートマトンＡ’を生成する。
【００２６】
曖昧性解消部２０において実行される一般化曖昧性解消演算アルゴリズムの疑似コードを、図３に示す。図３に示したＡｌｇｏｒｉｔｈｍ１は、有限状態木オートマトン（ＦＴＡ）を適用可能な形に一般化した一般化曖昧性解消演算アルゴリズムである。このアルゴリズムはＦＴＡ［Ａ］＝（Σ，Ｑ，ｉ，Ｆ，Ｅ）を入力として、ＦＴＡ［Ａ’］＝（Σ，Ｑ’，ｉ’； Ｆ’；Ｅ’） を出力する。なお、図３に示す筆記体の「Ｑ」は、以下「Ｑｕｅｕｅ」と称する。
【００２７】
図３に示したアルゴリズムではＡ’における２つの状態に対して、同値関係Ｒを定義する。Ｒは２つの状態が同じ木で到達できる実行を持つときに関係を持つ。疑似コードの２行目では、有限状態木オートマンＡと有限状態木オートマンＡとの積集合を計算し、その結果から終了状態へ到達できない状態を排除したＦＴＡをＢに代入する。なお、ＦＴＡの積集合演算はＯ（｜Ｑ｜２）で計算でき、上記図３に示した疑似コード内のｐｒｕｎｅＵｓｅｌｅｓｓＳｔａｔｅｓ（・）は状態数に対して線形時間で計算できる。Ｂに存在する状態は（ｑ，ｒ）（ｑ，ｒ∈Ｑ）の形をとり、ｑとｒは同じ木で到達できる実行を持ち、そこから同じ木で終了状態に至る実行を共有するため、定数時間でこのことをチェックするのにＢを使う。
【００２８】
曖昧性解消部２０は、まず、以下の処理（１）を行う。なお、疑似コードにおけるＭ及びｃａｎｄは情報が格納されるリストを表し、Ａｄｄはリストの最後尾への格納処理を表し、Ｇｅｔ（Ｍ，ｖ）はリストＭのｖ番目の要素の読み出し処理を表す。
処理（１）では、有限状態木オートマンＡの初期状態ｉと当該初期状態ｉからなる状態集合とのペアに対する状態（ｉ，｛ｉ｝）を、有限状態木オートマンＡ’の初期状態ｉ’として登録する。
具体的には、曖昧性解消部２０は、上記図３に示した疑似コードの３行目において、Ａ’の初期状態ｉ’を状態（ｉ，｛ｉ｝）として初期化する。また、Ａ’の状態は（ｐ，ｓ）（ｐ∈Ｑ，ｓ∈Ｑ＊）の形をとる。ｓは同じ木によって到達できる状態の集合とする。ｉはε遷移によって、ｉに到達すると考えることができる。なお、同値関係Ｒの記号について、例えば、疑似コードにおける（ｐ’，ｓ’）Ｒ（ｐ，ｓ）は、状態（ｐ，ｓ）と状態（ｐ’，ｓ’）とが同値関係にあることを示す。
上記図３に示した疑似コードの４行目では、新たな状態の集合Ｑ’に、５行目ではキューＱｕｅｕｅに状態ｉ’を追加する。６行目では関係Ｒに（ｉ’，ｉ’）を追加する。７行目では、リストＭ（ｉ）に状態ｉ’を追加する。リストＭ（ｐ）は（ｐ，・）∈Ｑ’を読み出すために構築する。
【００２９】
次に、曖昧性解消部２０は、以下の処理（２）を行う。
処理（２）では、有限状態木オートマンＡ’に登録されている状態（ｐ，ｓ）の各々について、以下の処理（２−１）、（２−２）を行う。
処理（２−１）では、状態ｐが、有限状態木オートマンＡの終了状態であって、状態（ｐ，ｓ）と同値関係にある状態が、有限状態木オートマンＡ’の終了状態として登録されていない場合、当該状態（ｐ，ｓ）を、有限状態木オートマンＡ’の終了状態として登録する。
【００３０】
具体的には、曖昧性解消部２０は、上記図３に示した疑似コードの８行目から３３行目において、新たな状態と辺を構築する繰り返し処理を行う。疑似コードの９行目から１２行目では８行目でキューから取り出し状態（ｐ，ｓ）が終了状態であるかをチェックし、Ｆ’に登録する。ただし、（ｐ’，ｓ’）Ｒ（ｐ，ｓ）が存在する、すなわち、同じ木で終了状態に至る（ｐ’，ｓ’）がすでに存在する場合は（ｐ，ｓ）をＦ’に登録しない。
【００３１】
処理（２−２）では、有限状態木オートマンＡにおける、状態ｐを含む状態ｐ１，・・・，ｐｋの組み合わせを始点とする辺の各々に対し、以下の処理（２−２−１）、（２−２−１）を行う。
処理（２−２−１）では、当該状態（ｐ，ｓ）を含む、状態（ｐ１、ｓ１），・・・，状態（ｐｋ、ｓｋ）の組み合わせを各々作成する。
具体的には、疑似コードの１３行目から３２行目では、ｐから出る辺σ（ｋ）（ｐ１，．．．，ｐ，．．．，ｐｋ）→ｑごとに処理が進む。１４行目のＧｅｔＣａｎｄｉｄａｔｅ関数では、ｐ１，．．．，ｐｋに対してすでに構築されたＡ’の状態をリストＭ（・）の先頭から読み出す（３９から４１行目）。ただし、ｐに対しては（ｐ，ｓ）を使う。４０行目の１はｋ次元の数値ベクトルで、各次元の値は全て１をとる。
また、疑似コードの３０行目のＡｐｐｅｎｄＮｅｘｔ関数では、状態ｐ１，．．．，ｐ，．．．，ｐｋのｐ 以外の状態に対して、リストＭに登録された次の状態へ更新することで、Ａ’におけるｋ個の状態集合とｋ次元の数値ベクトルの新たなペアを作り出す。ＡｐｐｅｎｄＮｅｘｔ関数の４８行目のｂｉはｉ次元目だけが１、その他の次元は全て０を持つｋ次元の数値ベクトルを表す。４９行目から５４行目では、ｉ番目の状態をＭ（ｐｉ）に登録されている次の状態に置き換えることで、新たなペアをｃａｎｄに追加している。
【００３２】
処理（２−２−２）では、処理（２−２−１）で作成された組み合わせの各々について、以下の処理（２−２−２−１）、（２−２−２−２）を行う。
処理（２−２−２−１）では、当該組み合わせの状態（ｐ１、ｓ１），・・・，状態（ｐｋ、ｓｋ）を始点とする辺から遷移する新たな状態（ｑ、ｔ）を作成すると共に、当該組み合わせの状態（ｐ１、ｓ１），・・・，状態（ｐｋ、ｓｋ）を始点とする辺を生成する。
処理（２−２−２−２）では、処理（２−２−２−１）で生成された辺が、有限状態木オートマンＡ’に登録されている辺に対して、曖昧性を作らない場合に、生成された辺を、有限状態木オートマンＡ’の辺として登録し、処理（２−２−２−１）で作成された新たな状態（ｑ、ｔ）が、有限状態木オートマンＡ’に登録されている状態の集合に含まれない場合に、新たな状態（ｑ、ｔ）を、有限状態木オートマンＡ’の状態として登録する。
具体的には、疑似コードの１５行目から３１行目の処理において、ｃａｎｄに登録されたＡ’におけるｋ個の状態集合とｋ次元の数値ベクトルのペアがなくなるまで繰り返す。１７行目にあるδ（ｓ，σ）は、状態集合ｓに含まれる全ての状態から記号σで遷移できる状態の集合を表す。１７行目で作られる状態集合ｔは各状態集合ｓ１，．．．，ｓ，．．．，ｓｋから記号σ（ｋ）で遷移できる状態集合の積集合をとったものである。
【００３３】
また、上記図３に示した疑似コードの１８行目から２９行目において、新たな状態（ｑ，ｔ）と辺σ（ｋ）（（ｐ１，ｓ１），．．．，（ｐ，ｓ），．．．，（ｐｋ，ｓｋ））→（ｑ，ｔ）の登録を行う。ただし、１８行目で（ｐ’１，s’１）Ｒ（ｐ１，ｓ１）．．．（ｐ’，ｓ’）Ｒ（ｐ，ｓ）．．．（ｐ’ｋ，ｓ’ｋ）Ｒ（ｐｋ，ｓｋ）を持つ辺σ（ｋ）（（ｐ’１，ｓ’１），．．．，（ｐ’，ｓ’），．．．，（ｐ’ｋ，ｓ’ｋ））→（ｑ，ｔ）がＥ’にすでに存在しないかをチェックし、存在しない場合のみ２４行目でＥ’に登録を行う。１９行目から２３行目では（ｑ，ｔ）がＱ’ に登録されていないとき、Ｑ’，Ｑｕｅｕｅ，Ｍ（ｑ）への登録を行う。
【００３４】
２５行目から２８行目では（ｑ，ｔ）について関係Ｒを構築できるか調べる。（（ｐ’１，ｓ’１）Ｒ（ｐ１，ｓ１）．．．（ｐ’ ，ｓ’）Ｒ（ｐ，ｓ）．．．（ｐ’ｋ，ｓ’ｋ）Ｒ（ｐｋ，ｓｋ））を持つ辺（ｋ）（（ｐ’１，ｓ’１），．．．，（ｐ’ ，ｓ’），．．．，（ｐ’ｋ，ｓ’ｋ））→（ｑ’ ，ｔ’） があるとき、（ｑ，ｔ）と（ｑ’ ，ｔ’）は同じ木で到達できることを意味する。よって、２７行目でそれらを関係Ｒに登録する。
【００３５】
出力部３０は、曖昧性解消部２０によって登録された有限状態木オートマンＡ’を結果として出力する。
【００３６】
＜曖昧性解消装置の作用＞
次に、本発明の実施の形態に係る曖昧性解消装置１００の作用について説明する。まず、入力部１０により、有限状態木オートマンＡが入力される。そして、曖昧性解消装置１００のＲＯＭに記憶されたプログラムを、ＣＰＵが実行することにより、図４及び図５に示す曖昧性解消処理ルーチンが実行される。
【００３７】
まず、ステップＳ１００において、入力部１０によって、有限状態木オートマトンＡを受け付ける。
【００３８】
次に、ステップＳ１０１において、上記ステップＳ１００で受け付けた有限状態木オートマトンＡに基づいて、有限状態木オートマトンＡと有限状態木オートマトンＡとの積集合を計算し、その結果から終了状態へ到達できない状態を排除したＦＴＡをＢに代入する。
【００３９】
次に、ステップＳ１０２において、曖昧性解消部２０によって、有限状態木オートマンＡ’の初期状態（ｉ，｛ｉ｝）を、ｉ’，Ｑ’，Ｑｕｅｕｅ，Ｍ（ｉ）へ登録する。また、｛（ｉ’，ｉ’）｝をＲへ登録する。
【００４０】
次に、ステップＳ１０４において、曖昧性解消部２０によって、上記ステップＳ１０２で登録処理が行われたＱｕｅｕｅ又は後述するステップＳ１２４で前回登録処理が行われたＱｕｅｕｅが空集合であるか否かを判定する。Ｑｕｅｕｅが空集合である場合には、ステップＳ１３４へ移行する。一方、Ｑｕｅｕｅが空集合でない場合には、ステップＳ１０６へ進む。
【００４１】
次に、ステップＳ１０６において、曖昧性解消部２０によって、上記ステップＳ１０２で登録処理が行われたＱｕｅｕｅ又は後述するステップＳ１２４で前回登録処理が行われたＱｕｅｕｅから、状態（ｐ，ｓ）を取り出す。
【００４２】
ステップＳ１０８において、曖昧性解消部２０によって、上記ステップＳ１０６で取り出された状態（ｐ，ｓ）と同値関係にある有限状態木オートマンＡ’の状態（ｐ’，ｓ’）において、ｐ∈Ｆかつ
【００４３】
【数２】
2016048462.tif 000004
【００４４】
であるか否かを判定条件とし、上記ステップＳ１０６で取り出された状態（ｐ，ｓ）を終了状態とすることができるか否かを判定する。上記判定条件を満たす場合には、状態（ｐ，ｓ）を終了状態とすることができると判定し、ステップＳ１１０へ進む。一方、上記判定条件を満たさない場合には、状態（ｐ，ｓ）を終了状態とすることができないと判定し、ステップＳ１１２へ移行する。
【００４５】
ステップＳ１１０において、上記ステップＳ１０６で取り出された状態（ｐ，ｓ）をＦ’に登録する。
【００４６】
ステップＳ１１２において、曖昧性解消部２０によって、有限状態木オートマンＡにおいて、上記ステップＳ１０６で取り出された状態（ｐ，ｓ）の状態ｐから出る１つの辺を設定する。
【００４７】
ステップＳ１１４において、曖昧性解消部２０によって、上記ステップＳ１１２で設定された辺の各始点に対応する状態の組み合わせ（ｐ１，．．．，ｐ，．．．，ｐｋ）に基づいて、上記ステップＳ１０２で登録処理が行われたＭ、又は後述するステップＳ１２４で前回登録処理が行われたＭの先頭から、状態集合｛（ｐ１，ｓ１），．．．，（ｐ，ｓ），．．．，（ｐｋ，ｓｋ）｝を読み出し、状態集合｛（ｐ１，ｓ１），．．．，（ｐ，ｓ），．．．，（ｐｋ，ｓｋ）｝と数値ベクトルとのペアをｃａｎｄに登録する。
【００４８】
ステップＳ１１６において、曖昧性解消部２０によって、上記ステップＳ１１４で登録処理が行われたｃａｎｄが空であるか否かを判定する。ｃａｎｄが空である場合には、ステップＳ１３２へ移行する。一方、ｃａｎｄが空でない場合には、ステップＳ１１８へ進む。
【００４９】
ステップＳ１１８において、曖昧性解消部２０によって、上記ステップＳ１１４で登録処理が行われたｃａｎｄから、状態集合｛（ｐ１，ｓ１），．．．，（ｐ，ｓ），．．．，（ｐｋ，ｓｋ）｝と数値ベクトルとのペアを取り出し、状態集合｛（ｐ１，ｓ１），．．．，（ｐ，ｓ），．．．，（ｐｋ，ｓｋ）｝と数値ベクトルとのペアに基づいて、新しい状態（ｑ，ｔ）及び新しい辺σ（ｋ）（（ｐ１，ｓ１），．．．，（ｐ，ｓ），．．．，（ｐｋ，ｓｋ））→（ｑ，ｔ）を構築する。
【００５０】
ステップＳ１２０において、曖昧性解消部２０によって、上記ステップＳ１１８で構築された新しい辺σ（ｋ）（（ｐ１，ｓ１），．．．，（ｐ，ｓ），．．．，（ｐｋ，ｓｋ））→（ｑ，ｔ）が曖昧性を作るか否かを判定する。新しい辺σ（ｋ）（（ｐ１，ｓ１），．．．，（ｐ，ｓ），．．．，（ｐｋ，ｓｋ））→（ｑ，ｔ）が曖昧性を作る場合には、ステップＳ１３０へ移行する。一方、新しい辺σ（ｋ）（（ｐ１，ｓ１），．．．，（ｐ，ｓ），．．．，（ｐｋ，ｓｋ））→（ｑ，ｔ）が曖昧性を作らない場合には、ステップＳ１２２へ進む。
【００５１】
ステップＳ１２２において、曖昧性解消部２０によって、上記ステップＳ１１８で構築された新しい状態（ｑ，ｔ）が、Ｑ’に登録されているか否かを判定する。新しい状態（ｑ，ｔ）が、Ｑ’に登録されていない場合には、ステップＳ１２４へ進む。一方、新しい状態（ｑ，ｔ）が、Ｑ’に登録されている場合には、ステップＳ１２６へ移行する。
【００５２】
ステップＳ１２４において、曖昧性解消部２０によって、上記ステップＳ１１８で構築された新しい状態（ｑ，ｔ）をＱ’、Ｑｕｅｕｅ、Ｍに登録する。
【００５３】
ステップＳ１２６において、曖昧性解消部２０によって、上記ステップＳ１１８で構築された新しい辺σ（ｋ）（（ｐ１，ｓ１），．．．，（ｐ，ｓ），．．．，（ｐｋ，ｓｋ））→（ｑ，ｔ）をＥ’に登録する。
【００５４】
ステップＳ１２８において、曖昧性解消部２０によって、上記ステップＳ１１８で構築された新しい状態（ｑ，ｔ）と、同値関係Ｒを構築することができる状態が存在する場合には、同値関係Ｒを構築する。
【００５５】
ステップＳ１３０において、曖昧性解消部２０によって、状態（ｐ１，．．．，ｐ，．．．，ｐｋ）のｐ 以外の状態について、Ｍに登録された次の状態へ更新することで、Ａ’におけるｋ個の状態集合｛（ｐ１，ｓ１），．．．，（ｐ，ｓ），．．．，（ｐｋ，ｓｋ）｝とｋ次元の数値ベクトルの新たなペアを作成し、作成されたペアをｃａｎｄへ登録する。
【００５６】
ステップＳ１３２において、曖昧性解消部２０によって、上記ステップＳ１１２で設定された状態ｐから出る全ての辺について、上記ステップＳ１１２〜Ｓ１３０の処理を実行したか否かを判定する。状態ｐから出る全ての辺について、上記ステップＳ１１２〜Ｓ１３０の処理を実行した場合には、ステップＳ１０４へ戻る。一方、状態ｐから出る全ての辺について、上記ステップＳ１１２〜Ｓ１３０の処理を実行していない場合には、ステップＳ１１２へ戻る。
【００５７】
ステップＳ１３４において、出力部３０によって、曖昧性が解消された有限状態木オートマンＡ’を結果として出力して、曖昧性解消処理ルーチンを終了する。
【００５８】
以上説明したように、本発明の実施の形態に係る曖昧性解消装置によれば、有限状態木オートマンＡ’に登録されている状態（ｐ，ｓ）の各々について、有限状態木オートマンＡにおける、状態ｐを含む状態ｐ１，・・・，ｐｋの組み合わせを始点とする辺の各々に対し、（２−２−１）状態（ｐ，ｓ）を含む、状態（ｐ１、ｓ１），・・・，状態（ｐｋ、ｓｋ）の組み合わせを各々作成し、（２−２−２）作成された組み合わせの各々について、（２−２−２−１）組み合わせの状態（ｐ１、ｓ１），・・・，状態（ｐｋ、ｓｋ）を始点とする辺から遷移する新たな状態（ｑ、ｔ）を作成すると共に、前記組み合わせの状態（ｐ１、ｓ１），・・・，状態（ｐｋ、ｓｋ）を始点とする辺を生成し、生成された辺が、有限状態木オートマンＡ’に登録されている辺に対して、曖昧性を作らない場合に、生成された辺を、有限状態木オートマンＡ’の辺として登録し、作成された新たな状態（ｑ、ｔ）が、有限状態木オートマンＡ’に登録されている状態の集合に含まれない場合に、新たな状態（ｑ、ｔ）を、有限状態木オートマンＡ’の状態として登録することにより、曖昧性を解消した有限状態木オートマトンＡ’を生成することができる。
【００５９】
また、本発明の実施の形態は、入力された有限状態木オートマトン（ＦＴＡ）に対して、元のＦＴＡと等価で、かつ曖昧性のないＦＴＡを構築することができる。
【００６０】
また、有限状態オートマトン（ＦＳＡ）にも適用可能である（上記非特許文献１の従来法を包含している）。
【００６１】
また、従来手法である決定化（上記非特許文献２を参照）では、最悪の場合、状態数が２Ｎに増幅するのに対し、本発明の実施の形態では
【００６２】
【数３】
2016048462.tif 000005
【００６３】
に抑えられる。
【００６４】
また、本発明の実施の形態が従来法である上記非特許文献１のアルゴリズムと異なる点は、木が扱えることにある。木を扱うためには、辺の始点が複数あることをアルゴリズムに考慮する必要がある。そのため、本発明の実施の形態における一般化曖昧性解消演算アルゴリズムのＧｅｔＣａｎｄｉｄａｔｅ関数、及びＡｐｐｅｎｄＮｅｘｔ関数は、従来法には存在しなかった。また、上記図３に示した疑似コード１７、１８、２５行目の操作でも、始点が複数あることを考慮した処理になっている。
【００６５】
［実施例］
図６に、上記図１に示したＦＴＡに、一般化曖昧性解消演算アルゴリズムを適用してできるＦＴＡを示す。点線で表された遷移は、どちらか一方のみが構築される。どちらの遷移が構築されるかは、一般化曖昧性解消演算アルゴリズムで使われている優先度付きキューＱｕｅｕｅの設計に依存する。図６からもわかるように、同じ木構造を持つ経路は１つだけとなっている。
【００６６】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【００６７】
上述の曖昧性解消装置１００は、内部にコンピュータシステムを有しているが、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
【００６８】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。
【符号の説明】
【００６９】
１０   入力部
２０   曖昧性解消部
３０   出力部
１００ 曖昧性解消装置
【図１】
2016048462.tif 000006
【図２】
2016048462.tif 000007
【図４】
2016048462.tif 000008
【図５】
2016048462.tif 000009
【図６】
2016048462.tif 000010
【図３】
2016048462.tif 000011