VC-dimensions of nondeterministic finite automata for words of equal length View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2021-08-24

AUTHORS

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

ABSTRACT

Let NFAb(q) denote the set of languages accepted by nondeterministic finite automata with q states over an alphabet with b letters. Let Bn denote the set of words of length n. We give a quadratic lower bound on the VC dimension of NFA2(q)∩Bn={L∩Bn∣L∈NFA2(q)}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ \text{NFA}_{2}(q)\cap B_{n} = \{L\cap B_{n} \mid L \in \text{NFA}_{2}(q)\} $$\end{document} as a function of q. Next, the work of Gruber and Holzer (Theoret. Comput. Sci. 387(2): 155–166, 2007) gives an upper bound for the nondeterministic state complexity of finite languages contained in Bn, which we strengthen using our methods. Finally, we give some theoretical and experimental results on the dependence on n of the VC dimension and testing dimension of NFA2(q) ∩ Bn. More... »

PAGES

1-13

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s10472-021-09769-9

DOI

http://dx.doi.org/10.1007/s10472-021-09769-9

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1140631393


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Mathematics, University of Hawai\u2019i at M\u0101noa, 2565 McCarthy Mall, 96822, Honolulu, HI, USA", 
          "id": "http://www.grid.ac/institutes/grid.410445.0", 
          "name": [
            "Department of Mathematics, University of Hawai\u2019i at M\u0101noa, 2565 McCarthy Mall, 96822, Honolulu, HI, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kjos-Hanssen", 
        "givenName": "Bj\u00f8rn", 
        "id": "sg:person.014135415067.15", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014135415067.15"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Mathematics, University of Hawai\u2019i at M\u0101noa, 2565 McCarthy Mall, 96822, Honolulu, HI, USA", 
          "id": "http://www.grid.ac/institutes/grid.410445.0", 
          "name": [
            "Department of Mathematics, University of Hawai\u2019i at M\u0101noa, 2565 McCarthy Mall, 96822, Honolulu, HI, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Felix", 
        "givenName": "Clyde James", 
        "id": "sg:person.011302422103.13", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011302422103.13"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Mathematics, University of Hawai\u2019i at M\u0101noa, 2565 McCarthy Mall, 96822, Honolulu, HI, USA", 
          "id": "http://www.grid.ac/institutes/grid.410445.0", 
          "name": [
            "Department of Mathematics, University of Hawai\u2019i at M\u0101noa, 2565 McCarthy Mall, 96822, Honolulu, HI, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kim", 
        "givenName": "Sun Young", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Mathematics, University of Hawai\u2019i at M\u0101noa, 2565 McCarthy Mall, 96822, Honolulu, HI, USA", 
          "id": "http://www.grid.ac/institutes/grid.410445.0", 
          "name": [
            "Department of Mathematics, University of Hawai\u2019i at M\u0101noa, 2565 McCarthy Mall, 96822, Honolulu, HI, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lamb", 
        "givenName": "Ethan", 
        "id": "sg:person.012675363103.42", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012675363103.42"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Mathematics, University of Hawai\u2019i at M\u0101noa, 2565 McCarthy Mall, 96822, Honolulu, HI, USA", 
          "id": "http://www.grid.ac/institutes/grid.410445.0", 
          "name": [
            "Department of Mathematics, University of Hawai\u2019i at M\u0101noa, 2565 McCarthy Mall, 96822, Honolulu, HI, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Takahashi", 
        "givenName": "Davin", 
        "id": "sg:person.013472743503.55", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013472743503.55"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2021-08-24", 
    "datePublishedReg": "2021-08-24", 
    "description": "Let NFAb(q) denote the set of languages accepted by nondeterministic finite automata with q states over an alphabet with b letters. Let Bn denote the set of words of length n. We give a quadratic lower bound on the VC dimension of\nNFA2(q)\u2229Bn={L\u2229Bn\u2223L\u2208NFA2(q)}\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$ \\text{NFA}_{2}(q)\\cap B_{n} = \\{L\\cap B_{n} \\mid L \\in \\text{NFA}_{2}(q)\\} $$\\end{document} as a function of q. Next, the work of Gruber and Holzer (Theoret. Comput. Sci. 387(2): 155\u2013166, 2007) gives an upper bound for the nondeterministic state complexity of finite languages contained in Bn, which we strengthen using our methods. Finally, we give some theoretical and experimental results on the dependence on n of the VC dimension and testing dimension of NFA2(q) \u2229 Bn.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s10472-021-09769-9", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1043955", 
        "issn": [
          "1012-2443", 
          "1573-7470"
        ], 
        "name": "Annals of Mathematics and Artificial Intelligence", 
        "type": "Periodical"
      }
    ], 
    "keywords": [
      "VC dimension", 
      "nondeterministic finite automata", 
      "finite automata", 
      "nondeterministic state complexity", 
      "set of languages", 
      "set of words", 
      "length n.", 
      "state complexity", 
      "finite languages", 
      "language", 
      "words", 
      "automata", 
      "BN", 
      "dimensions", 
      "equal length", 
      "experimental results", 
      "set", 
      "testing dimension", 
      "alphabet", 
      "Holzer", 
      "complexity", 
      "dependence", 
      "letter", 
      "n.", 
      "Gruber", 
      "function", 
      "state", 
      "work", 
      "results", 
      "length", 
      "method", 
      "work of Gruber"
    ], 
    "name": "VC-dimensions of nondeterministic finite automata for words of equal length", 
    "pagination": "1-13", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1140631393"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s10472-021-09769-9"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s10472-021-09769-9", 
      "https://app.dimensions.ai/details/publication/pub.1140631393"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-01-01T19:00", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/article/article_893.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s10472-021-09769-9"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s10472-021-09769-9'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s10472-021-09769-9'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10472-021-09769-9'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10472-021-09769-9'


 

This table displays all metadata directly associated to this object as RDF triples.

122 TRIPLES      21 PREDICATES      58 URIs      47 LITERALS      4 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s10472-021-09769-9 schema:about anzsrc-for:01
2 anzsrc-for:0102
3 anzsrc-for:08
4 anzsrc-for:0801
5 anzsrc-for:0802
6 schema:author N0ee827ce0b0940dd90b70ac08ba348e4
7 schema:datePublished 2021-08-24
8 schema:datePublishedReg 2021-08-24
9 schema:description Let NFAb(q) denote the set of languages accepted by nondeterministic finite automata with q states over an alphabet with b letters. Let Bn denote the set of words of length n. We give a quadratic lower bound on the VC dimension of NFA2(q)∩Bn={L∩Bn∣L∈NFA2(q)}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ \text{NFA}_{2}(q)\cap B_{n} = \{L\cap B_{n} \mid L \in \text{NFA}_{2}(q)\} $$\end{document} as a function of q. Next, the work of Gruber and Holzer (Theoret. Comput. Sci. 387(2): 155–166, 2007) gives an upper bound for the nondeterministic state complexity of finite languages contained in Bn, which we strengthen using our methods. Finally, we give some theoretical and experimental results on the dependence on n of the VC dimension and testing dimension of NFA2(q) ∩ Bn.
10 schema:genre article
11 schema:inLanguage en
12 schema:isAccessibleForFree true
13 schema:isPartOf sg:journal.1043955
14 schema:keywords BN
15 Gruber
16 Holzer
17 VC dimension
18 alphabet
19 automata
20 complexity
21 dependence
22 dimensions
23 equal length
24 experimental results
25 finite automata
26 finite languages
27 function
28 language
29 length
30 length n.
31 letter
32 method
33 n.
34 nondeterministic finite automata
35 nondeterministic state complexity
36 results
37 set
38 set of languages
39 set of words
40 state
41 state complexity
42 testing dimension
43 words
44 work
45 work of Gruber
46 schema:name VC-dimensions of nondeterministic finite automata for words of equal length
47 schema:pagination 1-13
48 schema:productId N75499b2fcc754592955806b92c5b5216
49 Ne67e2f34c80049c98173244be6894087
50 schema:sameAs https://app.dimensions.ai/details/publication/pub.1140631393
51 https://doi.org/10.1007/s10472-021-09769-9
52 schema:sdDatePublished 2022-01-01T19:00
53 schema:sdLicense https://scigraph.springernature.com/explorer/license/
54 schema:sdPublisher Ne994cb75e1494e2882e2cdd74cd3ba0b
55 schema:url https://doi.org/10.1007/s10472-021-09769-9
56 sgo:license sg:explorer/license/
57 sgo:sdDataset articles
58 rdf:type schema:ScholarlyArticle
59 N0ee827ce0b0940dd90b70ac08ba348e4 rdf:first sg:person.014135415067.15
60 rdf:rest N0ff9dae3ebd7422aafc3883779c2d9e8
61 N0ff9dae3ebd7422aafc3883779c2d9e8 rdf:first sg:person.011302422103.13
62 rdf:rest Nc727733b574c4960adbca3ab1dfd23c8
63 N10610d76be194374a3040f426e7a2094 schema:affiliation grid-institutes:grid.410445.0
64 schema:familyName Kim
65 schema:givenName Sun Young
66 rdf:type schema:Person
67 N75499b2fcc754592955806b92c5b5216 schema:name doi
68 schema:value 10.1007/s10472-021-09769-9
69 rdf:type schema:PropertyValue
70 N9b7a6dc46816497b9b47bb5368dd5b54 rdf:first sg:person.012675363103.42
71 rdf:rest Na8b57aa0ae4442c3a3bc72d72839f34a
72 Na8b57aa0ae4442c3a3bc72d72839f34a rdf:first sg:person.013472743503.55
73 rdf:rest rdf:nil
74 Nc727733b574c4960adbca3ab1dfd23c8 rdf:first N10610d76be194374a3040f426e7a2094
75 rdf:rest N9b7a6dc46816497b9b47bb5368dd5b54
76 Ne67e2f34c80049c98173244be6894087 schema:name dimensions_id
77 schema:value pub.1140631393
78 rdf:type schema:PropertyValue
79 Ne994cb75e1494e2882e2cdd74cd3ba0b schema:name Springer Nature - SN SciGraph project
80 rdf:type schema:Organization
81 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
82 schema:name Mathematical Sciences
83 rdf:type schema:DefinedTerm
84 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
85 schema:name Applied Mathematics
86 rdf:type schema:DefinedTerm
87 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
88 schema:name Information and Computing Sciences
89 rdf:type schema:DefinedTerm
90 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
91 schema:name Artificial Intelligence and Image Processing
92 rdf:type schema:DefinedTerm
93 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
94 schema:name Computation Theory and Mathematics
95 rdf:type schema:DefinedTerm
96 sg:journal.1043955 schema:issn 1012-2443
97 1573-7470
98 schema:name Annals of Mathematics and Artificial Intelligence
99 rdf:type schema:Periodical
100 sg:person.011302422103.13 schema:affiliation grid-institutes:grid.410445.0
101 schema:familyName Felix
102 schema:givenName Clyde James
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011302422103.13
104 rdf:type schema:Person
105 sg:person.012675363103.42 schema:affiliation grid-institutes:grid.410445.0
106 schema:familyName Lamb
107 schema:givenName Ethan
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012675363103.42
109 rdf:type schema:Person
110 sg:person.013472743503.55 schema:affiliation grid-institutes:grid.410445.0
111 schema:familyName Takahashi
112 schema:givenName Davin
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013472743503.55
114 rdf:type schema:Person
115 sg:person.014135415067.15 schema:affiliation grid-institutes:grid.410445.0
116 schema:familyName Kjos-Hanssen
117 schema:givenName Bjørn
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014135415067.15
119 rdf:type schema:Person
120 grid-institutes:grid.410445.0 schema:alternateName Department of Mathematics, University of Hawai’i at Mānoa, 2565 McCarthy Mall, 96822, Honolulu, HI, USA
121 schema:name Department of Mathematics, University of Hawai’i at Mānoa, 2565 McCarthy Mall, 96822, Honolulu, HI, USA
122 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...