# Computing All ℓ-Cover Automata Fast

Ontology type: schema:Chapter

### Chapter Info

DATE

2011

AUTHORS 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

### 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_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:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"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": "2022-01-01T19:09",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_154.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-642-22256-6_19"
}
]

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'

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
2 anzsrc-for:1701
3 schema:author Nef3cd2f5a3364b0ba74246f8f1834b05
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 N21a471710aee475ba80a53fcebf1ba1e
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N488469c44c8b4a0b8573bc55ee78b078
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 N307944f65831421d898c336560dc0413
49 Nda4b391822d443818f662328a227a0f9
50 schema:publisher Nd28300721b004318a43039d57caaa873
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 2022-01-01T19:09
55 schema:sdPublisher N21808606f7d347c78b403b219c525abe
56 schema:url https://doi.org/10.1007/978-3-642-22256-6_19
58 sgo:sdDataset chapters
59 rdf:type schema:Chapter
60 N21808606f7d347c78b403b219c525abe schema:name Springer Nature - SN SciGraph project
61 rdf:type schema:Organization
62 N21a471710aee475ba80a53fcebf1ba1e rdf:first N4b675b6da308488f89bbeec7a5356852
63 rdf:rest N869e815a00ed4b0c94835c23f74254a6
64 N307944f65831421d898c336560dc0413 schema:name dimensions_id
65 schema:value pub.1010336549
66 rdf:type schema:PropertyValue
67 N488469c44c8b4a0b8573bc55ee78b078 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 N4b675b6da308488f89bbeec7a5356852 schema:familyName Bouchou-Markhoff
72 schema:givenName Béatrice
73 rdf:type schema:Person
74 N6f13ce6a5b1f4eecb8f8cfe2f0b6f9b6 rdf:first Nd7139d69e6294e2caf5ace00881e4a95
75 rdf:rest rdf:nil
77 rdf:rest Nc1e411766d8b47f3b6fc8b6eeb367ab2
79 schema:givenName Pascal
80 rdf:type schema:Person
81 Nb83821facf42441fbd28b8730490afe5 rdf:first sg:person.016645332751.01
82 rdf:rest rdf:nil
83 Nb8596dbf5bb34e81afd176f109ff32a2 schema:familyName Champarnaud
84 schema:givenName Jean-Marc
85 rdf:type schema:Person
86 Nc1e411766d8b47f3b6fc8b6eeb367ab2 rdf:first Nb8596dbf5bb34e81afd176f109ff32a2
87 rdf:rest N6f13ce6a5b1f4eecb8f8cfe2f0b6f9b6
88 Nd28300721b004318a43039d57caaa873 schema:name Springer Nature
89 rdf:type schema:Organisation
90 Nd7139d69e6294e2caf5ace00881e4a95 schema:familyName Maurel
91 schema:givenName Denis
92 rdf:type schema:Person
93 Nda4b391822d443818f662328a227a0f9 schema:name doi
94 schema:value 10.1007/978-3-642-22256-6_19
95 rdf:type schema:PropertyValue
96 Nef3cd2f5a3364b0ba74246f8f1834b05 rdf:first sg:person.015252371751.76
97 rdf:rest Nb83821facf42441fbd28b8730490afe5
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