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": "2021-11-01T18:48", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_152.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 N2a96d3f978a545c88982467e5ef54d73
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 N107955765b584f18ac531c93fdf4671c
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nbc4a6113ce2f41beb025302838c69ea3
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 N043d3cbbd86c46cc900e3cc839c2ea0d
50 N64bc3ca8b6ed4531941ae6aebf9e6172
51 schema:publisher N1121b77658c94c5b9f108950c20581b1
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 2021-11-01T18:48
55 schema:sdLicense https://scigraph.springernature.com/explorer/license/
56 schema:sdPublisher Ne9a9936e7a7d43d1b924f0f3052f0bd6
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 N043d3cbbd86c46cc900e3cc839c2ea0d schema:name dimensions_id
62 schema:value pub.1018296198
63 rdf:type schema:PropertyValue
64 N107955765b584f18ac531c93fdf4671c rdf:first N3210efc9bf62404484ad965667ab6a2f
65 rdf:rest N2fcef4a7935545589f6e4086ad15644c
66 N1121b77658c94c5b9f108950c20581b1 schema:name Springer Nature
67 rdf:type schema:Organisation
68 N1252e1b546e34192a5c81b5fd52df7eb rdf:first sg:person.016645332751.01
69 rdf:rest rdf:nil
70 N2a96d3f978a545c88982467e5ef54d73 rdf:first sg:person.013657430751.28
71 rdf:rest N33b0677b131c47d3ac6d42f078013d64
72 N2fcef4a7935545589f6e4086ad15644c rdf:first N926719b730984f2f8fdaed0e5934f3c7
73 rdf:rest rdf:nil
74 N3210efc9bf62404484ad965667ab6a2f schema:familyName Murlak
75 schema:givenName Filip
76 rdf:type schema:Person
77 N33b0677b131c47d3ac6d42f078013d64 rdf:first sg:person.015252371751.76
78 rdf:rest N1252e1b546e34192a5c81b5fd52df7eb
79 N64bc3ca8b6ed4531941ae6aebf9e6172 schema:name doi
80 schema:value 10.1007/978-3-642-22993-0_31
81 rdf:type schema:PropertyValue
82 N926719b730984f2f8fdaed0e5934f3c7 schema:familyName Sankowski
83 schema:givenName Piotr
84 rdf:type schema:Person
85 Nbc4a6113ce2f41beb025302838c69ea3 schema:isbn 978-3-642-22992-3
86 978-3-642-22993-0
87 schema:name Mathematical Foundations of Computer Science 2011
88 rdf:type schema:Book
89 Ne9a9936e7a7d43d1b924f0f3052f0bd6 schema:name Springer Nature - SN SciGraph project
90 rdf:type schema:Organization
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)


...