𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the complexity of minimizing probabilistic and quantum automata

✍ Scribed by Paulo Mateus; Daowen Qiu; Lvzhou Li


Book ID
119257778
Publisher
Elsevier Science
Year
2012
Tongue
English
Weight
295 KB
Volume
218
Category
Article
ISSN
0890-5401

No coin nor oath required. For personal study only.


πŸ“œ SIMILAR VOLUMES


On the Computational Complexity of P Aut
✍ ErzsΓ©bet Csuhaj-VarjΓΊ; Oscar H. Ibarra; GyΓΆrgy Vaszil πŸ“‚ Article πŸ“… 2006 πŸ› Springer Netherlands 🌐 English βš– 296 KB
On the Learnability and Usage of Acyclic
✍ Dana Ron; Yoram Singer; Naftali Tishby πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 960 KB

We propose and analyze a distribution learning algorithm for a subclass of acyclic probalistic finite automata (APFA). This subclass is characterized by a certain distinguishability property of the automata's states. Though hardness results are known for learning distributions generated by general A