Crisp-Determinization of Weighted Tree Automata over Additively Locally Finite and Past-Finite Monotonic Strong Bimonoids Is Decidable View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2020-11-06

AUTHORS

Manfred Droste , Zoltán Fülöp , Dávid Kószó , Heiko Vogler

ABSTRACT

A weighted tree automaton is crisp-deterministic if it is deterministic and each of its transitions carries either the additive or multiplicative unit of the underlying weight algebra; weights different from these units may only appear at the root of the given input tree. A weighted tree automaton is crisp-determinizable if there exists an equivalent crisp-deterministic one. We prove that it is decidable whether weighted tree automata over additively locally finite and past-finite monotonic strong bimonoids are crisp-determinizable. More... »

PAGES

39-51

Book

TITLE

Descriptional Complexity of Formal Systems

ISBN

978-3-030-62535-1
978-3-030-62536-8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-62536-8_4

DOI

http://dx.doi.org/10.1007/978-3-030-62536-8_4

DIMENSIONS

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


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/06", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Biological Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0607", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Plant Biology", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Leipzig, Leipzig, Germany", 
          "id": "http://www.grid.ac/institutes/grid.9647.c", 
          "name": [
            "University of Leipzig, Leipzig, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Droste", 
        "givenName": "Manfred", 
        "id": "sg:person.010545141652.14", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010545141652.14"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Szeged, Szeged, Hungary", 
          "id": "http://www.grid.ac/institutes/grid.9008.1", 
          "name": [
            "University of Szeged, Szeged, Hungary"
          ], 
          "type": "Organization"
        }, 
        "familyName": "F\u00fcl\u00f6p", 
        "givenName": "Zolt\u00e1n", 
        "id": "sg:person.014007607055.43", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014007607055.43"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Szeged, Szeged, Hungary", 
          "id": "http://www.grid.ac/institutes/grid.9008.1", 
          "name": [
            "University of Szeged, Szeged, Hungary"
          ], 
          "type": "Organization"
        }, 
        "familyName": "K\u00f3sz\u00f3", 
        "givenName": "D\u00e1vid", 
        "id": "sg:person.013635021547.32", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013635021547.32"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Technische Universit\u00e4t Dresden, Dresden, Germany", 
          "id": "http://www.grid.ac/institutes/grid.4488.0", 
          "name": [
            "Technische Universit\u00e4t Dresden, Dresden, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vogler", 
        "givenName": "Heiko", 
        "id": "sg:person.014562633673.93", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014562633673.93"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2020-11-06", 
    "datePublishedReg": "2020-11-06", 
    "description": "A weighted tree automaton is crisp-deterministic if it is deterministic and each of its transitions carries either the additive or multiplicative unit of the underlying weight algebra; weights different from these units may only appear at the root of the given input tree. A weighted tree automaton is crisp-determinizable if there exists an equivalent crisp-deterministic one. We prove that it is decidable whether weighted tree automata over additively locally finite and past-finite monotonic strong bimonoids are crisp-determinizable.", 
    "editor": [
      {
        "familyName": "Jir\u00e1skov\u00e1", 
        "givenName": "Galina", 
        "type": "Person"
      }, 
      {
        "familyName": "Pighizzini", 
        "givenName": "Giovanni", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-62536-8_4", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-030-62535-1", 
        "978-3-030-62536-8"
      ], 
      "name": "Descriptional Complexity of Formal Systems", 
      "type": "Book"
    }, 
    "keywords": [
      "weight algebra", 
      "multiplicative unit", 
      "finite", 
      "automata", 
      "algebra", 
      "bimonoids", 
      "strong bimonoids", 
      "tree automata", 
      "input trees", 
      "transition", 
      "Weighted Tree Automata", 
      "one", 
      "units", 
      "trees", 
      "roots", 
      "weight"
    ], 
    "name": "Crisp-Determinization of Weighted Tree Automata over Additively Locally Finite and Past-Finite Monotonic Strong Bimonoids Is Decidable", 
    "pagination": "39-51", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1132401198"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-62536-8_4"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-62536-8_4", 
      "https://app.dimensions.ai/details/publication/pub.1132401198"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:44", 
    "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_256.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-62536-8_4"
  }
]
 

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-030-62536-8_4'

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-030-62536-8_4'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-62536-8_4'

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-030-62536-8_4'


 

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

