Random Generation of Deterministic Acyclic Automata Using Markov Chains View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2011

AUTHORS

Vincent Carnino , Sven De Felice

ABSTRACT

In this article we propose an algorithm, based on Markov chain techniques, to generate random automata that are deterministic, accessible and acyclic. The distribution of the output approaches the uniform distribution on n-state such automata. We then show how to adapt this algorithm in order to generate minimal acyclic automata with n states almost uniformly. More... »

PAGES

65-75

References to SciGraph publications

Book

TITLE

Implementation and Application of Automata

ISBN

978-3-642-22255-9
978-3-642-22256-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-22256-6_7

DOI

http://dx.doi.org/10.1007/978-3-642-22256-6_7

DIMENSIONS

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


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/1606", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Political Science", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Laboratoire d'Informatique Gaspard-Monge", 
          "id": "https://www.grid.ac/institutes/grid.462940.d", 
          "name": [
            "LIGM, UMR 8049, Universit\u00e9 Paris-Est et CNRS, 77454, Marne-la-Vall\u00e9e, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Carnino", 
        "givenName": "Vincent", 
        "id": "sg:person.015775264501.67", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015775264501.67"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Laboratoire d'Informatique Gaspard-Monge", 
          "id": "https://www.grid.ac/institutes/grid.462940.d", 
          "name": [
            "LIGM, UMR 8049, Universit\u00e9 Paris-Est et CNRS, 77454, Marne-la-Vall\u00e9e, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "De Felice", 
        "givenName": "Sven", 
        "id": "sg:person.011240225026.42", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011240225026.42"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0304-3975(94)90226-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012477802"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0304-3975(97)00296-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018775213"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0304-3975(92)90142-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022358047"
        ], 
        "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": "https://doi.org/10.1016/j.dam.2005.06.009", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024250927"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.ipl.2003.06.002", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024485965"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/s0963548304006315", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028516816"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2010.05.036", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033292928"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2010.05.023", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033882731"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-02979-0_23", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044992612", 
          "https://doi.org/10.1007/978-3-642-02979-0_23"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-02979-0_23", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044992612", 
          "https://doi.org/10.1007/978-3-642-02979-0_23"
        ], 
        "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": "https://doi.org/10.1016/s1571-0653(04)00394-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048492149"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/s0129054108005930", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062896886"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2011", 
    "datePublishedReg": "2011-01-01", 
    "description": "In this article we propose an algorithm, based on Markov chain techniques, to generate random automata that are deterministic, accessible and acyclic. The distribution of the output approaches the uniform distribution on n-state such automata. We then show how to adapt this algorithm in order to generate minimal acyclic automata with n states almost uniformly.", 
    "editor": [
      {
        "familyName": "Bouchou-Markhoff", 
        "givenName": "B\u00e9atrice", 
        "type": "Person"
      }, 
      {
        "familyName": "Caron", 
        "givenName": "Pascal", 
        "type": "Person"
      }, 
      {
        "familyName": "Champarnaud", 
        "givenName": "Jean-Marc", 
        "type": "Person"
      }, 
      {
        "familyName": "Maurel", 
        "givenName": "Denis", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-22256-6_7", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-22255-9", 
        "978-3-642-22256-6"
      ], 
      "name": "Implementation and Application of Automata", 
      "type": "Book"
    }, 
    "name": "Random Generation of Deterministic Acyclic Automata Using Markov Chains", 
    "pagination": "65-75", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1048259078"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-22256-6_7"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "e5e64916ae157dc193d3d4f234b6f834c8706982434f2fee0899f820991aea0d"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-22256-6_7", 
      "https://app.dimensions.ai/details/publication/pub.1048259078"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T08:55", 
    "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/0000000369_0000000369/records_68947_00000001.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-642-22256-6_7"
  }
]
 

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-22256-6_7'

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-22256-6_7'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-22256-6_7'

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-22256-6_7'


 

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

