On the learnability and usage of acyclic probabilistic finite automata

DOI10.1006/jcss.1997.1555zbMath0915.68124OpenAlexW3089948396MaRDI QIDQ1271548

Yoram Singer, Naftali Tishby, Dana Ron

Publication date: 10 November 1998

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1997.1555

zbMATH Keywords

distribution learning algorithmacyclic probabilistic finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (15)

Learning deterministic regular grammars from stochastic samples in polynomial time ⋮ Learning deterministic context free grammars: the Omphalos competition ⋮ Modelling discrete longitudinal data using acyclic probabilistic finite automata ⋮ KIS: An automated attribute induction method for classification of DNA sequences ⋮ Learning deterministic probabilistic automata from a model checking perspective ⋮ Abductive learning of quantized stochastic processes with probabilistic finite automata ⋮ An inner product space on irreducible and synchronizable probabilistic finite state automata ⋮ Vector space formulation of probabilistic finite state automata ⋮ Spectral learning of weighted automata. A forward-backward perspective ⋮ Adaptively learning probabilistic deterministic automata from data streams ⋮ PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance ⋮ The power of amnesia: Learning probabilistic automata with variable memory length ⋮ Kernel methods for learning languages ⋮ Grammatical inference of directed acyclic graph languages with polynomial time complexity ⋮ Context-specific graphical models for discrete longitudinal data

Cites Work

• Unnamed Item
• On the computational complexity of approximating distributions by probabilistic automata
• Dynamical encoding of cursive handwriting
• On the learnability of discrete distributions
• Efficient learning of typical finite automata from random walks
• Efficient noise-tolerant learning from statistical queries
• Probability Inequalities for Sums of Bounded Random Variables
• Statistical Inference for Probabilistic Functions of Finite State Markov Chains

This page was built for publication: On the learnability and usage of acyclic probabilistic finite automata