Learning commutative deterministic finite state automata in polynomial time

DOI10.1007/BF03037090zbMath0712.68078MaRDI QIDQ749224

Naoki Abe

Publication date: 1991

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

zbMATH Keywords

computational learning theorymachine learningcommutative DFAmistake bound modelPAC learning model

Mathematics Subject Classification ID

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

Related Items (2)

VC-dimensions of finite automata and commutative finite automata with \(k\) letters and \(n\) states ⋮ VC-dimensions of finite automata and commutative finite automata with \(k\) letters and \(n\) states

Cites Work

• Prediction-preserving reducibility
• Predicting \(\{ 0,1\}\)-functions on randomly drawn points
• Learnability and the Vapnik-Chervonenkis dimension
• Cryptographic limitations on learning Boolean formulae and finite automata
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Unnamed Item
• Unnamed Item

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