Hyper-minimization for Deterministic Tree Automata View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2012

AUTHORS

Artur Jeż , Andreas Maletti

ABSTRACT

Hyper-minimization aims to reduce the size of the representation of a language beyond the limits imposed by classical minimization. To this end, the hyper-minimal representation can represent a language that has a finite difference to the original language. The first hyper-minimization algorithm is presented for (bottom-up) deterministic tree automata, which represent the recognizable tree languages. It 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}${\cal O}(\ell m n)$\end{document}, where ℓ is the maximal rank of the input symbols, m is the number of transitions, and n is the number of states of the input tree automaton. More... »

PAGES

217-228

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-31606-7_19

DOI

http://dx.doi.org/10.1007/978-3-642-31606-7_19

DIMENSIONS

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


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, 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, Pfaffenwaldring\u00a05b, 70569, Stuttgart, Germany", 
          "id": "http://www.grid.ac/institutes/grid.5719.a", 
          "name": [
            "Institute for Natural Language Processing, Universit\u00e4t Stuttgart, Pfaffenwaldring\u00a05b, 70569, 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": "2012", 
    "datePublishedReg": "2012-01-01", 
    "description": "Hyper-minimization aims to reduce the size of the representation of a language beyond the limits imposed by classical minimization. To this end, the hyper-minimal representation can represent a language that has a finite difference to the original language. The first hyper-minimization algorithm is presented for (bottom-up) deterministic tree automata, which represent the recognizable tree languages. It 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}${\\cal O}(\\ell m n)$\\end{document}, where \u2113\u00a0is the maximal rank of the input symbols, m\u00a0is the number of transitions, and n\u00a0is the number of states of the input tree automaton.", 
    "editor": [
      {
        "familyName": "Moreira", 
        "givenName": "Nelma", 
        "type": "Person"
      }, 
      {
        "familyName": "Reis", 
        "givenName": "Rog\u00e9rio", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-31606-7_19", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-31605-0", 
        "978-3-642-31606-7"
      ], 
      "name": "Implementation and Application of Automata", 
      "type": "Book"
    }, 
    "keywords": [
      "deterministic tree automata", 
      "recognizable tree languages", 
      "original language", 
      "tree automata", 
      "tree languages", 
      "language", 
      "classical minimization", 
      "representation", 
      "symbols", 
      "automata", 
      "input symbols", 
      "number of states", 
      "end", 
      "number of transitions", 
      "rank", 
      "differences", 
      "state", 
      "time", 
      "number", 
      "maximal rank", 
      "limit", 
      "transition", 
      "algorithm", 
      "size", 
      "minimization", 
      "finite differences", 
      "hyper-minimal representation", 
      "first hyper-minimization algorithm", 
      "hyper-minimization algorithm", 
      "input tree automaton"
    ], 
    "name": "Hyper-minimization for Deterministic Tree Automata", 
    "pagination": "217-228", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1039386393"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-31606-7_19"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-31606-7_19", 
      "https://app.dimensions.ai/details/publication/pub.1039386393"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:59", 
    "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_411.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-31606-7_19"
  }
]
 

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

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

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-31606-7_19'

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


 

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

