Computing All ℓ-Cover Automata Fast View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2011

AUTHORS

Artur Jeż , Andreas Maletti

ABSTRACT

Given a language L and a number ℓ, an ℓ-cover automaton for L is a DFA M such that its language coincides with L on all words of length at most ℓ. It is known that an equivalent minimal ℓ-cover automaton can be constructed in time \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{O}(n \log n)$\end{document}, where n is the number of states of M. This is achieved by a clever and sophisticated variant of Hopcroft’s algorithm, which computes the ℓ-similarity inside the main algorithm. This contribution presents an alternative simple algorithm with running time \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{O}(n \log n)$\end{document}, in which the computation is split into three phases. First, a compact representation of the gap table is created. Second, this representation is enriched with information about the length of a shortest word leading to the states. These two steps are independent of the parameter ℓ. Third, the ℓ-similarity is extracted by simple comparisons against ℓ. In particular, this approach allows the calculation of all the sizes of minimal ℓ-cover automata (for all valid ℓ) in the same time bound. More... »

PAGES

203-214

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/1701", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Institute of Computer Science, University of Wroc\u0142aw, ul. Joliot-Curie 15, 50\u2013383, Wroc\u0142aw, Poland", 
          "id": "http://www.grid.ac/institutes/grid.8505.8", 
          "name": [
            "Institute of Computer Science, University of Wroc\u0142aw, ul. Joliot-Curie 15, 50\u2013383, Wroc\u0142aw, Poland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Je\u017c", 
        "givenName": "Artur", 
        "id": "sg:person.015252371751.76", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute for Natural Language Processing, Universit\u00e4t Stuttgart, Azenbergstra\u00dfe\u00a012, 70174, Stuttgart, Germany", 
          "id": "http://www.grid.ac/institutes/grid.5719.a", 
          "name": [
            "Institute for Natural Language Processing, Universit\u00e4t Stuttgart, Azenbergstra\u00dfe\u00a012, 70174, Stuttgart, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Maletti", 
        "givenName": "Andreas", 
        "id": "sg:person.016645332751.01", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016645332751.01"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2011", 
    "datePublishedReg": "2011-01-01", 
    "description": "Given a language\u00a0L and a number\u00a0\u2113, an \u2113-cover automaton for\u00a0L is a DFA\u00a0M such that its language coincides with\u00a0L on all words of length at most\u00a0\u2113. It is known that an equivalent minimal \u2113-cover automaton can be constructed in time \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\mathcal{O}(n \\log n)$\\end{document}, where n\u00a0is the number of states of\u00a0M. This is achieved by a clever and sophisticated variant of Hopcroft\u2019s algorithm, which computes the \u2113-similarity inside the main algorithm. This contribution presents an alternative simple algorithm with running time \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\mathcal{O}(n \\log n)$\\end{document}, in which the computation is split into three phases. First, a compact representation of the gap\u00a0table is created. Second, this representation is enriched with information about the length of a\u00a0shortest word leading to the states. These two steps are independent of the parameter\u00a0\u2113. Third, the \u2113-similarity is extracted by simple comparisons against\u00a0\u2113. In particular, this approach allows the calculation of all the sizes of minimal \u2113-cover automata (for all valid\u00a0\u2113) in the same time bound.", 
    "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_19", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-22255-9", 
        "978-3-642-22256-6"
      ], 
      "name": "Implementation and Application of Automata", 
      "type": "Book"
    }, 
    "keywords": [
      "short words", 
      "words", 
      "language", 
      "sophisticated variants", 
      "words of length", 
      "representation", 
      "information", 
      "simple comparison", 
      "same time", 
      "time", 
      "contribution", 
      "compact representation", 
      "state", 
      "gap", 
      "approach", 
      "number of states", 
      "number", 
      "comparison", 
      "automata", 
      "DFA", 
      "computation", 
      "step", 
      "variants", 
      "algorithm", 
      "length", 
      "phase", 
      "table", 
      "size", 
      "simple algorithm", 
      "parameters", 
      "main algorithm", 
      "Hopcroft\u2019s algorithm", 
      "calculations", 
      "alternative simple algorithm"
    ], 
    "name": "Computing All \u2113-Cover Automata Fast", 
    "pagination": "203-214", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1010336549"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-22256-6_19"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-22256-6_19", 
      "https://app.dimensions.ai/details/publication/pub.1010336549"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:11", 
    "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_441.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-22256-6_19"
  }
]
 

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_19'

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_19'

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_19'

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_19'


 

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

