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": "2021-12-01T19:20", 
        "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/article/article_452.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 N001126abdb684b098f25c704d158f1f1
    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 N434e91a36c5a4d63b573589eb3714757
    19 N6391586423ed443a8ad33a6fec26d9b8
    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 N9d9c89e5870841d99f252684881f80bc
    41 Nf45eeece1d78489089ba02b33828685b
    42 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003330683
    43 https://doi.org/10.1007/s00224-007-9091-9
    44 schema:sdDatePublished 2021-12-01T19:20
    45 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    46 schema:sdPublisher Ndece32ec4ff4484da40a25cbd8d77e5d
    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 N001126abdb684b098f25c704d158f1f1 rdf:first sg:person.014007607055.43
    52 rdf:rest N99e2544f7b6c4bde9bc392da9c0cf548
    53 N434e91a36c5a4d63b573589eb3714757 schema:volumeNumber 44
    54 rdf:type schema:PublicationVolume
    55 N6391586423ed443a8ad33a6fec26d9b8 schema:issueNumber 3
    56 rdf:type schema:PublicationIssue
    57 N99e2544f7b6c4bde9bc392da9c0cf548 rdf:first sg:person.016645332751.01
    58 rdf:rest Nee89e2bde08243b7a5af55d02e044614
    59 N9d9c89e5870841d99f252684881f80bc schema:name dimensions_id
    60 schema:value pub.1003330683
    61 rdf:type schema:PropertyValue
    62 Ndece32ec4ff4484da40a25cbd8d77e5d schema:name Springer Nature - SN SciGraph project
    63 rdf:type schema:Organization
    64 Nee89e2bde08243b7a5af55d02e044614 rdf:first sg:person.014562633673.93
    65 rdf:rest rdf:nil
    66 Nf45eeece1d78489089ba02b33828685b schema:name doi
    67 schema:value 10.1007/s00224-007-9091-9
    68 rdf:type schema:PropertyValue
    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)


    ...