Efficient learning of typical finite automata from random walks
type: Item
instance of: scholarly article
title: Efficient learning of typical finite automata from random walks
zbMATH Open document ID: 0889.68131
author: Yoav Freund
author: Michael Kearns
author: Dana Ron
author: Ronitt Rubinfeld
author: Robert E. Schapire
author: Linda Sellie
published in: Information and Computation
publication date: 1998-06-02T00:00:00Z
Mathematics Subject Classification ID: 68T05
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 1083947
zbMATH Keywords: learning deterministic finite automata
MaRDI profile type: Publication
full work available at URL: inco.1997.2648
OpenAlex ID: W2043635106
cites work: Learning regular sets from queries and counterexamples
cites work: On the complexity of minimum inference of regular sets
cites work: Biased random walks
cites work: Q5614667
cites work: New approximation algorithms for graph coloring
cites work: Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
cites work: Universal prediction of individual sequences
cites work: Q5538132
cites work: System identification via state characterization
cites work: Complexity of automaton identification from given data
cites work: Predicting \(\{ 0,1\}\)-functions on randomly drawn points
cites work: On the learnability of discrete distributions
cites work: Cryptographic limitations on learning Boolean formulae and finite automata
cites work: Computational limitations on learning from examples
cites work: Prediction-preserving reducibility
cites work: The minimum consistent DFA problem cannot be approximated within any polynomial
cites work: Inference of finite automata using homing sequences
cites work: Diversity-based inference of finite automata
cites work: Generating quasi-random sequences from semi-random sources
cites work: Q3214824
cites work: A theory of the learnable
cites work: Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources
cites work: Q3702366
DOI: 10.1006/INCO.1997.2648
Recommended article: Grammatical Inference: Algorithms and Applications
Recommended article: Q5875378
Recommended article: Towards Feasible PAC-Learning of Probabilistic Deterministic Finite Automata
Recommended article: Learning fallible deterministic finite automata
Recommended article: On the learnability and usage of acyclic probabilistic finite automata
Recommended article: Q4999312
Recommended article: Learning Theory
Recommended article: Learning Deterministic Finite Automata from Interleaved Strings
Recommended article: Q3093192
description: scientific article; zbMATH DE number 1083947