VC-dimensions of nondeterministic finite automata for words of equal length

DOI10.1007/s10472-021-09769-9OpenAlexW3194952410MaRDI QIDQ2075374

Davin Takahashi, Bjørn Kjos-Hanssen, Clyde James Felix, Ethan Lamb, Sun Young Kim

Publication date: 14 February 2022

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2001.02309

zbMATH Keywords

finite automatanondeterminismstate complexityVapnik-Chervonenkis dimensiontesting dimension

Mathematics Subject Classification ID

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

Uses Software

• OEIS
• GitHub

Cites Work

• Unnamed Item
• Unnamed Item
• Nondeterministic automatic complexity of overlap-free and almost square-free words
• Approximate testing and its relationship to learning
• On the average state and transition complexity of finite languages
• A combinatorial problem; stability and order for models and theories in infinitary languages
• On the density of families of sets
• VC-dimensions of finite automata and commutative finite automata with \(k\) letters and \(n\) states

This page was built for publication: VC-dimensions of nondeterministic finite automata for words of equal length