105 TRIPLES      23 PREDICATES      56 URIs      49 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-31606-7_19 schema:about anzsrc-for:20
2 anzsrc-for:2004
3 schema:author Na94aa6c013864c30b3ad62defe6bf6ea
4 schema:datePublished 2012
5 schema:datePublishedReg 2012-01-01
6 schema:description Hyper-minimization aims to reduce the size of the representation of a language beyond the limits imposed by classical minimization. To this end, the hyper-minimal representation can represent a language that has a finite difference to the original language. The first hyper-minimization algorithm is presented for (bottom-up) deterministic tree automata, which represent the recognizable tree languages. It 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}${\cal O}(\ell m n)$\end{document}, where ℓ is the maximal rank of the input symbols, m is the number of transitions, and n is the number of states of the input tree automaton.
7 schema:editor Nccd7aedb84e04ed5ba8223ba2b4086c0
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N20101185b7314fb6beb4bd2d822cbc80
12 schema:keywords algorithm
13 automata
14 classical minimization
15 deterministic tree automata
16 differences
17 end
18 finite differences
19 first hyper-minimization algorithm
20 hyper-minimal representation
21 hyper-minimization algorithm
22 input symbols
23 input tree automaton
24 language
25 limit
26 maximal rank
27 minimization
28 number
29 number of states
30 number of transitions
31 original language
32 rank
33 recognizable tree languages
34 representation
35 size
36 state
37 symbols
38 time
39 transition
40 tree automata
41 tree languages
42 schema:name Hyper-minimization for Deterministic Tree Automata
43 schema:pagination 217-228
44 schema:productId N0a3785f7e5194f7d9a76850bb6f4d9e9
45 N286078f0a73d497da788de7d712ff763
46 schema:publisher Na18168a53af645e0abcb9cdfb2bec67d
47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039386393
48 https://doi.org/10.1007/978-3-642-31606-7_19
49 schema:sdDatePublished 2021-11-01T18:59
50 schema:sdLicense https://scigraph.springernature.com/explorer/license/
51 schema:sdPublisher N7b3afd692fcd45bfae17e89b8ef82fd4
52 schema:url https://doi.org/10.1007/978-3-642-31606-7_19
53 sgo:license sg:explorer/license/
54 sgo:sdDataset chapters
55 rdf:type schema:Chapter
56 N0a3785f7e5194f7d9a76850bb6f4d9e9 schema:name dimensions_id
57 schema:value pub.1039386393
58 rdf:type schema:PropertyValue
59 N20101185b7314fb6beb4bd2d822cbc80 schema:isbn 978-3-642-31605-0
60 978-3-642-31606-7
61 schema:name Implementation and Application of Automata
62 rdf:type schema:Book
63 N286078f0a73d497da788de7d712ff763 schema:name doi
64 schema:value 10.1007/978-3-642-31606-7_19
65 rdf:type schema:PropertyValue
66 N553fcee323584c1bb3972e7f89025920 schema:familyName Moreira
67 schema:givenName Nelma
68 rdf:type schema:Person
69 N75611350cadc40879c88b46e62ae93b7 schema:familyName Reis
70 schema:givenName Rogério
71 rdf:type schema:Person
72 N7b3afd692fcd45bfae17e89b8ef82fd4 schema:name Springer Nature - SN SciGraph project
73 rdf:type schema:Organization
74 Na18168a53af645e0abcb9cdfb2bec67d schema:name Springer Nature
75 rdf:type schema:Organisation
76 Na94aa6c013864c30b3ad62defe6bf6ea rdf:first sg:person.015252371751.76
77 rdf:rest Nef9be2eaeb0d44bd9fc823474caa387a
78 Nccd7aedb84e04ed5ba8223ba2b4086c0 rdf:first N553fcee323584c1bb3972e7f89025920
79 rdf:rest Nd5911866a0e643a3a08c0d53b8c02224
80 Nd5911866a0e643a3a08c0d53b8c02224 rdf:first N75611350cadc40879c88b46e62ae93b7
81 rdf:rest rdf:nil
82 Nef9be2eaeb0d44bd9fc823474caa387a rdf:first sg:person.016645332751.01
83 rdf:rest rdf:nil
84 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
85 schema:name Language, Communication and Culture
86 rdf:type schema:DefinedTerm
87 anzsrc-for:2004 schema:inDefinedTermSet anzsrc-for:
88 schema:name Linguistics
89 rdf:type schema:DefinedTerm
90 sg:person.015252371751.76 schema:affiliation grid-institutes:grid.8505.8
91 schema:familyName Jeż
92 schema:givenName Artur
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76
94 rdf:type schema:Person
95 sg:person.016645332751.01 schema:affiliation grid-institutes:grid.5719.a
96 schema:familyName Maletti
97 schema:givenName Andreas
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016645332751.01
99 rdf:type schema:Person
100 grid-institutes:grid.5719.a schema:alternateName Institute for Natural Language Processing, Universität Stuttgart, Pfaffenwaldring 5b, 70569, Stuttgart, Germany
101 schema:name Institute for Natural Language Processing, Universität Stuttgart, Pfaffenwaldring 5b, 70569, Stuttgart, Germany
102 rdf:type schema:Organization
103 grid-institutes:grid.8505.8 schema:alternateName Institute of Computer Science, University of Wrocław, ul. Joliot-Curie 15, 50-383, Wrocław, Poland
104 schema:name Institute of Computer Science, University of Wrocław, ul. Joliot-Curie 15, 50-383, Wrocław, Poland
105 rdf:type schema:Organization
 




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


...