VC-dimensions of finite automata and commutative finite automata with k letters and n states

被引：5
|
作者：
Ishigami, Y [1 ]
Tani, S [1 ]
机构：
[1] TOKAI UNIV, DEPT MATH, HIRATSUKA, KANAGAWA 25912, JAPAN
来源：
DISCRETE APPLIED MATHEMATICS | 1997年 / 74卷 / 02期
关键词：
D O I：
10.1016/S0166-218X(96)00025-X
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
An investigation is conducted of the Vapnik-Chervonenkis dimensions (VC-dimensions) of finite automata having k letters and n states. It is shown for a fixed positive integer k(greater than or equal to 2) that (1) the VC-dimension of DFA(k)(n) := {L subset of(1,2,..., k}* : some deterministic finite automaton with at most n states accepts L} is n + log(2) n - O(log log n) for k = 1 and (k - 1 + o(1))n log(2) n for k greater than or equal to 2, and (2) the VC-dimension of CDFA(k)(n) := {L epsilon DFA(k)-(n) : L is commutative} is o(n).s n + o(n).
引用
收藏
页码：123 / 134
页数：12
相关论文
共 50 条
  • [1] VC-dimensions of finite automata and commutative finite automata with k letters and n states
    Ishigami, Y
    Tani, S
    DISCRETE APPLIED MATHEMATICS, 1997, 74 (03) : 229 - 240
  • [2] VC-dimensions of nondeterministic finite automata for words of equal length
    Kjos-Hanssen, Bjorn
    Felix, Clyde James
    Kim, Sun Young
    Lamb, Ethan
    Takahashi, Davin
    ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 2022, 90 (01) : 93 - 105
  • [3] VC-dimensions of nondeterministic finite automata for words of equal length
    Bjørn Kjos-Hanssen
    Clyde James Felix
    Sun Young Kim
    Ethan Lamb
    Davin Takahashi
    Annals of Mathematics and Artificial Intelligence, 2022, 90 : 93 - 105
  • [4] State-deterministic Finite Automata with Translucent Letters and Finite Automata with Nondeterministically Translucent Letters
    Nagy, Benedek
    ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE, 2023, 386 : 170 - 184
  • [5] Repetitive Finite Automata With Translucent Letters
    Mraz, Frantisek
    Otto, Friedrich
    ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE, 2024, (407):
  • [6] AUTOMATA AND FINITE AUTOMATA
    LEE, CY
    BELL SYSTEM TECHNICAL JOURNAL, 1960, 39 (05): : 1267 - 1295
  • [7] Jump complexity of finite automata with translucent letters
    Mitrana, Victor
    Paun, Andrei
    Paun, Mihaela
    Couso, Jose Ramon Sanchez
    THEORETICAL COMPUTER SCIENCE, 2024, 992
  • [8] ON FINITE AUTOMATA WITH QUANTUM AND CLASSICAL STATES
    Grilo, A. B.
    Moura, A., V
    SIBERIAN ELECTRONIC MATHEMATICAL REPORTS-SIBIRSKIE ELEKTRONNYE MATEMATICHESKIE IZVESTIYA, 2013, 10 : 676 - 688
  • [9] On the number of active states in finite automata
    Bordihn, Henning
    Holzer, Markus
    ACTA INFORMATICA, 2021, 58 (04) : 301 - 318
  • [10] ESTIMATES OF NUMBER OF FINITE AUTOMATA STATES
    MASLOV, AN
    DOKLADY AKADEMII NAUK SSSR, 1970, 194 (06): : 1266 - &
12345