How considering incompatible state mergings may reduce the DFA induction search tree View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1998

AUTHORS

François Coste , Jacques Nicolas

ABSTRACT

A simple and effective method for DFA induction from positive and negative samples is the state merging method. The corresponding search space may be tree-structured, considering two subspaces for a given pair of states: the subspace where states are merged and the subspace where states remain different. Choosing different pairs leads to different sizes of space, due to state mergings dependencies. Thus, ordering the successive choices of these pairs is an important issue. Starting from a constraint characterization of incompatible state mergings, we show that this characterization allows to achieve better choices, i.e. to reduce the size of the search tree. Within this framework, we address the issue of learning the set of all minimal compatible DFA's. We propose a pruning criterion and experiment with several ordering criteria. The prefix order and a new entropy based criterion have exhibit the best results in our test sets. More... »

PAGES

199-210

Book

TITLE

Grammatical Inference

ISBN

978-3-540-64776-8
978-3-540-68707-8

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/16", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Studies in Human Society", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1606", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Political Science", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "IRISA-INRIA, Campus de Beaulieu, F-35042, Cedex, France", 
          "id": "http://www.grid.ac/institutes/grid.410368.8", 
          "name": [
            "IRISA-INRIA, Campus de Beaulieu, F-35042, Cedex, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Coste", 
        "givenName": "Fran\u00e7ois", 
        "id": "sg:person.012322041531.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012322041531.28"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IRISA-INRIA, Campus de Beaulieu, F-35042, Cedex, France", 
          "id": "http://www.grid.ac/institutes/grid.410368.8", 
          "name": [
            "IRISA-INRIA, Campus de Beaulieu, F-35042, Cedex, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Nicolas", 
        "givenName": "Jacques", 
        "id": "sg:person.01143715001.20", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01143715001.20"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1998", 
    "datePublishedReg": "1998-01-01", 
    "description": "A simple and effective method for DFA induction from positive and negative samples is the state merging method. The corresponding search space may be tree-structured, considering two subspaces for a given pair of states: the subspace where states are merged and the subspace where states remain different. Choosing different pairs leads to different sizes of space, due to state mergings dependencies. Thus, ordering the successive choices of these pairs is an important issue. Starting from a constraint characterization of incompatible state mergings, we show that this characterization allows to achieve better choices, i.e. to reduce the size of the search tree. Within this framework, we address the issue of learning the set of all minimal compatible DFA's. We propose a pruning criterion and experiment with several ordering criteria. The prefix order and a new entropy based criterion have exhibit the best results in our test sets.", 
    "editor": [
      {
        "familyName": "Honavar", 
        "givenName": "Vasant", 
        "type": "Person"
      }, 
      {
        "familyName": "Slutzki", 
        "givenName": "Giora", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/bfb0054076", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-64776-8", 
        "978-3-540-68707-8"
      ], 
      "name": "Grammatical Inference", 
      "type": "Book"
    }, 
    "keywords": [
      "different pairs", 
      "successive choices", 
      "effective method", 
      "method", 
      "induction", 
      "negative samples", 
      "samples", 
      "merging method", 
      "search space", 
      "space", 
      "subspace", 
      "pairs of states", 
      "pairs", 
      "state", 
      "different sizes", 
      "size", 
      "dependency", 
      "choice", 
      "important issue", 
      "issues", 
      "characterization", 
      "merging", 
      "best choice", 
      "trees", 
      "framework", 
      "set", 
      "DFA", 
      "criteria", 
      "experiments", 
      "order", 
      "new entropy", 
      "entropy", 
      "exhibit", 
      "good results", 
      "results", 
      "test set", 
      "DFA induction", 
      "state merging method", 
      "corresponding search space", 
      "state mergings dependencies", 
      "mergings dependencies", 
      "constraint characterization", 
      "incompatible state mergings", 
      "state merging", 
      "search tree", 
      "minimal compatible DFA's", 
      "compatible DFA's", 
      "prefix order", 
      "DFA induction search tree", 
      "induction search tree"
    ], 
    "name": "How considering incompatible state mergings may reduce the DFA induction search tree", 
    "pagination": "199-210", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1002492411"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bfb0054076"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/bfb0054076", 
      "https://app.dimensions.ai/details/publication/pub.1002492411"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:53", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_270.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/bfb0054076"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

122 TRIPLES      23 PREDICATES      76 URIs      69 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bfb0054076 schema:about anzsrc-for:16
2 anzsrc-for:1606
3 schema:author N2b926c8888cb43ac83447f1574397058
4 schema:datePublished 1998
5 schema:datePublishedReg 1998-01-01
6 schema:description A simple and effective method for DFA induction from positive and negative samples is the state merging method. The corresponding search space may be tree-structured, considering two subspaces for a given pair of states: the subspace where states are merged and the subspace where states remain different. Choosing different pairs leads to different sizes of space, due to state mergings dependencies. Thus, ordering the successive choices of these pairs is an important issue. Starting from a constraint characterization of incompatible state mergings, we show that this characterization allows to achieve better choices, i.e. to reduce the size of the search tree. Within this framework, we address the issue of learning the set of all minimal compatible DFA's. We propose a pruning criterion and experiment with several ordering criteria. The prefix order and a new entropy based criterion have exhibit the best results in our test sets.
7 schema:editor N0671b10ff28e4b1eb05af018842c8a1c
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nba0215df1eae4582ad2c94960ae1a475
12 schema:keywords DFA
13 DFA induction
14 DFA induction search tree
15 best choice
16 characterization
17 choice
18 compatible DFA's
19 constraint characterization
20 corresponding search space
21 criteria
22 dependency
23 different pairs
24 different sizes
25 effective method
26 entropy
27 exhibit
28 experiments
29 framework
30 good results
31 important issue
32 incompatible state mergings
33 induction
34 induction search tree
35 issues
36 merging
37 merging method
38 mergings dependencies
39 method
40 minimal compatible DFA's
41 negative samples
42 new entropy
43 order
44 pairs
45 pairs of states
46 prefix order
47 results
48 samples
49 search space
50 search tree
51 set
52 size
53 space
54 state
55 state merging
56 state merging method
57 state mergings dependencies
58 subspace
59 successive choices
60 test set
61 trees
62 schema:name How considering incompatible state mergings may reduce the DFA induction search tree
63 schema:pagination 199-210
64 schema:productId Ncafb8466a83b41b891a0f83b38eac366
65 Ne8f024950b354276ac11e1c16607e2c5
66 schema:publisher Nd7cc5e67c8924659b54c03055b085b4e
67 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002492411
68 https://doi.org/10.1007/bfb0054076
69 schema:sdDatePublished 2021-11-01T18:53
70 schema:sdLicense https://scigraph.springernature.com/explorer/license/
71 schema:sdPublisher N45fbbf74ae20415c91614f9bc8e360e2
72 schema:url https://doi.org/10.1007/bfb0054076
73 sgo:license sg:explorer/license/
74 sgo:sdDataset chapters
75 rdf:type schema:Chapter
76 N0671b10ff28e4b1eb05af018842c8a1c rdf:first N5dec06178647480abfe8574c01d490b6
77 rdf:rest N722b1cb0289a4e5f912ddef301b58063
78 N07843a66b6714a838d6d8edc4e1b8b25 rdf:first sg:person.01143715001.20
79 rdf:rest rdf:nil
80 N2b926c8888cb43ac83447f1574397058 rdf:first sg:person.012322041531.28
81 rdf:rest N07843a66b6714a838d6d8edc4e1b8b25
82 N45fbbf74ae20415c91614f9bc8e360e2 schema:name Springer Nature - SN SciGraph project
83 rdf:type schema:Organization
84 N5dec06178647480abfe8574c01d490b6 schema:familyName Honavar
85 schema:givenName Vasant
86 rdf:type schema:Person
87 N722b1cb0289a4e5f912ddef301b58063 rdf:first N7266a861cdb64114aa18e158f4b57c06
88 rdf:rest rdf:nil
89 N7266a861cdb64114aa18e158f4b57c06 schema:familyName Slutzki
90 schema:givenName Giora
91 rdf:type schema:Person
92 Nba0215df1eae4582ad2c94960ae1a475 schema:isbn 978-3-540-64776-8
93 978-3-540-68707-8
94 schema:name Grammatical Inference
95 rdf:type schema:Book
96 Ncafb8466a83b41b891a0f83b38eac366 schema:name doi
97 schema:value 10.1007/bfb0054076
98 rdf:type schema:PropertyValue
99 Nd7cc5e67c8924659b54c03055b085b4e schema:name Springer Nature
100 rdf:type schema:Organisation
101 Ne8f024950b354276ac11e1c16607e2c5 schema:name dimensions_id
102 schema:value pub.1002492411
103 rdf:type schema:PropertyValue
104 anzsrc-for:16 schema:inDefinedTermSet anzsrc-for:
105 schema:name Studies in Human Society
106 rdf:type schema:DefinedTerm
107 anzsrc-for:1606 schema:inDefinedTermSet anzsrc-for:
108 schema:name Political Science
109 rdf:type schema:DefinedTerm
110 sg:person.01143715001.20 schema:affiliation grid-institutes:grid.410368.8
111 schema:familyName Nicolas
112 schema:givenName Jacques
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01143715001.20
114 rdf:type schema:Person
115 sg:person.012322041531.28 schema:affiliation grid-institutes:grid.410368.8
116 schema:familyName Coste
117 schema:givenName François
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012322041531.28
119 rdf:type schema:Person
120 grid-institutes:grid.410368.8 schema:alternateName IRISA-INRIA, Campus de Beaulieu, F-35042, Cedex, France
121 schema:name IRISA-INRIA, Campus de Beaulieu, F-35042, Cedex, France
122 rdf:type schema:Organization
 




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


...