Hyper-minimisation Made Efficient View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2009

AUTHORS

Paweł Gawrychowski , Artur Jeż

ABSTRACT

We consider a problem of hyper-minimisation of an automaton [2,3]: given a DFA M we want to compute a smallest automaton N such that the language L(M) ΔL(N) is finite, where Δ denotes the symmetric difference. We improve the previously known \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal O (|\Sigma|n^2)$\end{document} solution by giving an expected \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal O (|\delta|\log n)$\end{document} time algorithm for this problem, where |δ| is the size of the (potentially partial) transition function. We also give a slightly slower deterministic \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal O(|\delta|\log^2 n)$\end{document} version of the algorithm.Then we introduce a similar problem of k-minimisation: for an automaton M and number k we want to find a smallest automaton N such that L(M) ΔL(N) ⊆ Σ< k, i.e. the languages they recognize differ only on words of length less than k. We characterise such minimal automata and give algorithm with a similar complexity for this problem. More... »

PAGES

356-368

Book

TITLE

Mathematical Foundations of Computer Science 2009

ISBN

978-3-642-03815-0
978-3-642-03816-7

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-03816-7_31

DOI

http://dx.doi.org/10.1007/978-3-642-03816-7_31

DIMENSIONS

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


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/20", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Language, Communication and Culture", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/2004", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Linguistics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Institute of Computer Science, University of Wroc\u0142aw, Poland", 
          "id": "http://www.grid.ac/institutes/grid.8505.8", 
          "name": [
            "Institute of Computer Science, University of 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, Poland", 
          "id": "http://www.grid.ac/institutes/grid.8505.8", 
          "name": [
            "Institute of Computer Science, University of 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"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "We consider a problem of hyper-minimisation of an automaton [2,3]: given a DFA M we want to compute a smallest automaton N such that the language L(M) \u0394L(N) is finite, where \u0394 denotes the symmetric difference. We improve the previously known \\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 (|\\Sigma|n^2)$\\end{document} solution by giving an expected \\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 (|\\delta|\\log n)$\\end{document} time algorithm for this problem, where |\u03b4| is the size of the (potentially partial) transition function. We also give a slightly slower deterministic \\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(|\\delta|\\log^2 n)$\\end{document} version of the algorithm.Then we introduce a similar problem of k-minimisation: for an automaton M and number k we want to find a smallest automaton N such that L(M) \u0394L(N)\u2009\u2286\u2009\u03a3<\u2009k, i.e. the languages they recognize differ only on words of length less than k. We characterise such minimal automata and give algorithm with a similar complexity for this problem.", 
    "editor": [
      {
        "familyName": "Kr\u00e1lovi\u010d", 
        "givenName": "Rastislav", 
        "type": "Person"
      }, 
      {
        "familyName": "Niwi\u0144ski", 
        "givenName": "Damian", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-03816-7_31", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-03815-0", 
        "978-3-642-03816-7"
      ], 
      "name": "Mathematical Foundations of Computer Science 2009", 
      "type": "Book"
    }, 
    "keywords": [
      "DFA M", 
      "minimal automaton", 
      "language", 
      "words", 
      "automaton M", 
      "words of length", 
      "automata", 
      "symmetric difference", 
      "version", 
      "similar problems", 
      "similar complexity", 
      "complexity", 
      "problem", 
      "differences", 
      "transition function", 
      "function", 
      "solution", 
      "algorithm", 
      "length", 
      "time algorithm", 
      "size", 
      "minimisation", 
      "number k"
    ], 
    "name": "Hyper-minimisation Made Efficient", 
    "pagination": "356-368", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1017648139"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-03816-7_31"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-03816-7_31", 
      "https://app.dimensions.ai/details/publication/pub.1017648139"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:42", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_168.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-03816-7_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-03816-7_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-03816-7_31'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-03816-7_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-03816-7_31'


 

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

95 TRIPLES      23 PREDICATES      49 URIs      42 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-03816-7_31 schema:about anzsrc-for:20
2 anzsrc-for:2004
3 schema:author Nd8093515e7344213855c01bfb87da8d7
4 schema:datePublished 2009
5 schema:datePublishedReg 2009-01-01
6 schema:description We consider a problem of hyper-minimisation of an automaton [2,3]: given a DFA M we want to compute a smallest automaton N such that the language L(M) ΔL(N) is finite, where Δ denotes the symmetric difference. We improve the previously known \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal O (|\Sigma|n^2)$\end{document} solution by giving an expected \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal O (|\delta|\log n)$\end{document} time algorithm for this problem, where |δ| is the size of the (potentially partial) transition function. We also give a slightly slower deterministic \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal O(|\delta|\log^2 n)$\end{document} version of the algorithm.Then we introduce a similar problem of k-minimisation: for an automaton M and number k we want to find a smallest automaton N such that L(M) ΔL(N) ⊆ Σ< k, i.e. the languages they recognize differ only on words of length less than k. We characterise such minimal automata and give algorithm with a similar complexity for this problem.
7 schema:editor N2aed6e0ecf5b461ab006d2516de354bc
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N19d73d71b7ff4f49a964587768cb5bf6
12 schema:keywords DFA M
13 algorithm
14 automata
15 automaton M
16 complexity
17 differences
18 function
19 language
20 length
21 minimal automaton
22 minimisation
23 number k
24 problem
25 similar complexity
26 similar problems
27 size
28 solution
29 symmetric difference
30 time algorithm
31 transition function
32 version
33 words
34 words of length
35 schema:name Hyper-minimisation Made Efficient
36 schema:pagination 356-368
37 schema:productId N0a2b79a4f2da4ca49dd06837907689cc
38 N186f9aa9fc704dfea6a30f09901763fd
39 schema:publisher N375cff4234244600b09b2cf3a86d3153
40 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017648139
41 https://doi.org/10.1007/978-3-642-03816-7_31
42 schema:sdDatePublished 2022-05-20T07:42
43 schema:sdLicense https://scigraph.springernature.com/explorer/license/
44 schema:sdPublisher Nff037831d2b04bb3b79c002488b6e5ff
45 schema:url https://doi.org/10.1007/978-3-642-03816-7_31
46 sgo:license sg:explorer/license/
47 sgo:sdDataset chapters
48 rdf:type schema:Chapter
49 N0a2b79a4f2da4ca49dd06837907689cc schema:name doi
50 schema:value 10.1007/978-3-642-03816-7_31
51 rdf:type schema:PropertyValue
52 N186f9aa9fc704dfea6a30f09901763fd schema:name dimensions_id
53 schema:value pub.1017648139
54 rdf:type schema:PropertyValue
55 N19d73d71b7ff4f49a964587768cb5bf6 schema:isbn 978-3-642-03815-0
56 978-3-642-03816-7
57 schema:name Mathematical Foundations of Computer Science 2009
58 rdf:type schema:Book
59 N2aed6e0ecf5b461ab006d2516de354bc rdf:first N8b76de944af148f2a1f3c89668e7fe90
60 rdf:rest Na8bc0f84a58b4db68e07ea3ebcdcda3f
61 N375cff4234244600b09b2cf3a86d3153 schema:name Springer Nature
62 rdf:type schema:Organisation
63 N63e687aedbce44d792b58a78c401a75c schema:familyName Niwiński
64 schema:givenName Damian
65 rdf:type schema:Person
66 N8b76de944af148f2a1f3c89668e7fe90 schema:familyName Královič
67 schema:givenName Rastislav
68 rdf:type schema:Person
69 Na8bc0f84a58b4db68e07ea3ebcdcda3f rdf:first N63e687aedbce44d792b58a78c401a75c
70 rdf:rest rdf:nil
71 Nd8093515e7344213855c01bfb87da8d7 rdf:first sg:person.013657430751.28
72 rdf:rest Ne536f80cde994bab8f4bc345b6a9bd98
73 Ne536f80cde994bab8f4bc345b6a9bd98 rdf:first sg:person.015252371751.76
74 rdf:rest rdf:nil
75 Nff037831d2b04bb3b79c002488b6e5ff schema:name Springer Nature - SN SciGraph project
76 rdf:type schema:Organization
77 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
78 schema:name Language, Communication and Culture
79 rdf:type schema:DefinedTerm
80 anzsrc-for:2004 schema:inDefinedTermSet anzsrc-for:
81 schema:name Linguistics
82 rdf:type schema:DefinedTerm
83 sg:person.013657430751.28 schema:affiliation grid-institutes:grid.8505.8
84 schema:familyName Gawrychowski
85 schema:givenName Paweł
86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013657430751.28
87 rdf:type schema:Person
88 sg:person.015252371751.76 schema:affiliation grid-institutes:grid.8505.8
89 schema:familyName Jeż
90 schema:givenName Artur
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76
92 rdf:type schema:Person
93 grid-institutes:grid.8505.8 schema:alternateName Institute of Computer Science, University of Wrocław, Poland
94 schema:name Institute of Computer Science, University of Wrocław, Poland
95 rdf:type schema:Organization
 




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


...