Automatic functions, linear time and learning

DOI10.2168/LMCS-9(3:19)2013MaRDI QIDQ2848364zbMATH OpenOpenAlexFDO

Authors Sanjay Jain, John Case, Frank Stephan

Publication date 26 September 2013

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2168/lmcs-9(3:19)2013

zbMATH Keywords

computational complexityautomatic structuresinductive inferencelearning power of resource-bounded learnerslinear time computation

Mathematics Subject Classification ID

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

Recommendations

• Automatic functions, linear time and learning
• Learning functions represented as multiplicity automata
• On the complexity of function learning
• Automata Learning
• On-line learning of linear functions
• Learning recursive functions from approximations
• On the intrinsic complexity of learning recursive functions
• An introduction to learning automata and optimization

Cited in

(14)

• Lamplighter groups and automata
• Automatic functions, linear time and learning
• Second-order finite automata
• Cayley linear-time computable groups
• Finitely generated semiautomatic groups
• On computability and learnability of the pumping lemma function
• Learning pattern languages over groups
• A computation model with automatic functions and relations as primitive operations
• String compression in FA-presentable structures
• Automatic learning from positive data and negative counterexamples
• Foreground automata
• Addition machines, automatic functions and open problems of Floyd and Knuth
• Learners based on transducers
• Cayley polynomial-time computable groups

This page was built for publication: Automatic functions, linear time and learning

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