Characterizations of recognizable weighted tree languages by logic and bimorphisms View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2015-05-29

AUTHORS

Zoltán Fülöp, Heiko Vogler

ABSTRACT

We give a general definition of weighted tree automata (wta) and define three instances which differ in the underlying weight algebras: semirings, multi-operator monoids, and tree-valuation monoids. Also, we define a general concept of weighted expressions based on monadic second-order logics. In the same way as for wta, we define three instances corresponding to the above-mentioned weight algebras. We prove that wta over semirings are equivalent to weighted expressions over semirings, and prove the same equivalence over tree-valuation monoids. For wta over semirings and for wta over tree-valuation monoids we prove characterizations in terms of bimorphisms. More... »

PAGES

1035-1046

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
  • 1975-06. Bottom-up and top-down tree transformations— a comparison in THEORY OF COMPUTING SYSTEMS
  • 2009-06-27. Weighted Logics for Unranked Tree Automata in THEORY OF COMPUTING SYSTEMS
  • 2009-09-16. Weighted Automata and Weighted Logics in HANDBOOK OF WEIGHTED AUTOMATA
  • 2009-09-16. Weighted Tree Automata and Tree Transducers in HANDBOOK OF WEIGHTED AUTOMATA
  • 2011. Weighted Tree Automata over Valuation Monoids and Their Characterization by Weighted Logics in ALGEBRAIC FOUNDATIONS IN COMPUTER SCIENCE
  • 2010-10-28. A Büchi-Like Theorem for Weighted Tree Automata over Multioperator Monoids in THEORY OF COMPUTING SYSTEMS
  • 2005. Weighted Automata and Weighted Logics in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 2007-10-24. A Kleene Theorem for Weighted Tree Automata over Distributive Multioperator Monoids in THEORY OF COMPUTING SYSTEMS
  • 1997. Tree Languages in HANDBOOK OF FORMAL LANGUAGES
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00500-015-1717-2

    DOI

    http://dx.doi.org/10.1007/s00500-015-1717-2

    DIMENSIONS

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


    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/17", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Psychology and Cognitive 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/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1702", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Cognitive Sciences", 
            "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, Technische Universit\u00e4t Dresden, 01062, Dresden, Germany", 
              "id": "http://www.grid.ac/institutes/grid.4488.0", 
              "name": [
                "Faculty of Computer Science, Technische Universit\u00e4t Dresden, 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/bf01691346", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038809008", 
              "https://doi.org/10.1007/bf01691346"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11523468_42", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003892152", 
              "https://doi.org/10.1007/11523468_42"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-01492-5_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013273492", 
              "https://doi.org/10.1007/978-3-642-01492-5_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-007-9091-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003330683", 
              "https://doi.org/10.1007/s00224-007-9091-9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-24897-9_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024563312", 
              "https://doi.org/10.1007/978-3-642-24897-9_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01704020", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006876172", 
              "https://doi.org/10.1007/bf01704020"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-010-9296-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051700987", 
              "https://doi.org/10.1007/s00224-010-9296-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-59126-6_1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000867424", 
              "https://doi.org/10.1007/978-3-642-59126-6_1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-01492-5_5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009402049", 
              "https://doi.org/10.1007/978-3-642-01492-5_5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-009-9224-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045410699", 
              "https://doi.org/10.1007/s00224-009-9224-4"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2015-05-29", 
        "datePublishedReg": "2015-05-29", 
        "description": "We give a general definition of weighted tree automata (wta) and define three instances which differ in the underlying weight algebras: semirings, multi-operator monoids, and tree-valuation monoids. Also, we define a general concept of weighted expressions based on monadic second-order logics. In the same way as for wta, we define three instances corresponding to the above-mentioned weight algebras. We prove that wta over semirings are equivalent to weighted expressions over semirings, and prove the same equivalence over tree-valuation monoids. For wta over semirings and for wta over tree-valuation monoids we prove characterizations in terms of bimorphisms.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00500-015-1717-2", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1050238", 
            "issn": [
              "1432-7643", 
              "1433-7479"
            ], 
            "name": "Soft Computing", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "4", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "22"
          }
        ], 
        "keywords": [
          "weight algebra", 
          "monadic second-order logic", 
          "algebra", 
          "semirings", 
          "monoids", 
          "second-order logic", 
          "same equivalence", 
          "general definition", 
          "weighted expressions", 
          "general concept", 
          "equivalence", 
          "automata", 
          "instances", 
          "bimorphisms", 
          "tree automata", 
          "same way", 
          "terms", 
          "logic", 
          "tree languages", 
          "definition", 
          "concept", 
          "WTA", 
          "characterization", 
          "way", 
          "expression", 
          "language"
        ], 
        "name": "Characterizations of recognizable weighted tree languages by logic and bimorphisms", 
        "pagination": "1035-1046", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1006617090"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00500-015-1717-2"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00500-015-1717-2", 
          "https://app.dimensions.ai/details/publication/pub.1006617090"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-05-10T10:14", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/article/article_665.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00500-015-1717-2"
      }
    ]
     

    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/s00500-015-1717-2'

    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/s00500-015-1717-2'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00500-015-1717-2'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00500-015-1717-2'


     

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

    150 TRIPLES      22 PREDICATES      65 URIs      43 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00500-015-1717-2 schema:about anzsrc-for:01
    2 anzsrc-for:0102
    3 anzsrc-for:08
    4 anzsrc-for:0801
    5 anzsrc-for:17
    6 anzsrc-for:1702
    7 schema:author N5fb0c1eb1dc34e10b5d93b2af9c8f258
    8 schema:citation sg:pub.10.1007/11523468_42
    9 sg:pub.10.1007/978-3-642-01492-5_5
    10 sg:pub.10.1007/978-3-642-01492-5_9
    11 sg:pub.10.1007/978-3-642-24897-9_2
    12 sg:pub.10.1007/978-3-642-59126-6_1
    13 sg:pub.10.1007/bf01691346
    14 sg:pub.10.1007/bf01704020
    15 sg:pub.10.1007/s00224-007-9091-9
    16 sg:pub.10.1007/s00224-009-9224-4
    17 sg:pub.10.1007/s00224-010-9296-1
    18 schema:datePublished 2015-05-29
    19 schema:datePublishedReg 2015-05-29
    20 schema:description We give a general definition of weighted tree automata (wta) and define three instances which differ in the underlying weight algebras: semirings, multi-operator monoids, and tree-valuation monoids. Also, we define a general concept of weighted expressions based on monadic second-order logics. In the same way as for wta, we define three instances corresponding to the above-mentioned weight algebras. We prove that wta over semirings are equivalent to weighted expressions over semirings, and prove the same equivalence over tree-valuation monoids. For wta over semirings and for wta over tree-valuation monoids we prove characterizations in terms of bimorphisms.
    21 schema:genre article
    22 schema:inLanguage en
    23 schema:isAccessibleForFree false
    24 schema:isPartOf N70e80c3110f044468c0a7f99a912b268
    25 Nd0ca2b13147c4531953559c4f485754b
    26 sg:journal.1050238
    27 schema:keywords WTA
    28 algebra
    29 automata
    30 bimorphisms
    31 characterization
    32 concept
    33 definition
    34 equivalence
    35 expression
    36 general concept
    37 general definition
    38 instances
    39 language
    40 logic
    41 monadic second-order logic
    42 monoids
    43 same equivalence
    44 same way
    45 second-order logic
    46 semirings
    47 terms
    48 tree automata
    49 tree languages
    50 way
    51 weight algebra
    52 weighted expressions
    53 schema:name Characterizations of recognizable weighted tree languages by logic and bimorphisms
    54 schema:pagination 1035-1046
    55 schema:productId N166289d606d6409caeaaaebf71001a5e
    56 Ned22823bfe1d4a1c99f902a923f172e4
    57 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006617090
    58 https://doi.org/10.1007/s00500-015-1717-2
    59 schema:sdDatePublished 2022-05-10T10:14
    60 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    61 schema:sdPublisher N3409a44c1d7042a59e2cb369b3ee9a38
    62 schema:url https://doi.org/10.1007/s00500-015-1717-2
    63 sgo:license sg:explorer/license/
    64 sgo:sdDataset articles
    65 rdf:type schema:ScholarlyArticle
    66 N166289d606d6409caeaaaebf71001a5e schema:name doi
    67 schema:value 10.1007/s00500-015-1717-2
    68 rdf:type schema:PropertyValue
    69 N3409a44c1d7042a59e2cb369b3ee9a38 schema:name Springer Nature - SN SciGraph project
    70 rdf:type schema:Organization
    71 N3b089b43d07541438e77c0f7239c2b07 rdf:first sg:person.014562633673.93
    72 rdf:rest rdf:nil
    73 N5fb0c1eb1dc34e10b5d93b2af9c8f258 rdf:first sg:person.014007607055.43
    74 rdf:rest N3b089b43d07541438e77c0f7239c2b07
    75 N70e80c3110f044468c0a7f99a912b268 schema:issueNumber 4
    76 rdf:type schema:PublicationIssue
    77 Nd0ca2b13147c4531953559c4f485754b schema:volumeNumber 22
    78 rdf:type schema:PublicationVolume
    79 Ned22823bfe1d4a1c99f902a923f172e4 schema:name dimensions_id
    80 schema:value pub.1006617090
    81 rdf:type schema:PropertyValue
    82 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    83 schema:name Mathematical Sciences
    84 rdf:type schema:DefinedTerm
    85 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
    86 schema:name Applied Mathematics
    87 rdf:type schema:DefinedTerm
    88 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    89 schema:name Information and Computing Sciences
    90 rdf:type schema:DefinedTerm
    91 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    92 schema:name Artificial Intelligence and Image Processing
    93 rdf:type schema:DefinedTerm
    94 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
    95 schema:name Psychology and Cognitive Sciences
    96 rdf:type schema:DefinedTerm
    97 anzsrc-for:1702 schema:inDefinedTermSet anzsrc-for:
    98 schema:name Cognitive Sciences
    99 rdf:type schema:DefinedTerm
    100 sg:journal.1050238 schema:issn 1432-7643
    101 1433-7479
    102 schema:name Soft Computing
    103 schema:publisher Springer Nature
    104 rdf:type schema:Periodical
    105 sg:person.014007607055.43 schema:affiliation grid-institutes:grid.9008.1
    106 schema:familyName Fülöp
    107 schema:givenName Zoltán
    108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014007607055.43
    109 rdf:type schema:Person
    110 sg:person.014562633673.93 schema:affiliation grid-institutes:grid.4488.0
    111 schema:familyName Vogler
    112 schema:givenName Heiko
    113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014562633673.93
    114 rdf:type schema:Person
    115 sg:pub.10.1007/11523468_42 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003892152
    116 https://doi.org/10.1007/11523468_42
    117 rdf:type schema:CreativeWork
    118 sg:pub.10.1007/978-3-642-01492-5_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009402049
    119 https://doi.org/10.1007/978-3-642-01492-5_5
    120 rdf:type schema:CreativeWork
    121 sg:pub.10.1007/978-3-642-01492-5_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013273492
    122 https://doi.org/10.1007/978-3-642-01492-5_9
    123 rdf:type schema:CreativeWork
    124 sg:pub.10.1007/978-3-642-24897-9_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024563312
    125 https://doi.org/10.1007/978-3-642-24897-9_2
    126 rdf:type schema:CreativeWork
    127 sg:pub.10.1007/978-3-642-59126-6_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000867424
    128 https://doi.org/10.1007/978-3-642-59126-6_1
    129 rdf:type schema:CreativeWork
    130 sg:pub.10.1007/bf01691346 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038809008
    131 https://doi.org/10.1007/bf01691346
    132 rdf:type schema:CreativeWork
    133 sg:pub.10.1007/bf01704020 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006876172
    134 https://doi.org/10.1007/bf01704020
    135 rdf:type schema:CreativeWork
    136 sg:pub.10.1007/s00224-007-9091-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003330683
    137 https://doi.org/10.1007/s00224-007-9091-9
    138 rdf:type schema:CreativeWork
    139 sg:pub.10.1007/s00224-009-9224-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045410699
    140 https://doi.org/10.1007/s00224-009-9224-4
    141 rdf:type schema:CreativeWork
    142 sg:pub.10.1007/s00224-010-9296-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051700987
    143 https://doi.org/10.1007/s00224-010-9296-1
    144 rdf:type schema:CreativeWork
    145 grid-institutes:grid.4488.0 schema:alternateName Faculty of Computer Science, Technische Universität Dresden, 01062, Dresden, Germany
    146 schema:name Faculty of Computer Science, Technische Universität Dresden, 01062, Dresden, Germany
    147 rdf:type schema:Organization
    148 grid-institutes:grid.9008.1 schema:alternateName Department of Computer Science, University of Szeged, Árpád tér 2, 6720, Szeged, Hungary
    149 schema:name Department of Computer Science, University of Szeged, Árpád tér 2, 6720, Szeged, Hungary
    150 rdf:type schema:Organization
     




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


    ...