# Hyper-optimization for Deterministic Tree Automata

Ontology type: schema:Chapter

### Chapter Info

DATE

2013

AUTHORS ABSTRACT

A recent minimization technique, called hyper-minimization, permits reductions of language representations beyond the limits imposed by classical semantics-preserving minimization. Naturally, the semantics is not preserved by hyper-minimization; rather the reduced representation, which is called hyper-minimal, can accept a language that has a finite symmetric difference to the language of the original representation. It was demonstrated that hyper-minimization for (bottom-up) deterministic tree automata (dtas), which represent the recognizable tree languages, can be achieved 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}(m \cdot{\log n})$\end{document}, where m is the size of the dta and n is the number of its states. In this contribution, this result is complemented by two results on the quantity of the errors. It is shown that optimal hyper-minimization for dtas (i.e., computing a hyper-minimal dta that commits the least number of errors of all hyper-minimal dtas) can be achieved 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}(m \cdot n)$\end{document}. In the same time bound also the number of errors of any hyper-minimal dta can be computed. More... »

PAGES

244-255

### Book

TITLE

Implementation and Application of Automata

ISBN

978-3-642-39273-3
978-3-642-39274-0

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-39274-0_22

DOI

http://dx.doi.org/10.1007/978-3-642-39274-0_22

DIMENSIONS

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

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:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"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 for Natural Language Processing, Universit\u00e4t Stuttgart, Pfaffenwaldring 5b, 70569, Stuttgart, Germany",
"id": "http://www.grid.ac/institutes/grid.5719.a",
"name": [
"Institute for Natural Language Processing, Universit\u00e4t Stuttgart, Pfaffenwaldring 5b, 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": "2013",
"datePublishedReg": "2013-01-01",
"description": "A recent minimization technique, called hyper-minimization, permits reductions of language representations beyond the limits imposed by classical semantics-preserving minimization. Naturally, the semantics is not preserved by hyper-minimization; rather the reduced representation, which is called hyper-minimal, can accept a language that has a finite symmetric difference to the language of the original representation. It was demonstrated that hyper-minimization for (bottom-up) deterministic tree automata\u00a0(dtas), which represent the recognizable tree languages, can be achieved in time \\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}(m \\cdot{\\log n})$\\end{document}, where m\u00a0is the size of the dta and n\u00a0is the number of its states. In this contribution, this result is complemented by two results on the quantity of the errors. It is shown that optimal hyper-minimization for dtas (i.e., computing a hyper-minimal dta that commits the least number of errors of all hyper-minimal dtas) can be achieved 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}(m \\cdot n)$\\end{document}. In the same time bound also the number of errors of any hyper-minimal dta can be computed.",
"editor": [
{
"familyName": "Konstantinidis",
"givenName": "Stavros",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-642-39274-0_22",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-642-39273-3",
"978-3-642-39274-0"
],
"name": "Implementation and Application of Automata",
"type": "Book"
},
"keywords": [
"deterministic tree automata",
"recognizable tree languages",
"language representation",
"tree languages",
"tree automata",
"language",
"representation",
"original representation",
"same time",
"semantics",
"number of errors",
"automata",
"symmetric difference",
"contribution",
"time",
"differences",
"state",
"number",
"error",
"limit",
"results",
"quantity",
"technique",
"size",
"minimization",
"reduction",
"DTA",
"minimization technique",
"recent minimization technique",
"classical semantics-preserving minimization",
"semantics-preserving minimization",
"finite symmetric difference",
"hyper-minimal dta"
],
"name": "Hyper-optimization for Deterministic Tree Automata",
"pagination": "244-255",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1041235264"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-642-39274-0_22"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-642-39274-0_22",
"https://app.dimensions.ai/details/publication/pub.1041235264"
],
"sdDataset": "chapters",
"sdDatePublished": "2021-11-01T18:49",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_176.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-642-39274-0_22"
}
]

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-39274-0_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-39274-0_22'

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

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

