An incremental interactive algorithm for regular grammar inference View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1996

AUTHORS

Rajesh Parekh , Vasant Honavar

ABSTRACT

We present provably correct interactive algorithms for learning regular grammars from positive examples and membership queries. A structurally complete set of strings from a language L(G) corresponding to a target regular grammar G implicitly specifies a lattice of finite state automata (FSA) which contains a FSA MG corresponding to G. The lattice is compactly represented as a version-space and MG is identified by searching the version-space using membership queries. We explore the problem of regular grammar inference in a setting where positive examples are provided intermittently. We provide an incremental version of the algorithm along with a set of sufficient conditions for its convergence. More... »

PAGES

238-249

Book

TITLE

Grammatical Interference: Learning Syntax from Sentences

ISBN

978-3-540-61778-5
978-3-540-70678-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bfb0033358

DOI

http://dx.doi.org/10.1007/bfb0033358

DIMENSIONS

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


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/20", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Language, Communication and Culture", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/2004", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Linguistics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Artificial Intelligence Research Group Department of Computer Science, Iowa State University, 50011, Ames, IA, USA", 
          "id": "http://www.grid.ac/institutes/grid.34421.30", 
          "name": [
            "Artificial Intelligence Research Group Department of Computer Science, Iowa State University, 50011, Ames, IA, 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": "Artificial Intelligence Research Group Department of Computer Science, Iowa State University, 50011, Ames, IA, USA", 
          "id": "http://www.grid.ac/institutes/grid.34421.30", 
          "name": [
            "Artificial Intelligence Research Group 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"
      }
    ], 
    "datePublished": "1996", 
    "datePublishedReg": "1996-01-01", 
    "description": "We present provably correct interactive algorithms for learning regular grammars from positive examples and membership queries. A structurally complete set of strings from a language L(G) corresponding to a target regular grammar G implicitly specifies a lattice of finite state automata (FSA) which contains a FSA MG corresponding to G. The lattice is compactly represented as a version-space and MG is identified by searching the version-space using membership queries. We explore the problem of regular grammar inference in a setting where positive examples are provided intermittently. We provide an incremental version of the algorithm along with a set of sufficient conditions for its convergence.", 
    "editor": [
      {
        "familyName": "Miclet", 
        "givenName": "Laurent", 
        "type": "Person"
      }, 
      {
        "familyName": "de la Higuera", 
        "givenName": "Colin", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/bfb0033358", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-61778-5", 
        "978-3-540-70678-6"
      ], 
      "name": "Grammatical Interference: Learning Syntax from Sentences", 
      "type": "Book"
    }, 
    "keywords": [
      "finite state automata", 
      "interactive algorithm", 
      "grammar inference", 
      "membership queries", 
      "positive examples", 
      "incremental version", 
      "state automata", 
      "algorithm", 
      "queries", 
      "regular grammars", 
      "grammar G", 
      "set", 
      "inference", 
      "automata", 
      "language", 
      "complete set", 
      "example", 
      "grammar", 
      "version", 
      "convergence", 
      "strings", 
      "sufficient conditions", 
      "setting", 
      "conditions", 
      "lattice", 
      "problem", 
      "Mg", 
      "correct interactive algorithms", 
      "target regular grammar G", 
      "regular grammar G", 
      "FSA MG", 
      "regular grammar inference", 
      "incremental interactive algorithm"
    ], 
    "name": "An incremental interactive algorithm for regular grammar inference", 
    "pagination": "238-249", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1004884178"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bfb0033358"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/bfb0033358", 
      "https://app.dimensions.ai/details/publication/pub.1004884178"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:10", 
    "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/chapter/chapter_428.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/bfb0033358"
  }
]
 

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/bfb0033358'

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/bfb0033358'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bfb0033358'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bfb0033358'


 

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

