On the Computational Complexity of Hidden Markov Model Identification
The paper investigates whether there is a complete algorithm to determine if a Hidden Markov Model (HMM) is identifiable and what its computational complexity class is. By studying various identification types, including deterministic and generic, the authors prove that all studied notions of HMM identifiability are decidable in PSPACE. They also establish hardness results for certain identification problems.