# On Minimising Automata with Errors

Ontology type: schema:Chapter      Open Access: True

### Chapter Info

DATE

2011

AUTHORS ABSTRACT

The problem of k-minimisation for a DFA M is the computation of a smallest DFA N (where the size |M | of a DFA M is the size of the domain of the transition function) such that L(M) ΔL(N) ⊆ Σ< k, which means that their recognized languages differ only on words of length less than k. The previously best algorithm, which runs 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}(\mid M \mid{\rm log}^{2} n)$\end{document} where n is the number of states, is extended to DFAs with partial transition functions. Moreover, a faster \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{O}(\mid M \mid\log n)$\end{document} algorithm for DFAs that recognise finite languages is presented. In comparison to the previous algorithm for total DFAs, the new algorithm is much simpler and allows the calculation of a k-minimal DFA for each k in parallel. Secondly, it is demonstrated that calculating the least number of introduced errors is hard: Given a DFA M and numbers k and m, it is NP-hard to decide whether there exists a k-minimal DFA N with |L(M) ΔL(N) ≤ m. A similar result holds for hyper-minimisation of DFAs in general: Given a DFA M and numbers s and m, it is NP-hard to decide whether there exists a DFA N with at most s states such that |L(M) ΔL(N) ≤ m. More... »

PAGES

327-338

### Book

TITLE

Mathematical Foundations of Computer Science 2011

ISBN

978-3-642-22992-3
978-3-642-22993-0

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-22993-0_31

DOI

http://dx.doi.org/10.1007/978-3-642-22993-0_31

