A Kleene Theorem for Weighted Tree Automata over Distributive Multioperator Monoids View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2007-10-24

AUTHORS

Zoltán Fülöp, Andreas Maletti, Heiko Vogler

ABSTRACT

Kleene’s theorem on the equivalence of recognizability and rationality for formal tree series over distributive multioperator monoids is proved. As a consequence of this, Kleene’s theorem for weighted tree automata over arbitrary, i.e., not necessarily commutative, semirings is derived.

PAGES

455-499

References to SciGraph publications

  • 1968-03. Generalized finite automata theory with an application to a decision problem of second-order logic in THEORY OF COMPUTING SYSTEMS
  • 1997. Two-Dimensional Languages in HANDBOOK OF FORMAL LANGUAGES
  • 2003. Kleene’s Theorem for Weighted Tree-Automata in FUNDAMENTALS OF COMPUTATION THEORY
  • 1999-02. Equational Elements in Additive Algebras in THEORY OF COMPUTING SYSTEMS
  • 2004-09-15. A Kleene Theorem for Weighted Tree Automata in THEORY OF COMPUTING SYSTEMS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00224-007-9091-9

    DOI

    http://dx.doi.org/10.1007/s00224-007-9091-9

    DIMENSIONS

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


    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/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "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/0102", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Applied Mathematics", 
            "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"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0805", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Distributed Computing", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, University of Szeged, \u00c1rp\u00e1d t\u00e9r 2., 6720, Szeged, Hungary", 
              "id": "http://www.grid.ac/institutes/grid.9008.1", 
              "name": [
                "Department of Computer Science, University of Szeged, \u00c1rp\u00e1d t\u00e9r 2., 6720, 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": "Faculty of Computer Science, Dresden University of Technology, 01062, Dresden, Germany", 
              "id": "http://www.grid.ac/institutes/grid.4488.0", 
              "name": [
                "Faculty of Computer Science, Dresden University of Technology, 01062, Dresden, 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"
          }, 
          {
            "affiliation": {
              "alternateName": "Faculty of Computer Science, Dresden University of Technology, 01062, Dresden, Germany", 
              "id": "http://www.grid.ac/institutes/grid.4488.0", 
              "name": [
                "Faculty of Computer Science, Dresden University of Technology, 01062, 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"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-642-59126-6_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001827630", 
              "https://doi.org/10.1007/978-3-642-59126-6_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01691346", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038809008", 
              "https://doi.org/10.1007/bf01691346"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s002240000110", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024542271", 
              "https://doi.org/10.1007/s002240000110"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-004-1096-z", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014237043", 
              "https://doi.org/10.1007/s00224-004-1096-z"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-45077-1_36", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014459493", 
              "https://doi.org/10.1007/978-3-540-45077-1_36"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2007-10-24", 
        "datePublishedReg": "2007-10-24", 
        "description": "Abstract\nKleene\u2019s theorem on the equivalence of recognizability and rationality for formal tree series over distributive multioperator monoids is proved. As a consequence of this, Kleene\u2019s theorem for weighted tree automata over arbitrary, i.e., not necessarily commutative, semirings is derived.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00224-007-9091-9", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1052098", 
            "issn": [
              "1432-4350", 
              "1433-0490"
            ], 
            "name": "Theory of Computing Systems", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "44"
          }
        ], 
        "keywords": [
          "tree series", 
          "consequences", 
          "series", 
          "Kleene theorem", 
          "theorem", 
          "equivalence", 
          "recognizability", 
          "monoids", 
          "automata", 
          "semirings", 
          "equivalence of recognizability", 
          "rationality", 
          "formal tree series", 
          "distributive multioperator monoids", 
          "multioperator monoids", 
          "Weighted Tree Automata", 
          "tree automata"
        ], 
        "name": "A Kleene Theorem for Weighted Tree Automata over Distributive Multioperator Monoids", 
        "pagination": "455-499", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1003330683"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00224-007-9091-9"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00224-007-9091-9", 
          "https://app.dimensions.ai/details/publication/pub.1003330683"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-01-01T18:17", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/article/article_444.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00224-007-9091-9"
      }
    ]
     

    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/s00224-007-9091-9'

    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/s00224-007-9091-9'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-007-9091-9'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00224-007-9091-9'


     

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

    124 TRIPLES      22 PREDICATES      50 URIs      34 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00224-007-9091-9 schema:about anzsrc-for:01
    2 anzsrc-for:0102
    3 anzsrc-for:08
    4 anzsrc-for:0802
    5 anzsrc-for:0805
    6 schema:author Ne194c349655146969dee4e93a13b18ce
    7 schema:citation sg:pub.10.1007/978-3-540-45077-1_36
    8 sg:pub.10.1007/978-3-642-59126-6_4
    9 sg:pub.10.1007/bf01691346
    10 sg:pub.10.1007/s00224-004-1096-z
    11 sg:pub.10.1007/s002240000110
    12 schema:datePublished 2007-10-24
    13 schema:datePublishedReg 2007-10-24
    14 schema:description Abstract Kleene’s theorem on the equivalence of recognizability and rationality for formal tree series over distributive multioperator monoids is proved. As a consequence of this, Kleene’s theorem for weighted tree automata over arbitrary, i.e., not necessarily commutative, semirings is derived.
    15 schema:genre article
    16 schema:inLanguage en
    17 schema:isAccessibleForFree false
    18 schema:isPartOf Nc7256e60b4b444a8b1dbd751db77b841
    19 Ncb5a7d9d8a7144eca1cb4460779eb3d8
    20 sg:journal.1052098
    21 schema:keywords Kleene theorem
    22 Weighted Tree Automata
    23 automata
    24 consequences
    25 distributive multioperator monoids
    26 equivalence
    27 equivalence of recognizability
    28 formal tree series
    29 monoids
    30 multioperator monoids
    31 rationality
    32 recognizability
    33 semirings
    34 series
    35 theorem
    36 tree automata
    37 tree series
    38 schema:name A Kleene Theorem for Weighted Tree Automata over Distributive Multioperator Monoids
    39 schema:pagination 455-499
    40 schema:productId N12ef5a6810e147d992185bc04374f029
    41 N19cba913ad9f472b9a74f9520ea51091
    42 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003330683
    43 https://doi.org/10.1007/s00224-007-9091-9
    44 schema:sdDatePublished 2022-01-01T18:17
    45 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    46 schema:sdPublisher Nc0756405651e4e50878d1d2822629704
    47 schema:url https://doi.org/10.1007/s00224-007-9091-9
    48 sgo:license sg:explorer/license/
    49 sgo:sdDataset articles
    50 rdf:type schema:ScholarlyArticle
    51 N12ef5a6810e147d992185bc04374f029 schema:name doi
    52 schema:value 10.1007/s00224-007-9091-9
    53 rdf:type schema:PropertyValue
    54 N19cba913ad9f472b9a74f9520ea51091 schema:name dimensions_id
    55 schema:value pub.1003330683
    56 rdf:type schema:PropertyValue
    57 N44c70c327d6e482aac709b131f0ef9d2 rdf:first sg:person.016645332751.01
    58 rdf:rest N91b520a74aa84e19aa31b327bd48c54b
    59 N91b520a74aa84e19aa31b327bd48c54b rdf:first sg:person.014562633673.93
    60 rdf:rest rdf:nil
    61 Nc0756405651e4e50878d1d2822629704 schema:name Springer Nature - SN SciGraph project
    62 rdf:type schema:Organization
    63 Nc7256e60b4b444a8b1dbd751db77b841 schema:issueNumber 3
    64 rdf:type schema:PublicationIssue
    65 Ncb5a7d9d8a7144eca1cb4460779eb3d8 schema:volumeNumber 44
    66 rdf:type schema:PublicationVolume
    67 Ne194c349655146969dee4e93a13b18ce rdf:first sg:person.014007607055.43
    68 rdf:rest N44c70c327d6e482aac709b131f0ef9d2
    69 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    70 schema:name Mathematical Sciences
    71 rdf:type schema:DefinedTerm
    72 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
    73 schema:name Applied Mathematics
    74 rdf:type schema:DefinedTerm
    75 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    76 schema:name Information and Computing Sciences
    77 rdf:type schema:DefinedTerm
    78 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    79 schema:name Computation Theory and Mathematics
    80 rdf:type schema:DefinedTerm
    81 anzsrc-for:0805 schema:inDefinedTermSet anzsrc-for:
    82 schema:name Distributed Computing
    83 rdf:type schema:DefinedTerm
    84 sg:journal.1052098 schema:issn 1432-4350
    85 1433-0490
    86 schema:name Theory of Computing Systems
    87 schema:publisher Springer Nature
    88 rdf:type schema:Periodical
    89 sg:person.014007607055.43 schema:affiliation grid-institutes:grid.9008.1
    90 schema:familyName Fülöp
    91 schema:givenName Zoltán
    92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014007607055.43
    93 rdf:type schema:Person
    94 sg:person.014562633673.93 schema:affiliation grid-institutes:grid.4488.0
    95 schema:familyName Vogler
    96 schema:givenName Heiko
    97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014562633673.93
    98 rdf:type schema:Person
    99 sg:person.016645332751.01 schema:affiliation grid-institutes:grid.4488.0
    100 schema:familyName Maletti
    101 schema:givenName Andreas
    102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016645332751.01
    103 rdf:type schema:Person
    104 sg:pub.10.1007/978-3-540-45077-1_36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014459493
    105 https://doi.org/10.1007/978-3-540-45077-1_36
    106 rdf:type schema:CreativeWork
    107 sg:pub.10.1007/978-3-642-59126-6_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001827630
    108 https://doi.org/10.1007/978-3-642-59126-6_4
    109 rdf:type schema:CreativeWork
    110 sg:pub.10.1007/bf01691346 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038809008
    111 https://doi.org/10.1007/bf01691346
    112 rdf:type schema:CreativeWork
    113 sg:pub.10.1007/s00224-004-1096-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1014237043
    114 https://doi.org/10.1007/s00224-004-1096-z
    115 rdf:type schema:CreativeWork
    116 sg:pub.10.1007/s002240000110 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024542271
    117 https://doi.org/10.1007/s002240000110
    118 rdf:type schema:CreativeWork
    119 grid-institutes:grid.4488.0 schema:alternateName Faculty of Computer Science, Dresden University of Technology, 01062, Dresden, Germany
    120 schema:name Faculty of Computer Science, Dresden University of Technology, 01062, Dresden, Germany
    121 rdf:type schema:Organization
    122 grid-institutes:grid.9008.1 schema:alternateName Department of Computer Science, University of Szeged, Árpád tér 2., 6720, Szeged, Hungary
    123 schema:name Department of Computer Science, University of Szeged, Árpád tér 2., 6720, Szeged, Hungary
    124 rdf:type schema:Organization
     




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


    ...