Random Generation of Deterministic Tree (Walking) Automata View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2009

AUTHORS

Pierre-Cyrille Héam , Cyril Nicaud , Sylvain Schmitz

ABSTRACT

Uniform random generators deliver a simple empirical means to estimate the average complexity of an algorithm. We present a general rejection algorithm that generates sequential letter-to-letter transducers up to isomorphism. We tailor this general scheme to randomly generate deterministic tree walking automata and deterministic top-down tree automata. We apply our implementation of the generator to the estimation of the average complexity of a deterministic tree walking automata to nondeterministic top-down tree automata construction we also implemented. More... »

PAGES

115-124

Book

TITLE

Implementation and Application of Automata

ISBN

978-3-642-02978-3
978-3-642-02979-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-02979-0_15

DOI

http://dx.doi.org/10.1007/978-3-642-02979-0_15

DIMENSIONS

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


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/0501", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Ecological Applications", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/05", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Environmental Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Laboratoire Sp\u00e9cification et V\u00e9rification", 
          "id": "https://www.grid.ac/institutes/grid.464035.0", 
          "name": [
            "LIFC, Universit\u00e9 de Franche-Comt\u00e9 & INRIA, Besan\u00e7on, France", 
            "LSV, ENS Cachan & CNRS & INRIA, Cachan, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "H\u00e9am", 
        "givenName": "Pierre-Cyrille", 
        "id": "sg:person.012233352623.91", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012233352623.91"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Laboratoire d'Informatique Gaspard-Monge", 
          "id": "https://www.grid.ac/institutes/grid.462940.d", 
          "name": [
            "LIGM, Universit\u00e9 Paris Est & CNRS, Marne-la-Vall\u00e9e, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Nicaud", 
        "givenName": "Cyril", 
        "id": "sg:person.016640760301.07", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016640760301.07"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Laboratoire Sp\u00e9cification et V\u00e9rification", 
          "id": "https://www.grid.ac/institutes/grid.464035.0", 
          "name": [
            "LSV, ENS Cachan & CNRS & INRIA, Cachan, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Schmitz", 
        "givenName": "Sylvain", 
        "id": "sg:person.011452353057.40", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011452353057.40"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/978-3-642-60207-8_7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001808103", 
          "https://doi.org/10.1007/978-3-642-60207-8_7"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-60207-8_7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001808103", 
          "https://doi.org/10.1007/978-3-642-60207-8_7"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-70844-5_17", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014143640", 
          "https://doi.org/10.1007/978-3-540-70844-5_17"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2007.04.001", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024157878"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-76336-9_28", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027706994", 
          "https://doi.org/10.1007/978-3-540-76336-9_28"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-76336-9_28", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027706994", 
          "https://doi.org/10.1007/978-3-540-76336-9_28"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11817963_5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028708675", 
          "https://doi.org/10.1007/11817963_5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11817963_5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028708675", 
          "https://doi.org/10.1007/11817963_5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1376916.1376952", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031920229"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-00768-2_3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043779185", 
          "https://doi.org/10.1007/978-3-642-00768-2_3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-00768-2_3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043779185", 
          "https://doi.org/10.1007/978-3-642-00768-2_3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1111627.1111631", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045309995"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2004.03.072", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047924754"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11591191_28", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049448434", 
          "https://doi.org/10.1007/11591191_28"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11591191_28", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049448434", 
          "https://doi.org/10.1007/11591191_28"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/601858.601869", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051456921"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/050645427", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062846729"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "Uniform random generators deliver a simple empirical means to estimate the average complexity of an algorithm. We present a general rejection algorithm that generates sequential letter-to-letter transducers up to isomorphism. We tailor this general scheme to randomly generate deterministic tree walking automata and deterministic top-down tree automata. We apply our implementation of the generator to the estimation of the average complexity of a deterministic tree walking automata to nondeterministic top-down tree automata construction we also implemented.", 
    "editor": [
      {
        "familyName": "Maneth", 
        "givenName": "Sebastian", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-02979-0_15", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-02978-3", 
        "978-3-642-02979-0"
      ], 
      "name": "Implementation and Application of Automata", 
      "type": "Book"
    }, 
    "name": "Random Generation of Deterministic Tree (Walking) Automata", 
    "pagination": "115-124", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1039258176"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-02979-0_15"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "bb012b36ec8c04effc5d48d13951206e267c8de395befd2b284d8883a0557d49"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-02979-0_15", 
      "https://app.dimensions.ai/details/publication/pub.1039258176"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T07:14", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000353_0000000353/records_45366_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-642-02979-0_15"
  }
]
 

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/978-3-642-02979-0_15'

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/978-3-642-02979-0_15'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-02979-0_15'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-02979-0_15'


 

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

125 TRIPLES      23 PREDICATES      39 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-02979-0_15 schema:about anzsrc-for:05
2 anzsrc-for:0501
3 schema:author N85d34858621244b6b30983989fef7a05
4 schema:citation sg:pub.10.1007/11591191_28
5 sg:pub.10.1007/11817963_5
6 sg:pub.10.1007/978-3-540-70844-5_17
7 sg:pub.10.1007/978-3-540-76336-9_28
8 sg:pub.10.1007/978-3-642-00768-2_3
9 sg:pub.10.1007/978-3-642-60207-8_7
10 https://doi.org/10.1016/j.tcs.2004.03.072
11 https://doi.org/10.1016/j.tcs.2007.04.001
12 https://doi.org/10.1137/050645427
13 https://doi.org/10.1145/1111627.1111631
14 https://doi.org/10.1145/1376916.1376952
15 https://doi.org/10.1145/601858.601869
16 schema:datePublished 2009
17 schema:datePublishedReg 2009-01-01
18 schema:description Uniform random generators deliver a simple empirical means to estimate the average complexity of an algorithm. We present a general rejection algorithm that generates sequential letter-to-letter transducers up to isomorphism. We tailor this general scheme to randomly generate deterministic tree walking automata and deterministic top-down tree automata. We apply our implementation of the generator to the estimation of the average complexity of a deterministic tree walking automata to nondeterministic top-down tree automata construction we also implemented.
19 schema:editor Nda14c3cb7e1e462d9d47ba2bc381d733
20 schema:genre chapter
21 schema:inLanguage en
22 schema:isAccessibleForFree true
23 schema:isPartOf N3780716132fc4e79a6a5f60e6816960f
24 schema:name Random Generation of Deterministic Tree (Walking) Automata
25 schema:pagination 115-124
26 schema:productId N3bbd526ea461472e9d01d6b6bb92480e
27 N4219d910bef643a0b2ab28e786521be3
28 N671c200278ff46a7940ad9cf3a63b383
29 schema:publisher N138ce7a357f44629b3b2bdc0672a2aef
30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039258176
31 https://doi.org/10.1007/978-3-642-02979-0_15
32 schema:sdDatePublished 2019-04-16T07:14
33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
34 schema:sdPublisher N119869f5a8ac4f269fb4f7890f2ab736
35 schema:url https://link.springer.com/10.1007%2F978-3-642-02979-0_15
36 sgo:license sg:explorer/license/
37 sgo:sdDataset chapters
38 rdf:type schema:Chapter
39 N119869f5a8ac4f269fb4f7890f2ab736 schema:name Springer Nature - SN SciGraph project
40 rdf:type schema:Organization
41 N138ce7a357f44629b3b2bdc0672a2aef schema:location Berlin, Heidelberg
42 schema:name Springer Berlin Heidelberg
43 rdf:type schema:Organisation
44 N3780716132fc4e79a6a5f60e6816960f schema:isbn 978-3-642-02978-3
45 978-3-642-02979-0
46 schema:name Implementation and Application of Automata
47 rdf:type schema:Book
48 N3bbd526ea461472e9d01d6b6bb92480e schema:name dimensions_id
49 schema:value pub.1039258176
50 rdf:type schema:PropertyValue
51 N4219d910bef643a0b2ab28e786521be3 schema:name doi
52 schema:value 10.1007/978-3-642-02979-0_15
53 rdf:type schema:PropertyValue
54 N671c200278ff46a7940ad9cf3a63b383 schema:name readcube_id
55 schema:value bb012b36ec8c04effc5d48d13951206e267c8de395befd2b284d8883a0557d49
56 rdf:type schema:PropertyValue
57 N751dbbf1499e4cd4964fc4f1dddcc0af rdf:first sg:person.011452353057.40
58 rdf:rest rdf:nil
59 N85d34858621244b6b30983989fef7a05 rdf:first sg:person.012233352623.91
60 rdf:rest N8fd9f1714a2a4ffaa2d41c4245cecf83
61 N8fd9f1714a2a4ffaa2d41c4245cecf83 rdf:first sg:person.016640760301.07
62 rdf:rest N751dbbf1499e4cd4964fc4f1dddcc0af
63 N92cbbccc198c44a3922596639a634c76 schema:familyName Maneth
64 schema:givenName Sebastian
65 rdf:type schema:Person
66 Nda14c3cb7e1e462d9d47ba2bc381d733 rdf:first N92cbbccc198c44a3922596639a634c76
67 rdf:rest rdf:nil
68 anzsrc-for:05 schema:inDefinedTermSet anzsrc-for:
69 schema:name Environmental Sciences
70 rdf:type schema:DefinedTerm
71 anzsrc-for:0501 schema:inDefinedTermSet anzsrc-for:
72 schema:name Ecological Applications
73 rdf:type schema:DefinedTerm
74 sg:person.011452353057.40 schema:affiliation https://www.grid.ac/institutes/grid.464035.0
75 schema:familyName Schmitz
76 schema:givenName Sylvain
77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011452353057.40
78 rdf:type schema:Person
79 sg:person.012233352623.91 schema:affiliation https://www.grid.ac/institutes/grid.464035.0
80 schema:familyName Héam
81 schema:givenName Pierre-Cyrille
82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012233352623.91
83 rdf:type schema:Person
84 sg:person.016640760301.07 schema:affiliation https://www.grid.ac/institutes/grid.462940.d
85 schema:familyName Nicaud
86 schema:givenName Cyril
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016640760301.07
88 rdf:type schema:Person
89 sg:pub.10.1007/11591191_28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049448434
90 https://doi.org/10.1007/11591191_28
91 rdf:type schema:CreativeWork
92 sg:pub.10.1007/11817963_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028708675
93 https://doi.org/10.1007/11817963_5
94 rdf:type schema:CreativeWork
95 sg:pub.10.1007/978-3-540-70844-5_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014143640
96 https://doi.org/10.1007/978-3-540-70844-5_17
97 rdf:type schema:CreativeWork
98 sg:pub.10.1007/978-3-540-76336-9_28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027706994
99 https://doi.org/10.1007/978-3-540-76336-9_28
100 rdf:type schema:CreativeWork
101 sg:pub.10.1007/978-3-642-00768-2_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043779185
102 https://doi.org/10.1007/978-3-642-00768-2_3
103 rdf:type schema:CreativeWork
104 sg:pub.10.1007/978-3-642-60207-8_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001808103
105 https://doi.org/10.1007/978-3-642-60207-8_7
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1016/j.tcs.2004.03.072 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047924754
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1016/j.tcs.2007.04.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024157878
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1137/050645427 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062846729
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1145/1111627.1111631 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045309995
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1145/1376916.1376952 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031920229
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1145/601858.601869 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051456921
118 rdf:type schema:CreativeWork
119 https://www.grid.ac/institutes/grid.462940.d schema:alternateName Laboratoire d'Informatique Gaspard-Monge
120 schema:name LIGM, Université Paris Est & CNRS, Marne-la-Vallée, France
121 rdf:type schema:Organization
122 https://www.grid.ac/institutes/grid.464035.0 schema:alternateName Laboratoire Spécification et Vérification
123 schema:name LIFC, Université de Franche-Comté & INRIA, Besançon, France
124 LSV, ENS Cachan & CNRS & INRIA, Cachan, France
125 rdf:type schema:Organization
 




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


...