Learning DFA from Simple Examples View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2001-07

AUTHORS

Rajesh Parekh, Vasant Honavar

ABSTRACT

Efficient learning of DFA is a challenging research problem in grammatical inference. It is known that both exact and approximate (in the PAC sense) identifiability of DFA is hard. Pitt has posed the following open research problem: “Are DFA PAC-identifiable if examples are drawn from the uniform distribution, or some other known simple distribution?” (Pitt, in Lecture Notes in Artificial Intelligence, 397, pp. 18–44, Springer-Verlag, 1989). We demonstrate that the class of DFA whose canonical representations have logarithmic Kolmogorov complexity is efficiently PAC learnable under the Solomonoff Levin universal distribution (m). We prove that the class of DFA is efficiently learnable under the PACS (PAC learning with simple examples) model (Denis, D'Halluin & Gilleron, STACS'96—Proceedings of the 13th Annual Symposium on the Theoretical Aspects of Computer Science, pp. 231–242, 1996) wherein positive and negative examples are sampled according to the universal distribution conditional on a description of the target concept. Further, we show that any concept that is learnable under Gold's model of learning from characteristic samples, Goldman and Mathias' polynomial teachability model, and the model of learning from example based queries is also learnable under the PACS model. More... »

PAGES

9-35

References to SciGraph publications

  • 1996. PAC learning with simple examples in STACS 96
  • 1996. Incremental regular inference in GRAMMATICAL INTERFERENCE: LEARNING SYNTAX FROM SENTENCES
  • 1989. Inductive inference, DFAs, and computational complexity in ANALOGICAL AND INDUCTIVE INFERENCE
  • 1996. Characteristic sets for polynomial grammatical inference in GRAMMATICAL INTERFERENCE: LEARNING SYNTAX FROM SENTENCES
  • 1997. PAC learning under helpful distributions in ALGORITHMIC LEARNING THEORY
  • 1988-04. Queries and concept learning in MACHINE LEARNING
  • 1994. What is the search space of the regular inference? in GRAMMATICAL INFERENCE AND APPLICATIONS
  • 1997. Learning DFA from simple examples in ALGORITHMIC LEARNING THEORY
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1023/a:1010822518073

    DOI

    http://dx.doi.org/10.1023/a:1010822518073

    DIMENSIONS

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


    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/17", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Psychology and Cognitive Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1701", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Psychology", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Blue Martini Software, 2600 Campus Drive, 94403, San Mateo, CA, USA", 
              "id": "http://www.grid.ac/institutes/None", 
              "name": [
                "Blue Martini Software, 2600 Campus Drive, 94403, San Mateo, CA, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Parekh", 
            "givenName": "Rajesh", 
            "id": "sg:person.012635522717.12", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012635522717.12"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, Iowa State University, 50011, Ames, IA, USA", 
              "id": "http://www.grid.ac/institutes/grid.34421.30", 
              "name": [
                "Department of Computer Science, Iowa State University, 50011, Ames, IA, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Honavar", 
            "givenName": "Vasant", 
            "id": "sg:person.01335570111.71", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01335570111.71"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-63577-7_39", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037471244", 
              "https://doi.org/10.1007/3-540-63577-7_39"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-63577-7_40", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037983954", 
              "https://doi.org/10.1007/3-540-63577-7_40"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0033357", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024508659", 
              "https://doi.org/10.1007/bfb0033357"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00116828", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030500577", 
              "https://doi.org/10.1007/bf00116828"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0033342", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003847248", 
              "https://doi.org/10.1007/bfb0033342"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-60922-9_20", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014518579", 
              "https://doi.org/10.1007/3-540-60922-9_20"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-51734-0_50", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025007515", 
              "https://doi.org/10.1007/3-540-51734-0_50"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-58473-0_134", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044554965", 
              "https://doi.org/10.1007/3-540-58473-0_134"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2001-07", 
        "datePublishedReg": "2001-07-01", 
        "description": "Efficient learning of DFA is a challenging research problem in grammatical inference. It is known that both exact and approximate (in the PAC sense) identifiability of DFA is hard. Pitt has posed the following open research problem: \u201cAre DFA PAC-identifiable if examples are drawn from the uniform distribution, or some other known simple distribution?\u201d (Pitt, in Lecture Notes in Artificial Intelligence, 397, pp. 18\u201344, Springer-Verlag, 1989). We demonstrate that the class of DFA whose canonical representations have logarithmic Kolmogorov complexity is efficiently PAC learnable under the Solomonoff Levin universal distribution (m). We prove that the class of DFA is efficiently learnable under the PACS (PAC learning with simple examples) model (Denis, D'Halluin & Gilleron, STACS'96\u2014Proceedings of the 13th Annual Symposium on the Theoretical Aspects of Computer Science, pp. 231\u2013242, 1996) wherein positive and negative examples are sampled according to the universal distribution conditional on a description of the target concept. Further, we show that any concept that is learnable under Gold's model of learning from characteristic samples, Goldman and Mathias' polynomial teachability model, and the model of learning from example based queries is also learnable under the PACS model.", 
        "genre": "article", 
        "id": "sg:pub.10.1023/a:1010822518073", 
        "inLanguage": "en", 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1125588", 
            "issn": [
              "0885-6125", 
              "1573-0565"
            ], 
            "name": "Machine Learning", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1-2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "44"
          }
        ], 
        "keywords": [
          "research problem", 
          "class of DFA", 
          "challenging research problem", 
          "open research problems", 
          "grammatical inference", 
          "negative examples", 
          "efficient learning", 
          "target concept", 
          "Kolmogorov complexity", 
          "Gold\u2019s model", 
          "canonical representation", 
          "simple example", 
          "approximate identifiability", 
          "queries", 
          "characteristic samples", 
          "example", 
          "complexity", 
          "DFA", 
          "learning", 
          "simple distribution", 
          "concept", 
          "model", 
          "representation", 
          "inference", 
          "class", 
          "distribution conditional", 
          "description", 
          "identifiability", 
          "PAC", 
          "conditional", 
          "problem", 
          "uniform distribution", 
          "universal distribution", 
          "Pitt", 
          "Goldman", 
          "distribution", 
          "samples", 
          "DFA PAC", 
          "logarithmic Kolmogorov complexity", 
          "Solomonoff Levin universal distribution", 
          "Levin universal distribution", 
          "PACS (PAC learning with simple examples) model", 
          "universal distribution conditional", 
          "Mathias' polynomial teachability model", 
          "' polynomial teachability model", 
          "teachability model"
        ], 
        "name": "Learning DFA from Simple Examples", 
        "pagination": "9-35", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1026505593"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1023/a:1010822518073"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1023/a:1010822518073", 
          "https://app.dimensions.ai/details/publication/pub.1026505593"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2021-12-01T19:14", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/article/article_348.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1023/a:1010822518073"
      }
    ]
     

    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.1023/a:1010822518073'

    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.1023/a:1010822518073'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1023/a:1010822518073'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1023/a:1010822518073'


     

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

    146 TRIPLES      22 PREDICATES      80 URIs      64 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1023/a:1010822518073 schema:about anzsrc-for:17
    2 anzsrc-for:1701
    3 schema:author Nfb942e8fafb540c7ae0f443867d315a9
    4 schema:citation sg:pub.10.1007/3-540-51734-0_50
    5 sg:pub.10.1007/3-540-58473-0_134
    6 sg:pub.10.1007/3-540-60922-9_20
    7 sg:pub.10.1007/3-540-63577-7_39
    8 sg:pub.10.1007/3-540-63577-7_40
    9 sg:pub.10.1007/bf00116828
    10 sg:pub.10.1007/bfb0033342
    11 sg:pub.10.1007/bfb0033357
    12 schema:datePublished 2001-07
    13 schema:datePublishedReg 2001-07-01
    14 schema:description Efficient learning of DFA is a challenging research problem in grammatical inference. It is known that both exact and approximate (in the PAC sense) identifiability of DFA is hard. Pitt has posed the following open research problem: “Are DFA PAC-identifiable if examples are drawn from the uniform distribution, or some other known simple distribution?” (Pitt, in Lecture Notes in Artificial Intelligence, 397, pp. 18–44, Springer-Verlag, 1989). We demonstrate that the class of DFA whose canonical representations have logarithmic Kolmogorov complexity is efficiently PAC learnable under the Solomonoff Levin universal distribution (m). We prove that the class of DFA is efficiently learnable under the PACS (PAC learning with simple examples) model (Denis, D'Halluin & Gilleron, STACS'96—Proceedings of the 13th Annual Symposium on the Theoretical Aspects of Computer Science, pp. 231–242, 1996) wherein positive and negative examples are sampled according to the universal distribution conditional on a description of the target concept. Further, we show that any concept that is learnable under Gold's model of learning from characteristic samples, Goldman and Mathias' polynomial teachability model, and the model of learning from example based queries is also learnable under the PACS model.
    15 schema:genre article
    16 schema:inLanguage en
    17 schema:isAccessibleForFree true
    18 schema:isPartOf N20c7fd345cb14bc8a7385ba230fc7df8
    19 N28f374a4a4d7470487ca0226b07fa782
    20 sg:journal.1125588
    21 schema:keywords ' polynomial teachability model
    22 DFA
    23 DFA PAC
    24 Goldman
    25 Gold’s model
    26 Kolmogorov complexity
    27 Levin universal distribution
    28 Mathias' polynomial teachability model
    29 PAC
    30 PACS (PAC learning with simple examples) model
    31 Pitt
    32 Solomonoff Levin universal distribution
    33 approximate identifiability
    34 canonical representation
    35 challenging research problem
    36 characteristic samples
    37 class
    38 class of DFA
    39 complexity
    40 concept
    41 conditional
    42 description
    43 distribution
    44 distribution conditional
    45 efficient learning
    46 example
    47 grammatical inference
    48 identifiability
    49 inference
    50 learning
    51 logarithmic Kolmogorov complexity
    52 model
    53 negative examples
    54 open research problems
    55 problem
    56 queries
    57 representation
    58 research problem
    59 samples
    60 simple distribution
    61 simple example
    62 target concept
    63 teachability model
    64 uniform distribution
    65 universal distribution
    66 universal distribution conditional
    67 schema:name Learning DFA from Simple Examples
    68 schema:pagination 9-35
    69 schema:productId N0cbb7a45ad264822937e7a1033cd96a5
    70 N67f1fadb37b848d7a592611f3a832718
    71 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026505593
    72 https://doi.org/10.1023/a:1010822518073
    73 schema:sdDatePublished 2021-12-01T19:14
    74 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    75 schema:sdPublisher Ne1acc51c8ef04cd898d871eda93bdeb1
    76 schema:url https://doi.org/10.1023/a:1010822518073
    77 sgo:license sg:explorer/license/
    78 sgo:sdDataset articles
    79 rdf:type schema:ScholarlyArticle
    80 N0cbb7a45ad264822937e7a1033cd96a5 schema:name dimensions_id
    81 schema:value pub.1026505593
    82 rdf:type schema:PropertyValue
    83 N20c7fd345cb14bc8a7385ba230fc7df8 schema:volumeNumber 44
    84 rdf:type schema:PublicationVolume
    85 N28f374a4a4d7470487ca0226b07fa782 schema:issueNumber 1-2
    86 rdf:type schema:PublicationIssue
    87 N67f1fadb37b848d7a592611f3a832718 schema:name doi
    88 schema:value 10.1023/a:1010822518073
    89 rdf:type schema:PropertyValue
    90 Ne1acc51c8ef04cd898d871eda93bdeb1 schema:name Springer Nature - SN SciGraph project
    91 rdf:type schema:Organization
    92 Nf1ef8b6da5774241949970d6d492ec67 rdf:first sg:person.01335570111.71
    93 rdf:rest rdf:nil
    94 Nfb942e8fafb540c7ae0f443867d315a9 rdf:first sg:person.012635522717.12
    95 rdf:rest Nf1ef8b6da5774241949970d6d492ec67
    96 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
    97 schema:name Psychology and Cognitive Sciences
    98 rdf:type schema:DefinedTerm
    99 anzsrc-for:1701 schema:inDefinedTermSet anzsrc-for:
    100 schema:name Psychology
    101 rdf:type schema:DefinedTerm
    102 sg:journal.1125588 schema:issn 0885-6125
    103 1573-0565
    104 schema:name Machine Learning
    105 schema:publisher Springer Nature
    106 rdf:type schema:Periodical
    107 sg:person.012635522717.12 schema:affiliation grid-institutes:None
    108 schema:familyName Parekh
    109 schema:givenName Rajesh
    110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012635522717.12
    111 rdf:type schema:Person
    112 sg:person.01335570111.71 schema:affiliation grid-institutes:grid.34421.30
    113 schema:familyName Honavar
    114 schema:givenName Vasant
    115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01335570111.71
    116 rdf:type schema:Person
    117 sg:pub.10.1007/3-540-51734-0_50 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025007515
    118 https://doi.org/10.1007/3-540-51734-0_50
    119 rdf:type schema:CreativeWork
    120 sg:pub.10.1007/3-540-58473-0_134 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044554965
    121 https://doi.org/10.1007/3-540-58473-0_134
    122 rdf:type schema:CreativeWork
    123 sg:pub.10.1007/3-540-60922-9_20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014518579
    124 https://doi.org/10.1007/3-540-60922-9_20
    125 rdf:type schema:CreativeWork
    126 sg:pub.10.1007/3-540-63577-7_39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037471244
    127 https://doi.org/10.1007/3-540-63577-7_39
    128 rdf:type schema:CreativeWork
    129 sg:pub.10.1007/3-540-63577-7_40 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037983954
    130 https://doi.org/10.1007/3-540-63577-7_40
    131 rdf:type schema:CreativeWork
    132 sg:pub.10.1007/bf00116828 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030500577
    133 https://doi.org/10.1007/bf00116828
    134 rdf:type schema:CreativeWork
    135 sg:pub.10.1007/bfb0033342 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003847248
    136 https://doi.org/10.1007/bfb0033342
    137 rdf:type schema:CreativeWork
    138 sg:pub.10.1007/bfb0033357 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024508659
    139 https://doi.org/10.1007/bfb0033357
    140 rdf:type schema:CreativeWork
    141 grid-institutes:None schema:alternateName Blue Martini Software, 2600 Campus Drive, 94403, San Mateo, CA, USA
    142 schema:name Blue Martini Software, 2600 Campus Drive, 94403, San Mateo, CA, USA
    143 rdf:type schema:Organization
    144 grid-institutes:grid.34421.30 schema:alternateName Department of Computer Science, Iowa State University, 50011, Ames, IA, USA
    145 schema:name Department of Computer Science, Iowa State University, 50011, Ames, IA, USA
    146 rdf:type schema:Organization
     




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


    ...