arXiv cs.LG· Markel Zubia, Nils Jansen·· 6 小时前AI 评分12
HMM 可识别性判定问题的计算复杂度研究
On the Computational Complexity of Hidden Markov Model Identification
AI 导读
针对隐马尔可夫模型（HMM）可识别性判定，研究证明确定性、通用、全局、局部、状态置换不变及有限字母表等各类可识别性判定问题均可在 PSPACE 内判定，方法是将问题归约到实数理论的不同量词交替层级。研究进一步表明，简单参数化族下的确定性变体已是 coETR-hard，因而也是 coNP-hard。
来源：arXiv cs.LG · arxiv.org