108 TRIPLES      23 PREDICATES      41 URIs      34 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-62536-8_4 schema:about anzsrc-for:06
2 anzsrc-for:0607
3 schema:author N5f8bed9dc6eb4300926133ea59c531ed
4 schema:datePublished 2020-11-06
5 schema:datePublishedReg 2020-11-06
6 schema:description A weighted tree automaton is crisp-deterministic if it is deterministic and each of its transitions carries either the additive or multiplicative unit of the underlying weight algebra; weights different from these units may only appear at the root of the given input tree. A weighted tree automaton is crisp-determinizable if there exists an equivalent crisp-deterministic one. We prove that it is decidable whether weighted tree automata over additively locally finite and past-finite monotonic strong bimonoids are crisp-determinizable.
7 schema:editor N281790ebe3c84f4da7cc3de6b746b4e7
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nfbda6d9723eb4554aebbe41be1ef5a60
12 schema:keywords Weighted Tree Automata
13 algebra
14 automata
15 bimonoids
16 finite
17 input trees
18 multiplicative unit
19 one
20 roots
21 strong bimonoids
22 transition
23 tree automata
24 trees
25 units
26 weight
27 weight algebra
28 schema:name Crisp-Determinization of Weighted Tree Automata over Additively Locally Finite and Past-Finite Monotonic Strong Bimonoids Is Decidable
29 schema:pagination 39-51
30 schema:productId N32c5cf3c9ebf4bd0b84eb4f93cb5aa74
31 Nbf7e3dcdcfe04acaa212bf00e07abded
32 schema:publisher Nb8157306c21e439fa4558da2a5ff9b65
33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1132401198
34 https://doi.org/10.1007/978-3-030-62536-8_4
35 schema:sdDatePublished 2022-05-20T07:44
36 schema:sdLicense https://scigraph.springernature.com/explorer/license/
37 schema:sdPublisher N0b7b4874361e4b50b6527934f91c3a65
38 schema:url https://doi.org/10.1007/978-3-030-62536-8_4
39 sgo:license sg:explorer/license/
40 sgo:sdDataset chapters
41 rdf:type schema:Chapter
42 N04d59e47078c416f834c9ddf61f5f955 rdf:first Nae4658a6f02a4bee91658221bd8642f1
43 rdf:rest rdf:nil
44 N0b7b4874361e4b50b6527934f91c3a65 schema:name Springer Nature - SN SciGraph project
45 rdf:type schema:Organization
46 N162c683f3df843d2bd9baab198d242ec rdf:first sg:person.014007607055.43
47 rdf:rest Na39d8a6ca52a48e1ad8441f97d03719e
48 N1991cbe4cbf64ca4a58cf0de39ca0b93 rdf:first sg:person.014562633673.93
49 rdf:rest rdf:nil
50 N281790ebe3c84f4da7cc3de6b746b4e7 rdf:first Nb6124e2eaccf4ada880115cebac811a4
51 rdf:rest N04d59e47078c416f834c9ddf61f5f955
52 N32c5cf3c9ebf4bd0b84eb4f93cb5aa74 schema:name doi
53 schema:value 10.1007/978-3-030-62536-8_4
54 rdf:type schema:PropertyValue
55 N5f8bed9dc6eb4300926133ea59c531ed rdf:first sg:person.010545141652.14
56 rdf:rest N162c683f3df843d2bd9baab198d242ec
57 Na39d8a6ca52a48e1ad8441f97d03719e rdf:first sg:person.013635021547.32
58 rdf:rest N1991cbe4cbf64ca4a58cf0de39ca0b93
59 Nae4658a6f02a4bee91658221bd8642f1 schema:familyName Pighizzini
60 schema:givenName Giovanni
61 rdf:type schema:Person
62 Nb6124e2eaccf4ada880115cebac811a4 schema:familyName Jirásková
63 schema:givenName Galina
64 rdf:type schema:Person
65 Nb8157306c21e439fa4558da2a5ff9b65 schema:name Springer Nature
66 rdf:type schema:Organisation
67 Nbf7e3dcdcfe04acaa212bf00e07abded schema:name dimensions_id
68 schema:value pub.1132401198
69 rdf:type schema:PropertyValue
70 Nfbda6d9723eb4554aebbe41be1ef5a60 schema:isbn 978-3-030-62535-1
71 978-3-030-62536-8
72 schema:name Descriptional Complexity of Formal Systems
73 rdf:type schema:Book
74 anzsrc-for:06 schema:inDefinedTermSet anzsrc-for:
75 schema:name Biological Sciences
76 rdf:type schema:DefinedTerm
77 anzsrc-for:0607 schema:inDefinedTermSet anzsrc-for:
78 schema:name Plant Biology
79 rdf:type schema:DefinedTerm
80 sg:person.010545141652.14 schema:affiliation grid-institutes:grid.9647.c
81 schema:familyName Droste
82 schema:givenName Manfred
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010545141652.14
84 rdf:type schema:Person
85 sg:person.013635021547.32 schema:affiliation grid-institutes:grid.9008.1
86 schema:familyName Kószó
87 schema:givenName Dávid
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013635021547.32
89 rdf:type schema:Person
90 sg:person.014007607055.43 schema:affiliation grid-institutes:grid.9008.1
91 schema:familyName Fülöp
92 schema:givenName Zoltán
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014007607055.43
94 rdf:type schema:Person
95 sg:person.014562633673.93 schema:affiliation grid-institutes:grid.4488.0
96 schema:familyName Vogler
97 schema:givenName Heiko
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014562633673.93
99 rdf:type schema:Person
100 grid-institutes:grid.4488.0 schema:alternateName Technische Universität Dresden, Dresden, Germany
101 schema:name Technische Universität Dresden, Dresden, Germany
102 rdf:type schema:Organization
103 grid-institutes:grid.9008.1 schema:alternateName University of Szeged, Szeged, Hungary
104 schema:name University of Szeged, Szeged, Hungary
105 rdf:type schema:Organization
106 grid-institutes:grid.9647.c schema:alternateName University of Leipzig, Leipzig, Germany
107 schema:name University of Leipzig, Leipzig, Germany
108 rdf:type schema:Organization
 




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


...