Better Hyper-minimization View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2011

AUTHORS

Andreas Maletti

ABSTRACT

Hyper-minimization aims to compute a minimal deterministic finite automaton (dfa) that recognizes the same language as a given dfa up to a finite number of errors. Algorithms for hyper-minimization that run in time O(n logn), where n is the number of states of the given dfa, have been reported recently in [Gawrychowski and Jeż: Hyper-minimisation made efficient. Proc. Mfcs, Lncs 5734, 2009] and [Holzer and Maletti: An n logn algorithm for hyper-minimizing a (minimized) deterministic automaton. Theor. Comput. Sci. 411, 2010]. These algorithms are improved to return a hyper-minimal dfa that commits the least number of errors. This closes another open problem of [Badr, Geffert, and Shipman: Hyper-minimizing minimized deterministic finite state automata. RairoTheor. Inf. Appl. 43, 2009]. Unfortunately, the time complexity for the obtained algorithm increases to O(n2). More... »

PAGES

201-210

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-18098-9_22

DOI

http://dx.doi.org/10.1007/978-3-642-18098-9_22

DIMENSIONS

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


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": "Departament de Filologies Rom\u00e0niques, Universitat Rovira i Virgili, Avinguda de Catalunya\u00a035, 43002, Tarragona, Spain", 
          "id": "http://www.grid.ac/institutes/grid.410367.7", 
          "name": [
            "Departament de Filologies Rom\u00e0niques, Universitat Rovira i Virgili, Avinguda de Catalunya\u00a035, 43002, Tarragona, Spain"
          ], 
          "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": "Hyper-minimization aims to compute a minimal deterministic finite automaton\u00a0(dfa) that recognizes the same language as a given dfa up to a finite number of errors. Algorithms for hyper-minimization that run in time\u00a0O(n logn), where n\u00a0is the number of states of the given dfa, have been reported recently in [Gawrychowski and Je\u017c: Hyper-minimisation made efficient. Proc. Mfcs, Lncs\u00a05734, 2009] and [Holzer and Maletti: An n logn algorithm for hyper-minimizing a (minimized) deterministic automaton. Theor. Comput. Sci.\u00a0411, 2010]. These algorithms are improved to return a hyper-minimal dfa that commits the least number of errors. This closes another open problem of [Badr, Geffert, and Shipman: Hyper-minimizing minimized deterministic finite state automata. RairoTheor. Inf. Appl.\u00a043, 2009]. Unfortunately, the time complexity for the obtained algorithm increases to\u00a0O(n2).", 
    "editor": [
      {
        "familyName": "Domaratzki", 
        "givenName": "Michael", 
        "type": "Person"
      }, 
      {
        "familyName": "Salomaa", 
        "givenName": "Kai", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-18098-9_22", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-18097-2", 
        "978-3-642-18098-9"
      ], 
      "name": "Implementation and Application of Automata", 
      "type": "Book"
    }, 
    "keywords": [
      "finite number", 
      "open problem", 
      "number of states", 
      "algorithm increases", 
      "minimal deterministic finite automaton", 
      "finite automata", 
      "time complexity", 
      "deterministic finite automata", 
      "algorithm", 
      "least number", 
      "error", 
      "automata", 
      "problem", 
      "number", 
      "complexity", 
      "same language", 
      "language", 
      "DFA", 
      "time", 
      "state", 
      "increase", 
      "hyper-minimal dfa"
    ], 
    "name": "Better Hyper-minimization", 
    "pagination": "201-210", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1040456474"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-18098-9_22"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-18098-9_22", 
      "https://app.dimensions.ai/details/publication/pub.1040456474"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:04", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_313.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-18098-9_22"
  }
]
 

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-18098-9_22'

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-18098-9_22'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-18098-9_22'

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-18098-9_22'


 

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

