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 Nba68b2acf8954861b61fe2a94027776c
    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 N246cf67c0c81494487b75f643ac8e6fb
    19 Nb655595e8bfa45b297de72a2fe8ef4ea
    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 N8801924ba39e4b7aa7e73c5b744d7f21
    70 Nf1b0ec9606b34175863170927e9b537f
    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 N307e5e981b454a80b61a2c9d77741525
    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 N246cf67c0c81494487b75f643ac8e6fb schema:issueNumber 1-2
    81 rdf:type schema:PublicationIssue
    82 N307e5e981b454a80b61a2c9d77741525 schema:name Springer Nature - SN SciGraph project
    83 rdf:type schema:Organization
    84 N8801924ba39e4b7aa7e73c5b744d7f21 schema:name doi
    85 schema:value 10.1023/a:1010822518073
    86 rdf:type schema:PropertyValue
    87 Na4be56c308124a699155dbe762403693 rdf:first sg:person.01335570111.71
    88 rdf:rest rdf:nil
    89 Nb655595e8bfa45b297de72a2fe8ef4ea schema:volumeNumber 44
    90 rdf:type schema:PublicationVolume
    91 Nba68b2acf8954861b61fe2a94027776c rdf:first sg:person.012635522717.12
    92 rdf:rest Na4be56c308124a699155dbe762403693
    93 Nf1b0ec9606b34175863170927e9b537f schema:name dimensions_id
    94 schema:value pub.1026505593
    95 rdf:type schema:PropertyValue
    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)


    ...