119 TRIPLES      23 PREDICATES      60 URIs      53 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-22256-6_19 schema:about anzsrc-for:17
2 anzsrc-for:1701
3 schema:author Naf31a9905a524388a587f3c750c5cab3
4 schema:datePublished 2011
5 schema:datePublishedReg 2011-01-01
6 schema:description Given a language L and a number ℓ, an ℓ-cover automaton for L is a DFA M such that its language coincides with L on all words of length at most ℓ. It is known that an equivalent minimal ℓ-cover automaton can be constructed in time \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{O}(n \log n)$\end{document}, where n is the number of states of M. This is achieved by a clever and sophisticated variant of Hopcroft’s algorithm, which computes the ℓ-similarity inside the main algorithm. This contribution presents an alternative simple algorithm with running time \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{O}(n \log n)$\end{document}, in which the computation is split into three phases. First, a compact representation of the gap table is created. Second, this representation is enriched with information about the length of a shortest word leading to the states. These two steps are independent of the parameter ℓ. Third, the ℓ-similarity is extracted by simple comparisons against ℓ. In particular, this approach allows the calculation of all the sizes of minimal ℓ-cover automata (for all valid ℓ) in the same time bound.
7 schema:editor Ncca101842c4d41a982ce8c39c2cbbd8a
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N6ede738689d24391adc0ea7634c3dc53
12 schema:keywords DFA
13 Hopcroft’s algorithm
14 algorithm
15 alternative simple algorithm
16 approach
17 automata
18 calculations
19 compact representation
20 comparison
21 computation
22 contribution
23 gap
24 information
25 language
26 length
27 main algorithm
28 number
29 number of states
30 parameters
31 phase
32 representation
33 same time
34 short words
35 simple algorithm
36 simple comparison
37 size
38 sophisticated variants
39 state
40 step
41 table
42 time
43 variants
44 words
45 words of length
46 schema:name Computing All ℓ-Cover Automata Fast
47 schema:pagination 203-214
48 schema:productId N4deb3791f08947c6a1e0d59a6f9da249
49 Nce4d734f52ba4a838cf9df8a0db29f4a
50 schema:publisher Nb6ae2a92fe0d488089b6ca754beb4e03
51 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010336549
52 https://doi.org/10.1007/978-3-642-22256-6_19
53 schema:sdDatePublished 2021-12-01T20:11
54 schema:sdLicense https://scigraph.springernature.com/explorer/license/
55 schema:sdPublisher N65e791de2a454229996532c8e71295ad
56 schema:url https://doi.org/10.1007/978-3-642-22256-6_19
57 sgo:license sg:explorer/license/
58 sgo:sdDataset chapters
59 rdf:type schema:Chapter
60 N2b74b11d5b31443699c3b381bd2af232 schema:familyName Champarnaud
61 schema:givenName Jean-Marc
62 rdf:type schema:Person
63 N4deb3791f08947c6a1e0d59a6f9da249 schema:name dimensions_id
64 schema:value pub.1010336549
65 rdf:type schema:PropertyValue
66 N62c6e8927d2f4281ba97b01404915c38 rdf:first Naad6d6e65f2b464a955bf10e21eece59
67 rdf:rest rdf:nil
68 N65e791de2a454229996532c8e71295ad schema:name Springer Nature - SN SciGraph project
69 rdf:type schema:Organization
70 N6ede738689d24391adc0ea7634c3dc53 schema:isbn 978-3-642-22255-9
71 978-3-642-22256-6
72 schema:name Implementation and Application of Automata
73 rdf:type schema:Book
74 N82c4abb40058436d8da693a2ce653f8b schema:familyName Bouchou-Markhoff
75 schema:givenName Béatrice
76 rdf:type schema:Person
77 Naad6d6e65f2b464a955bf10e21eece59 schema:familyName Maurel
78 schema:givenName Denis
79 rdf:type schema:Person
80 Naf31a9905a524388a587f3c750c5cab3 rdf:first sg:person.015252371751.76
81 rdf:rest Ncd41d79a033f427c8c77f82eb403d679
82 Nb6ae2a92fe0d488089b6ca754beb4e03 schema:name Springer Nature
83 rdf:type schema:Organisation
84 Ncca101842c4d41a982ce8c39c2cbbd8a rdf:first N82c4abb40058436d8da693a2ce653f8b
85 rdf:rest Nce34820c69024b03937405191f65a783
86 Ncd41d79a033f427c8c77f82eb403d679 rdf:first sg:person.016645332751.01
87 rdf:rest rdf:nil
88 Nce34820c69024b03937405191f65a783 rdf:first Nd99cdb0f22d248729437481389a9e759
89 rdf:rest Ndfe5ee655b734b4fa595392fd052e1d6
90 Nce4d734f52ba4a838cf9df8a0db29f4a schema:name doi
91 schema:value 10.1007/978-3-642-22256-6_19
92 rdf:type schema:PropertyValue
93 Nd99cdb0f22d248729437481389a9e759 schema:familyName Caron
94 schema:givenName Pascal
95 rdf:type schema:Person
96 Ndfe5ee655b734b4fa595392fd052e1d6 rdf:first N2b74b11d5b31443699c3b381bd2af232
97 rdf:rest N62c6e8927d2f4281ba97b01404915c38
98 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
99 schema:name Psychology and Cognitive Sciences
100 rdf:type schema:DefinedTerm
101 anzsrc-for:1701 schema:inDefinedTermSet anzsrc-for:
102 schema:name Psychology
103 rdf:type schema:DefinedTerm
104 sg:person.015252371751.76 schema:affiliation grid-institutes:grid.8505.8
105 schema:familyName Jeż
106 schema:givenName Artur
107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76
108 rdf:type schema:Person
109 sg:person.016645332751.01 schema:affiliation grid-institutes:grid.5719.a
110 schema:familyName Maletti
111 schema:givenName Andreas
112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016645332751.01
113 rdf:type schema:Person
114 grid-institutes:grid.5719.a schema:alternateName Institute for Natural Language Processing, Universität Stuttgart, Azenbergstraße 12, 70174, Stuttgart, Germany
115 schema:name Institute for Natural Language Processing, Universität Stuttgart, Azenbergstraße 12, 70174, Stuttgart, Germany
116 rdf:type schema:Organization
117 grid-institutes:grid.8505.8 schema:alternateName Institute of Computer Science, University of Wrocław, ul. Joliot-Curie 15, 50–383, Wrocław, Poland
118 schema:name Institute of Computer Science, University of Wrocław, ul. Joliot-Curie 15, 50–383, Wrocław, Poland
119 rdf:type schema:Organization
 




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


...