Learning Probabilistic Automata and Markov Chains via Queries

Wen-Guey Tzeng*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

We investigate the problem of learning probabilistic automata and Markov chains via queries in the teacher-student learning model. Probabilistic automata and Markov chains are probabilistic extensions of finite state automata and have similar structures. We discuss some natural oracles associated with probabilistic automata and Markov chains. We present polynomial-time algorithms for learning probabilistic automata and Markov Chains using these oracles.

Original languageEnglish
Pages (from-to)151-166
Number of pages16
JournalMachine Learning
Volume8
Issue number2
DOIs
StatePublished - 1 Jan 1992

Keywords

  • deterministic finite automaton
  • Learning via oracles
  • Markov chain
  • probabilistic automaton

Fingerprint Dive into the research topics of 'Learning Probabilistic Automata and Markov Chains via Queries'. Together they form a unique fingerprint.

Cite this