93 TRIPLES      23 PREDICATES      59 URIs      52 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:2004
3 schema:author Nca7bdb31dd6a4fb88091edde47dd22ce
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description A recent minimization technique, called hyper-minimization, permits reductions of language representations beyond the limits imposed by classical semantics-preserving minimization. Naturally, the semantics is not preserved by hyper-minimization; rather the reduced representation, which is called hyper-minimal, can accept a language that has a finite symmetric difference to the language of the original representation. It was demonstrated that hyper-minimization for (bottom-up) deterministic tree automata (dtas), which represent the recognizable tree languages, can be achieved 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}(m \cdot{\log n})$\end{document}, where m is the size of the dta and n is the number of its states. In this contribution, this result is complemented by two results on the quantity of the errors. It is shown that optimal hyper-minimization for dtas (i.e., computing a hyper-minimal dta that commits the least number of errors of all hyper-minimal dtas) can be achieved 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}(m \cdot n)$\end{document}. In the same time bound also the number of errors of any hyper-minimal dta can be computed.
7 schema:editor Nf152e28149d346c3acded680a5c9c343
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N8aec291cc0f143a0aa0b90a5e8b70e90
12 schema:keywords DTA
13 automata
14 classical semantics-preserving minimization
15 contribution
16 deterministic tree automata
17 differences
18 error
19 finite symmetric difference
20 hyper-minimal dta
21 language
22 language representation
23 limit
24 minimization
25 minimization technique
26 number
27 number of errors
28 original representation
29 quantity
30 recent minimization technique
31 recognizable tree languages
32 reduction
33 representation
34 results
35 same time
36 semantics
37 semantics-preserving minimization
38 size
39 state
40 symmetric difference
41 technique
42 time
43 tree automata
44 tree languages
45 schema:name Hyper-optimization for Deterministic Tree Automata
46 schema:pagination 244-255
47 schema:productId Ne0e707c606bf45bab5e79f53297831eb
48 Nf3df755b0cbb46168470f0d623b3c3c1
49 schema:publisher N8c13a73a9b59465da6e12191c57b09aa
50 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041235264
51 https://doi.org/10.1007/978-3-642-39274-0_22
52 schema:sdDatePublished 2021-11-01T18:49
54 schema:sdPublisher N8dd6ec86066446268aefd6a5ff0edc40
55 schema:url https://doi.org/10.1007/978-3-642-39274-0_22
57 sgo:sdDataset chapters
58 rdf:type schema:Chapter
59 N8aec291cc0f143a0aa0b90a5e8b70e90 schema:isbn 978-3-642-39273-3
60 978-3-642-39274-0
61 schema:name Implementation and Application of Automata
62 rdf:type schema:Book
63 N8c13a73a9b59465da6e12191c57b09aa schema:name Springer Nature
64 rdf:type schema:Organisation
65 N8dd6ec86066446268aefd6a5ff0edc40 schema:name Springer Nature - SN SciGraph project
66 rdf:type schema:Organization
67 Nca7bdb31dd6a4fb88091edde47dd22ce rdf:first sg:person.016645332751.01
68 rdf:rest rdf:nil
69 Nd1e7752a99bc4ef2bd1a6b104bde74a9 schema:familyName Konstantinidis
70 schema:givenName Stavros
71 rdf:type schema:Person
72 Ne0e707c606bf45bab5e79f53297831eb schema:name doi
73 schema:value 10.1007/978-3-642-39274-0_22
74 rdf:type schema:PropertyValue
75 Nf152e28149d346c3acded680a5c9c343 rdf:first Nd1e7752a99bc4ef2bd1a6b104bde74a9
76 rdf:rest rdf:nil
77 Nf3df755b0cbb46168470f0d623b3c3c1 schema:name dimensions_id
78 schema:value pub.1041235264
79 rdf:type schema:PropertyValue
80 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
81 schema:name Language, Communication and Culture
82 rdf:type schema:DefinedTerm
83 anzsrc-for:2004 schema:inDefinedTermSet anzsrc-for:
84 schema:name Linguistics
85 rdf:type schema:DefinedTerm
86 sg:person.016645332751.01 schema:affiliation grid-institutes:grid.5719.a
87 schema:familyName Maletti
88 schema:givenName Andreas
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016645332751.01
90 rdf:type schema:Person
91 grid-institutes:grid.5719.a schema:alternateName Institute for Natural Language Processing, Universität Stuttgart, Pfaffenwaldring 5b, 70569, Stuttgart, Germany
92 schema:name Institute for Natural Language Processing, Universität Stuttgart, Pfaffenwaldring 5b, 70569, Stuttgart, Germany
93 rdf:type schema:Organization