Learning commutative deterministic finite state automata in polynomial time

DOI10.1007/BF03037090MaRDI QIDQ749224zbMATH OpenFDO

Authors Naoki Abe

Publication date 1991

Published in New Generation Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF03037090

zbMATH Keywords

commutative DFAcomputational learning theorymachine learningmistake bound modelPAC learning model

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Learning and adaptive systems in artificial intelligence (68T05)

Recommendations

• scientific article; zbMATH DE number 5957212
• Learning deterministic finite automata from smallest counterexamples
• Efficient learning of typical finite automata from random walks
• scientific article; zbMATH DE number 1303603
• Grammatical Inference: Algorithms and Applications

Cites work

• Cryptographic limitations on learning Boolean formulae and finite automata
• scientific article; zbMATH DE number 67608 (Why is no real title available?)
• scientific article; zbMATH DE number 67625 (Why is no real title available?)
• Learnability and the Vapnik-Chervonenkis dimension
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Predicting \(\{ 0,1\}\)-functions on randomly drawn points
• Prediction-preserving reducibility

Cited in

(8)

• VC-dimensions of finite automata and commutative finite automata with \(k\) letters and \(n\) states
• On polynomial-time learnability in the limit of strictly deterministic automata
• Fundamental results for learning deterministic extended finite state machines from queries
• PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance
• Learning deterministic finite automata from smallest counterexamples
• scientific article; zbMATH DE number 1351099 (Why is no real title available?)
• VC-dimensions of finite automata and commutative finite automata with \(k\) letters and \(n\) states
• Subset mapping problems in solvable automata

This page was built for publication: Learning commutative deterministic finite state automata in polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q749224)