105 TRIPLES      23 PREDICATES      59 URIs      52 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bfb0033358 schema:about anzsrc-for:20
2 anzsrc-for:2004
3 schema:author Ncaad0837867b415a82d0c4094a1e5013
4 schema:datePublished 1996
5 schema:datePublishedReg 1996-01-01
6 schema:description We present provably correct interactive algorithms for learning regular grammars from positive examples and membership queries. A structurally complete set of strings from a language L(G) corresponding to a target regular grammar G implicitly specifies a lattice of finite state automata (FSA) which contains a FSA MG corresponding to G. The lattice is compactly represented as a version-space and MG is identified by searching the version-space using membership queries. We explore the problem of regular grammar inference in a setting where positive examples are provided intermittently. We provide an incremental version of the algorithm along with a set of sufficient conditions for its convergence.
7 schema:editor N4628ae587d2442caa79e278d9a2c0e2f
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N041ff7f3c7a540bfb0acace09c581c48
12 schema:keywords FSA MG
13 Mg
14 algorithm
15 automata
16 complete set
17 conditions
18 convergence
19 correct interactive algorithms
20 example
21 finite state automata
22 grammar
23 grammar G
24 grammar inference
25 incremental interactive algorithm
26 incremental version
27 inference
28 interactive algorithm
29 language
30 lattice
31 membership queries
32 positive examples
33 problem
34 queries
35 regular grammar G
36 regular grammar inference
37 regular grammars
38 set
39 setting
40 state automata
41 strings
42 sufficient conditions
43 target regular grammar G
44 version
45 schema:name An incremental interactive algorithm for regular grammar inference
46 schema:pagination 238-249
47 schema:productId Nc6811e407dc54e6fa0dbeda8673fa464
48 Ne8d784ef3934428e93e629c510f5386c
49 schema:publisher Nc07894b49f3942c697bc121f0896104c
50 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004884178
51 https://doi.org/10.1007/bfb0033358
52 schema:sdDatePublished 2021-12-01T20:10
53 schema:sdLicense https://scigraph.springernature.com/explorer/license/
54 schema:sdPublisher N5f7b5c83d22945708433eae632d8f86c
55 schema:url https://doi.org/10.1007/bfb0033358
56 sgo:license sg:explorer/license/
57 sgo:sdDataset chapters
58 rdf:type schema:Chapter
59 N041ff7f3c7a540bfb0acace09c581c48 schema:isbn 978-3-540-61778-5
60 978-3-540-70678-6
61 schema:name Grammatical Interference: Learning Syntax from Sentences
62 rdf:type schema:Book
63 N04728e45b80d4d72a3fb77fbb204870d rdf:first N554bd513d35a44f38cddc54336046c6b
64 rdf:rest rdf:nil
65 N4628ae587d2442caa79e278d9a2c0e2f rdf:first N9fd690331df94174a0f2733e617f5b35
66 rdf:rest N04728e45b80d4d72a3fb77fbb204870d
67 N554bd513d35a44f38cddc54336046c6b schema:familyName de la Higuera
68 schema:givenName Colin
69 rdf:type schema:Person
70 N5f7b5c83d22945708433eae632d8f86c schema:name Springer Nature - SN SciGraph project
71 rdf:type schema:Organization
72 N9fd690331df94174a0f2733e617f5b35 schema:familyName Miclet
73 schema:givenName Laurent
74 rdf:type schema:Person
75 Na7b897467fb446bba8388f361d0329bd rdf:first sg:person.01335570111.71
76 rdf:rest rdf:nil
77 Nc07894b49f3942c697bc121f0896104c schema:name Springer Nature
78 rdf:type schema:Organisation
79 Nc6811e407dc54e6fa0dbeda8673fa464 schema:name dimensions_id
80 schema:value pub.1004884178
81 rdf:type schema:PropertyValue
82 Ncaad0837867b415a82d0c4094a1e5013 rdf:first sg:person.012635522717.12
83 rdf:rest Na7b897467fb446bba8388f361d0329bd
84 Ne8d784ef3934428e93e629c510f5386c schema:name doi
85 schema:value 10.1007/bfb0033358
86 rdf:type schema:PropertyValue
87 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
88 schema:name Language, Communication and Culture
89 rdf:type schema:DefinedTerm
90 anzsrc-for:2004 schema:inDefinedTermSet anzsrc-for:
91 schema:name Linguistics
92 rdf:type schema:DefinedTerm
93 sg:person.012635522717.12 schema:affiliation grid-institutes:grid.34421.30
94 schema:familyName Parekh
95 schema:givenName Rajesh
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012635522717.12
97 rdf:type schema:Person
98 sg:person.01335570111.71 schema:affiliation grid-institutes:grid.34421.30
99 schema:familyName Honavar
100 schema:givenName Vasant
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01335570111.71
102 rdf:type schema:Person
103 grid-institutes:grid.34421.30 schema:alternateName Artificial Intelligence Research Group Department of Computer Science, Iowa State University, 50011, Ames, IA, USA
104 schema:name Artificial Intelligence Research Group Department of Computer Science, Iowa State University, 50011, Ames, IA, USA
105 rdf:type schema:Organization
 




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


...