DIMENSIONS

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

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/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Computation Theory and Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Institute of Computer Science, University of Wroc\u0142aw, ul. Joliot-Curie\u00a015, 50-383, Wroc\u0142aw, Poland",
"id": "http://www.grid.ac/institutes/grid.8505.8",
"name": [
"Institute of Computer Science, University of Wroc\u0142aw, ul. Joliot-Curie\u00a015, 50-383, Wroc\u0142aw, Poland"
],
"type": "Organization"
},
"familyName": "Gawrychowski",
"givenName": "Pawe\u0142",
"id": "sg:person.013657430751.28",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013657430751.28"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Institute of Computer Science, University of Wroc\u0142aw, ul. Joliot-Curie\u00a015, 50-383, Wroc\u0142aw, Poland",
"id": "http://www.grid.ac/institutes/grid.8505.8",
"name": [
"Institute of Computer Science, University of Wroc\u0142aw, ul. Joliot-Curie\u00a015, 50-383, 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": "The problem of k-minimisation for a DFA\u00a0M is the computation of a smallest DFA\u00a0N (where the size\u00a0|M | of a DFA\u00a0M is the size of the domain of the transition function) such that L(M) \u0394L(N)\u2009\u2286\u2009\u03a3<\u2009k, which means that their recognized languages differ only on words of length less than\u00a0k. The previously best algorithm, which runs in time\u00a0\\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}(\\mid M \\mid{\\rm log}^{2} n)$\\end{document} where n\u00a0is the number of states, is extended to DFAs with partial transition functions. Moreover, a faster \\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}(\\mid M \\mid\\log n)$\\end{document}\u00a0algorithm for DFAs that recognise finite languages is presented. In comparison to the previous algorithm for total DFAs, the new algorithm is much simpler and allows the calculation of a\u00a0k-minimal DFA for each\u00a0k in parallel. Secondly, it is demonstrated that calculating the least number of introduced errors is hard: Given a DFA\u00a0M and numbers k\u00a0and\u00a0m, it is NP-hard to decide whether there exists a k-minimal DFA\u00a0N with |L(M) \u0394L(N)\u2009\u2264\u2009m. A\u00a0similar result holds for hyper-minimisation of DFAs in general: Given a DFA\u00a0M and numbers s\u00a0and\u00a0m, it is NP-hard to decide whether there exists a DFA\u00a0N with at most s\u00a0states such that |L(M) \u0394L(N)\u2009\u2264\u2009m.",
"editor": [
{
"familyName": "Murlak",
"givenName": "Filip",
"type": "Person"
},
{
"familyName": "Sankowski",
"givenName": "Piotr",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-642-22993-0_31",
"inLanguage": "en",
"isAccessibleForFree": true,
"isPartOf": {
"isbn": [
"978-3-642-22992-3",
"978-3-642-22993-0"
],
"name": "Mathematical Foundations of Computer Science 2011",
"type": "Book"
},
"keywords": [
"best algorithm",
"previous algorithms",
"algorithm",
"new algorithm",
"smallest DFA",
"number of states",
"language",
"minimal DFA",
"least number",
"NP",
"transition function",
"finite languages",
"computation",
"error",
"DFA",
"automata",
"words of length",
"number k",
"number",
"minimisation",
"words",
"state",
"parallel",
"time",
"results",
"function",
"comparison",
"calculations",
"length",
"similar results",
"number S",
"problem",
"partial transition functions",
"total DFAs",
"Minimising Automata"
],
"name": "On Minimising Automata with Errors",
"pagination": "327-338",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1018296198"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-642-22993-0_31"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-642-22993-0_31",
"https://app.dimensions.ai/details/publication/pub.1018296198"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-01-01T19:11",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_190.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-642-22993-0_31"
}
]

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-22993-0_31'

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-22993-0_31'

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

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-22993-0_31'

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

117 TRIPLES      23 PREDICATES      61 URIs      54 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0802
3 schema:author N99b436ca4145464d832bc5f08d5d45c1
4 schema:datePublished 2011
5 schema:datePublishedReg 2011-01-01
6 schema:description The problem of k-minimisation for a DFA M is the computation of a smallest DFA N (where the size |M | of a DFA M is the size of the domain of the transition function) such that L(M) ΔL(N) ⊆ Σ< k, which means that their recognized languages differ only on words of length less than k. The previously best algorithm, which runs 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}(\mid M \mid{\rm log}^{2} n)$\end{document} where n is the number of states, is extended to DFAs with partial transition functions. Moreover, a faster \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{O}(\mid M \mid\log n)$\end{document} algorithm for DFAs that recognise finite languages is presented. In comparison to the previous algorithm for total DFAs, the new algorithm is much simpler and allows the calculation of a k-minimal DFA for each k in parallel. Secondly, it is demonstrated that calculating the least number of introduced errors is hard: Given a DFA M and numbers k and m, it is NP-hard to decide whether there exists a k-minimal DFA N with |L(M) ΔL(N) ≤ m. A similar result holds for hyper-minimisation of DFAs in general: Given a DFA M and numbers s and m, it is NP-hard to decide whether there exists a DFA N with at most s states such that |L(M) ΔL(N) ≤ m.
7 schema:editor N52e19564793449388400d711fe2a0142
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nc0f7bf16f0e84cb095355c1d47b1e75e
12 schema:keywords DFA
13 Minimising Automata
14 NP
15 algorithm
16 automata
17 best algorithm
18 calculations
19 comparison
20 computation
21 error
22 finite languages
23 function
24 language
25 least number
26 length
27 minimal DFA
28 minimisation
29 new algorithm
30 number
31 number S
32 number k
33 number of states
34 parallel
35 partial transition functions
36 previous algorithms
37 problem
38 results
39 similar results
40 smallest DFA
41 state
42 time
43 total DFAs
44 transition function
45 words
46 words of length
47 schema:name On Minimising Automata with Errors
48 schema:pagination 327-338
49 schema:productId N4eab360ea7ae4160835b738ec061c45d
50 Nde37be7ce7dc4df8bb24a3d229e0da5d
51 schema:publisher Nb04a1c52c61e4618a121bf713b404fb6
52 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018296198
53 https://doi.org/10.1007/978-3-642-22993-0_31
54 schema:sdDatePublished 2022-01-01T19:11
56 schema:sdPublisher N1e05c343cbb247908abe5a1126b711d9
57 schema:url https://doi.org/10.1007/978-3-642-22993-0_31
59 sgo:sdDataset chapters
60 rdf:type schema:Chapter
61 N1e05c343cbb247908abe5a1126b711d9 schema:name Springer Nature - SN SciGraph project
62 rdf:type schema:Organization
63 N2caa98d0a0a44394a27cb7130e44b943 rdf:first sg:person.015252371751.76
64 rdf:rest N822f78c597ed44bbb1a57e283c89b89d
65 N4eab360ea7ae4160835b738ec061c45d schema:name dimensions_id
66 schema:value pub.1018296198
67 rdf:type schema:PropertyValue
68 N52e19564793449388400d711fe2a0142 rdf:first Na6ae861c28bb4f14b77d39284cf56dfb
69 rdf:rest Ndebe0994e4bb485c8319608f884719eb
70 N822f78c597ed44bbb1a57e283c89b89d rdf:first sg:person.016645332751.01
71 rdf:rest rdf:nil
72 N99b436ca4145464d832bc5f08d5d45c1 rdf:first sg:person.013657430751.28
73 rdf:rest N2caa98d0a0a44394a27cb7130e44b943
74 Na6ae861c28bb4f14b77d39284cf56dfb schema:familyName Murlak
75 schema:givenName Filip
76 rdf:type schema:Person
77 Nb04a1c52c61e4618a121bf713b404fb6 schema:name Springer Nature
78 rdf:type schema:Organisation
79 Nc0f7bf16f0e84cb095355c1d47b1e75e schema:isbn 978-3-642-22992-3
80 978-3-642-22993-0
81 schema:name Mathematical Foundations of Computer Science 2011
82 rdf:type schema:Book
83 Nde37be7ce7dc4df8bb24a3d229e0da5d schema:name doi
84 schema:value 10.1007/978-3-642-22993-0_31
85 rdf:type schema:PropertyValue
87 rdf:rest rdf:nil
89 schema:givenName Piotr
90 rdf:type schema:Person
91 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
92 schema:name Information and Computing Sciences
93 rdf:type schema:DefinedTerm
94 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
95 schema:name Computation Theory and Mathematics
96 rdf:type schema:DefinedTerm
97 sg:person.013657430751.28 schema:affiliation grid-institutes:grid.8505.8
98 schema:familyName Gawrychowski
99 schema:givenName Paweł
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013657430751.28
101 rdf:type schema:Person
102 sg:person.015252371751.76 schema:affiliation grid-institutes:grid.8505.8
103 schema:familyName Jeż
104 schema:givenName Artur
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76
106 rdf:type schema:Person
107 sg:person.016645332751.01 schema:affiliation grid-institutes:grid.5719.a
108 schema:familyName Maletti
109 schema:givenName Andreas
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016645332751.01
111 rdf:type schema:Person
112 grid-institutes:grid.5719.a schema:alternateName Institute for Natural Language Processing, Universität Stuttgart, Azenbergstraße 12, 70174, Stuttgart, Germany
113 schema:name Institute for Natural Language Processing, Universität Stuttgart, Azenbergstraße 12, 70174, Stuttgart, Germany
114 rdf:type schema:Organization
115 grid-institutes:grid.8505.8 schema:alternateName Institute of Computer Science, University of Wrocław, ul. Joliot-Curie 15, 50-383, Wrocław, Poland
116 schema:name Institute of Computer Science, University of Wrocław, ul. Joliot-Curie 15, 50-383, Wrocław, Poland
117 rdf:type schema:Organization