On Minimising Automata with Errors View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2011

AUTHORS

Paweł Gawrychowski , Artur Jeż , Andreas Maletti

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

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: 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/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", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "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"
  }
]
 

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

Turtle is a human-readable linked data format.

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
1 sg:pub.10.1007/978-3-642-22993-0_31 schema:about anzsrc-for:08
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
55 schema:sdLicense https://scigraph.springernature.com/explorer/license/
56 schema:sdPublisher N1e05c343cbb247908abe5a1126b711d9
57 schema:url https://doi.org/10.1007/978-3-642-22993-0_31
58 sgo:license sg:explorer/license/
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
86 Ndebe0994e4bb485c8319608f884719eb rdf:first Ne405b998c9c446b6b6bb0d9dd8dad81e
87 rdf:rest rdf:nil
88 Ne405b998c9c446b6b6bb0d9dd8dad81e schema:familyName Sankowski
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
 




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


...