Inference of finite automata: Reducing the search space with an ordering of pairs of states View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1998

AUTHORS

François Coste , Jacques Nicolas

ABSTRACT

We investigate the set of all minimal deterministic finite automata accepting a given set of words and rejecting another given set of words. We present several criteria to order the exploration of the corresponding search space. Three criteria are shown to have a very good behavior with respect to the pruning they imply in the search space. Best results have been obtained for the prefix ordering. We have also worked on a new dynamic ordering based on an entropy computation. More... »

PAGES

37-42

Book

TITLE

Machine Learning: ECML-98

ISBN

978-3-540-64417-0
978-3-540-69781-7

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/1702", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Cognitive Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "IRISA- IRRIA, Campus de Beaulieu, F-35042, Cedex, France", 
          "id": "http://www.grid.ac/institutes/grid.410368.8", 
          "name": [
            "IRISA- IRRIA, 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- IRRIA, Campus de Beaulieu, F-35042, Cedex, France", 
          "id": "http://www.grid.ac/institutes/grid.410368.8", 
          "name": [
            "IRISA- IRRIA, 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": "We investigate the set of all minimal deterministic finite automata accepting a given set of words and rejecting another given set of words. We present several criteria to order the exploration of the corresponding search space. Three criteria are shown to have a very good behavior with respect to the pruning they imply in the search space. Best results have been obtained for the prefix ordering. We have also worked on a new dynamic ordering based on an entropy computation.", 
    "editor": [
      {
        "familyName": "N\u00e9dellec", 
        "givenName": "Claire", 
        "type": "Person"
      }, 
      {
        "familyName": "Rouveirol", 
        "givenName": "C\u00e9line", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/bfb0026669", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-64417-0", 
        "978-3-540-69781-7"
      ], 
      "name": "Machine Learning: ECML-98", 
      "type": "Book"
    }, 
    "keywords": [
      "set of words", 
      "ordering of pairs", 
      "words", 
      "set", 
      "finite automata", 
      "exploration", 
      "good behavior", 
      "behavior", 
      "inference", 
      "minimal deterministic finite automaton", 
      "deterministic finite automata", 
      "automata", 
      "criteria", 
      "corresponding search space", 
      "search space", 
      "space", 
      "respect", 
      "pruning", 
      "good results", 
      "results", 
      "prefix ordering", 
      "ordering", 
      "dynamic ordering", 
      "entropy computation", 
      "computation", 
      "pairs", 
      "state", 
      "new dynamic ordering"
    ], 
    "name": "Inference of finite automata: Reducing the search space with an ordering of pairs of states", 
    "pagination": "37-42", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1019465732"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bfb0026669"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/bfb0026669", 
      "https://app.dimensions.ai/details/publication/pub.1019465732"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:56", 
    "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_329.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/bfb0026669"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

100 TRIPLES      23 PREDICATES      54 URIs      47 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bfb0026669 schema:about anzsrc-for:17
2 anzsrc-for:1702
3 schema:author N7b03f6dda54846a58005541e257d1d47
4 schema:datePublished 1998
5 schema:datePublishedReg 1998-01-01
6 schema:description We investigate the set of all minimal deterministic finite automata accepting a given set of words and rejecting another given set of words. We present several criteria to order the exploration of the corresponding search space. Three criteria are shown to have a very good behavior with respect to the pruning they imply in the search space. Best results have been obtained for the prefix ordering. We have also worked on a new dynamic ordering based on an entropy computation.
7 schema:editor N21c91fed1cfd41e6a900734bcb961207
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N418c79dd648f40c480de22017021f559
12 schema:keywords automata
13 behavior
14 computation
15 corresponding search space
16 criteria
17 deterministic finite automata
18 dynamic ordering
19 entropy computation
20 exploration
21 finite automata
22 good behavior
23 good results
24 inference
25 minimal deterministic finite automaton
26 new dynamic ordering
27 ordering
28 ordering of pairs
29 pairs
30 prefix ordering
31 pruning
32 respect
33 results
34 search space
35 set
36 set of words
37 space
38 state
39 words
40 schema:name Inference of finite automata: Reducing the search space with an ordering of pairs of states
41 schema:pagination 37-42
42 schema:productId N7006467e99ef4ff3ac0669b96688c49c
43 Ncf9420d279604e6fa67eb3d6a6eb08d5
44 schema:publisher Na6b3ff21814e43708548793fe5a6eebe
45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019465732
46 https://doi.org/10.1007/bfb0026669
47 schema:sdDatePublished 2021-11-01T18:56
48 schema:sdLicense https://scigraph.springernature.com/explorer/license/
49 schema:sdPublisher Nef3e0d6337f0475b92f9534c12966e01
50 schema:url https://doi.org/10.1007/bfb0026669
51 sgo:license sg:explorer/license/
52 sgo:sdDataset chapters
53 rdf:type schema:Chapter
54 N21c91fed1cfd41e6a900734bcb961207 rdf:first N4c4dca4612e146a185ce01314b34b2e6
55 rdf:rest N22fecac7cab44663973326bb409b2222
56 N22fecac7cab44663973326bb409b2222 rdf:first Nab532224aed54499be36e91f37e02f04
57 rdf:rest rdf:nil
58 N2cec321810da46188d6cdb871b0b36a8 rdf:first sg:person.01143715001.20
59 rdf:rest rdf:nil
60 N418c79dd648f40c480de22017021f559 schema:isbn 978-3-540-64417-0
61 978-3-540-69781-7
62 schema:name Machine Learning: ECML-98
63 rdf:type schema:Book
64 N4c4dca4612e146a185ce01314b34b2e6 schema:familyName Nédellec
65 schema:givenName Claire
66 rdf:type schema:Person
67 N7006467e99ef4ff3ac0669b96688c49c schema:name dimensions_id
68 schema:value pub.1019465732
69 rdf:type schema:PropertyValue
70 N7b03f6dda54846a58005541e257d1d47 rdf:first sg:person.012322041531.28
71 rdf:rest N2cec321810da46188d6cdb871b0b36a8
72 Na6b3ff21814e43708548793fe5a6eebe schema:name Springer Nature
73 rdf:type schema:Organisation
74 Nab532224aed54499be36e91f37e02f04 schema:familyName Rouveirol
75 schema:givenName Céline
76 rdf:type schema:Person
77 Ncf9420d279604e6fa67eb3d6a6eb08d5 schema:name doi
78 schema:value 10.1007/bfb0026669
79 rdf:type schema:PropertyValue
80 Nef3e0d6337f0475b92f9534c12966e01 schema:name Springer Nature - SN SciGraph project
81 rdf:type schema:Organization
82 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
83 schema:name Psychology and Cognitive Sciences
84 rdf:type schema:DefinedTerm
85 anzsrc-for:1702 schema:inDefinedTermSet anzsrc-for:
86 schema:name Cognitive Sciences
87 rdf:type schema:DefinedTerm
88 sg:person.01143715001.20 schema:affiliation grid-institutes:grid.410368.8
89 schema:familyName Nicolas
90 schema:givenName Jacques
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01143715001.20
92 rdf:type schema:Person
93 sg:person.012322041531.28 schema:affiliation grid-institutes:grid.410368.8
94 schema:familyName Coste
95 schema:givenName François
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012322041531.28
97 rdf:type schema:Person
98 grid-institutes:grid.410368.8 schema:alternateName IRISA- IRRIA, Campus de Beaulieu, F-35042, Cedex, France
99 schema:name IRISA- IRRIA, Campus de Beaulieu, F-35042, Cedex, France
100 rdf:type schema:Organization
 




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


...