87 TRIPLES      23 PREDICATES      48 URIs      41 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-18098-9_22 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N64094609d7d64b1e8628ceddea259473
4 schema:datePublished 2011
5 schema:datePublishedReg 2011-01-01
6 schema:description Hyper-minimization aims to compute a minimal deterministic finite automaton (dfa) that recognizes the same language as a given dfa up to a finite number of errors. Algorithms for hyper-minimization that run in time O(n logn), where n is the number of states of the given dfa, have been reported recently in [Gawrychowski and Jeż: Hyper-minimisation made efficient. Proc. Mfcs, Lncs 5734, 2009] and [Holzer and Maletti: An n logn algorithm for hyper-minimizing a (minimized) deterministic automaton. Theor. Comput. Sci. 411, 2010]. These algorithms are improved to return a hyper-minimal dfa that commits the least number of errors. This closes another open problem of [Badr, Geffert, and Shipman: Hyper-minimizing minimized deterministic finite state automata. RairoTheor. Inf. Appl. 43, 2009]. Unfortunately, the time complexity for the obtained algorithm increases to O(n2).
7 schema:editor N2e33957a699249ecaf710184cfe1898f
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N55b1fcda6f8e4c1aa566c2182c8b101e
12 schema:keywords DFA
13 algorithm
14 algorithm increases
15 automata
16 complexity
17 deterministic finite automata
18 error
19 finite automata
20 finite number
21 hyper-minimal dfa
22 increase
23 language
24 least number
25 minimal deterministic finite automaton
26 number
27 number of states
28 open problem
29 problem
30 same language
31 state
32 time
33 time complexity
34 schema:name Better Hyper-minimization
35 schema:pagination 201-210
36 schema:productId N2de71437ec1d41e78af4a4d2d1ed5bba
37 N693a8be558324a088efc681afe31472f
38 schema:publisher N3e4b2b369c104b1cb31e48658210345a
39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040456474
40 https://doi.org/10.1007/978-3-642-18098-9_22
41 schema:sdDatePublished 2021-12-01T20:04
42 schema:sdLicense https://scigraph.springernature.com/explorer/license/
43 schema:sdPublisher Nae0f74633adc417f80891bce8ba7aa91
44 schema:url https://doi.org/10.1007/978-3-642-18098-9_22
45 sgo:license sg:explorer/license/
46 sgo:sdDataset chapters
47 rdf:type schema:Chapter
48 N2de71437ec1d41e78af4a4d2d1ed5bba schema:name doi
49 schema:value 10.1007/978-3-642-18098-9_22
50 rdf:type schema:PropertyValue
51 N2e33957a699249ecaf710184cfe1898f rdf:first Nb1110699d0524aa3a5b63acafbe44712
52 rdf:rest N81dfb38b94e44b6a94f7fbcded6344fa
53 N3e4b2b369c104b1cb31e48658210345a schema:name Springer Nature
54 rdf:type schema:Organisation
55 N55b1fcda6f8e4c1aa566c2182c8b101e schema:isbn 978-3-642-18097-2
56 978-3-642-18098-9
57 schema:name Implementation and Application of Automata
58 rdf:type schema:Book
59 N64094609d7d64b1e8628ceddea259473 rdf:first sg:person.016645332751.01
60 rdf:rest rdf:nil
61 N693a8be558324a088efc681afe31472f schema:name dimensions_id
62 schema:value pub.1040456474
63 rdf:type schema:PropertyValue
64 N81dfb38b94e44b6a94f7fbcded6344fa rdf:first Nc3c613def3574dd585422f2df1f0ef1a
65 rdf:rest rdf:nil
66 Nae0f74633adc417f80891bce8ba7aa91 schema:name Springer Nature - SN SciGraph project
67 rdf:type schema:Organization
68 Nb1110699d0524aa3a5b63acafbe44712 schema:familyName Domaratzki
69 schema:givenName Michael
70 rdf:type schema:Person
71 Nc3c613def3574dd585422f2df1f0ef1a schema:familyName Salomaa
72 schema:givenName Kai
73 rdf:type schema:Person
74 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
75 schema:name Information and Computing Sciences
76 rdf:type schema:DefinedTerm
77 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
78 schema:name Computation Theory and Mathematics
79 rdf:type schema:DefinedTerm
80 sg:person.016645332751.01 schema:affiliation grid-institutes:grid.410367.7
81 schema:familyName Maletti
82 schema:givenName Andreas
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016645332751.01
84 rdf:type schema:Person
85 grid-institutes:grid.410367.7 schema:alternateName Departament de Filologies Romàniques, Universitat Rovira i Virgili, Avinguda de Catalunya 35, 43002, Tarragona, Spain
86 schema:name Departament de Filologies Romàniques, Universitat Rovira i Virgili, Avinguda de Catalunya 35, 43002, Tarragona, Spain
87 rdf:type schema:Organization
 




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


...