127 TRIPLES      23 PREDICATES      40 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-22256-6_7 schema:about anzsrc-for:16
2 anzsrc-for:1606
3 schema:author N456dbdc8859c4fae83b7ff72f7e8addf
4 schema:citation sg:pub.10.1007/978-3-642-02979-0_23
5 https://doi.org/10.1016/0304-3975(92)90142-3
6 https://doi.org/10.1016/0304-3975(94)90226-7
7 https://doi.org/10.1016/j.dam.2005.06.009
8 https://doi.org/10.1016/j.ipl.2003.06.002
9 https://doi.org/10.1016/j.tcs.2004.03.072
10 https://doi.org/10.1016/j.tcs.2007.04.001
11 https://doi.org/10.1016/j.tcs.2010.05.023
12 https://doi.org/10.1016/j.tcs.2010.05.036
13 https://doi.org/10.1016/s0304-3975(97)00296-x
14 https://doi.org/10.1016/s1571-0653(04)00394-4
15 https://doi.org/10.1017/s0963548304006315
16 https://doi.org/10.1142/s0129054108005930
17 schema:datePublished 2011
18 schema:datePublishedReg 2011-01-01
19 schema:description In this article we propose an algorithm, based on Markov chain techniques, to generate random automata that are deterministic, accessible and acyclic. The distribution of the output approaches the uniform distribution on n-state such automata. We then show how to adapt this algorithm in order to generate minimal acyclic automata with n states almost uniformly.
20 schema:editor N3f8a3b869e314957ac778262eecde5b2
21 schema:genre chapter
22 schema:inLanguage en
23 schema:isAccessibleForFree true
24 schema:isPartOf N964659246eb74b43839d8b3706cf79cc
25 schema:name Random Generation of Deterministic Acyclic Automata Using Markov Chains
26 schema:pagination 65-75
27 schema:productId N2209871455a448c09b7a6d8767efd9e7
28 N53edabcc7f8b4feaa9748e0fe1e809be
29 Nc4da96e243ab4e5aab617b670ecfae3b
30 schema:publisher N625b0fa9184b405c9cd2593dbde64f03
31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048259078
32 https://doi.org/10.1007/978-3-642-22256-6_7
33 schema:sdDatePublished 2019-04-16T08:55
34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
35 schema:sdPublisher N6a87c7fe3d7241d8a72e264a7b83024f
36 schema:url https://link.springer.com/10.1007%2F978-3-642-22256-6_7
37 sgo:license sg:explorer/license/
38 sgo:sdDataset chapters
39 rdf:type schema:Chapter
40 N015344a3c0a6411796cb670630787389 rdf:first N4dd13a0fefb948b9a3a4169e48d2e1b4
41 rdf:rest N75d745c2f68f4bb6a8e7449e84225746
42 N020947413faf4924a2b9a51130b42d2e rdf:first sg:person.011240225026.42
43 rdf:rest rdf:nil
44 N1d7568905cb5460eb79941d505396039 schema:familyName Maurel
45 schema:givenName Denis
46 rdf:type schema:Person
47 N2209871455a448c09b7a6d8767efd9e7 schema:name doi
48 schema:value 10.1007/978-3-642-22256-6_7
49 rdf:type schema:PropertyValue
50 N3f8a3b869e314957ac778262eecde5b2 rdf:first Ncd5b8751a9f64b809762c42e25803fd1
51 rdf:rest Nf11f58f896244611a9c15c1ec2d3def9
52 N456dbdc8859c4fae83b7ff72f7e8addf rdf:first sg:person.015775264501.67
53 rdf:rest N020947413faf4924a2b9a51130b42d2e
54 N4dd13a0fefb948b9a3a4169e48d2e1b4 schema:familyName Champarnaud
55 schema:givenName Jean-Marc
56 rdf:type schema:Person
57 N53edabcc7f8b4feaa9748e0fe1e809be schema:name readcube_id
58 schema:value e5e64916ae157dc193d3d4f234b6f834c8706982434f2fee0899f820991aea0d
59 rdf:type schema:PropertyValue
60 N625b0fa9184b405c9cd2593dbde64f03 schema:location Berlin, Heidelberg
61 schema:name Springer Berlin Heidelberg
62 rdf:type schema:Organisation
63 N6a87c7fe3d7241d8a72e264a7b83024f schema:name Springer Nature - SN SciGraph project
64 rdf:type schema:Organization
65 N75d745c2f68f4bb6a8e7449e84225746 rdf:first N1d7568905cb5460eb79941d505396039
66 rdf:rest rdf:nil
67 N964659246eb74b43839d8b3706cf79cc schema:isbn 978-3-642-22255-9
68 978-3-642-22256-6
69 schema:name Implementation and Application of Automata
70 rdf:type schema:Book
71 Nc4da96e243ab4e5aab617b670ecfae3b schema:name dimensions_id
72 schema:value pub.1048259078
73 rdf:type schema:PropertyValue
74 Ncd5b8751a9f64b809762c42e25803fd1 schema:familyName Bouchou-Markhoff
75 schema:givenName Béatrice
76 rdf:type schema:Person
77 Ndbcb28a123d84d9680d0cc6ded8294af schema:familyName Caron
78 schema:givenName Pascal
79 rdf:type schema:Person
80 Nf11f58f896244611a9c15c1ec2d3def9 rdf:first Ndbcb28a123d84d9680d0cc6ded8294af
81 rdf:rest N015344a3c0a6411796cb670630787389
82 anzsrc-for:16 schema:inDefinedTermSet anzsrc-for:
83 schema:name Studies in Human Society
84 rdf:type schema:DefinedTerm
85 anzsrc-for:1606 schema:inDefinedTermSet anzsrc-for:
86 schema:name Political Science
87 rdf:type schema:DefinedTerm
88 sg:person.011240225026.42 schema:affiliation https://www.grid.ac/institutes/grid.462940.d
89 schema:familyName De Felice
90 schema:givenName Sven
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011240225026.42
92 rdf:type schema:Person
93 sg:person.015775264501.67 schema:affiliation https://www.grid.ac/institutes/grid.462940.d
94 schema:familyName Carnino
95 schema:givenName Vincent
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015775264501.67
97 rdf:type schema:Person
98 sg:pub.10.1007/978-3-642-02979-0_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044992612
99 https://doi.org/10.1007/978-3-642-02979-0_23
100 rdf:type schema:CreativeWork
101 https://doi.org/10.1016/0304-3975(92)90142-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022358047
102 rdf:type schema:CreativeWork
103 https://doi.org/10.1016/0304-3975(94)90226-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012477802
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1016/j.dam.2005.06.009 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024250927
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1016/j.ipl.2003.06.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024485965
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1016/j.tcs.2004.03.072 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047924754
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1016/j.tcs.2007.04.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024157878
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1016/j.tcs.2010.05.023 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033882731
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1016/j.tcs.2010.05.036 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033292928
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1016/s0304-3975(97)00296-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1018775213
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1016/s1571-0653(04)00394-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048492149
120 rdf:type schema:CreativeWork
121 https://doi.org/10.1017/s0963548304006315 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028516816
122 rdf:type schema:CreativeWork
123 https://doi.org/10.1142/s0129054108005930 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062896886
124 rdf:type schema:CreativeWork
125 https://www.grid.ac/institutes/grid.462940.d schema:alternateName Laboratoire d'Informatique Gaspard-Monge
126 schema:name LIGM, UMR 8049, Université Paris-Est et CNRS, 77454, Marne-la-Vallée, France
127 rdf:type schema:Organization
 




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


...