PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance

DOI10.1016/j.tcs.2007.07.023zbMath1143.68024OpenAlexW2148955780MaRDI QIDQ2465033

Nick Palmer, Paul W. Goldberg

Publication date: 19 December 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.07.023

zbMATH Keywords

computational complexitymachine learning

Mathematics Subject Classification ID

Computational learning theory (68Q32) Formal languages and automata (68Q45)

Related Items (3)

Learning Probability Distributions Generated by Finite-State Machines ⋮ Spectral learning of weighted automata. A forward-backward perspective ⋮ Adaptively learning probabilistic deterministic automata from data streams

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the computational complexity of approximating distributions by probabilistic automata
• On the learnability and usage of acyclic probabilistic finite automata
• Links between probabilistic automata and hidden Markov models: probability distributions, learning models and induction algorithms
• Evolutionary Trees Can be Learned in Polynomial Time in the Two-State General Markov Model
• On the learnability of discrete distributions
• Neural Network Learning
• Algorithmic Learning Theory
• Grammatical Inference: Algorithms and Applications

This page was built for publication: PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance