A Büchi-Like Theorem for Weighted Tree Automata over Multioperator Monoids View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2010-10-28

AUTHORS

Zoltán Fülöp, Torsten Stüber, Heiko Vogler

ABSTRACT

A multioperator monoid \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{A}$\end{document} is a commutative monoid with additional operations on its carrier set. A weighted tree automaton over \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{A}$\end{document} is a finite state tree automaton of which each transition is equipped with an operation of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{A}$\end{document}. We define M-expressions over \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{A}$\end{document} in the spirit of formulas of weighted monadic second-order logics and, as our main result, we prove that if \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{A}$\end{document} is absorptive, then the class of tree series recognizable by weighted tree automata over \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{A}$\end{document} coincides with the class of tree series definable by M-expressions over \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{A}$\end{document}. This result implies the known fact that for the series over semirings recognizability by weighted tree automata is equivalent with definability in syntactically restricted weighted monadic second-order logic. We prove this implication by providing two purely syntactical transformations, from M-expressions into formulas of syntactically restricted weighted monadic second-order logic, and vice versa. More... »

PAGES

241-278

References to SciGraph publications

  • 2004-09-15. A Kleene Theorem for Weighted Tree Automata in THEORY OF COMPUTING SYSTEMS
  • 1997. Two-Dimensional Languages in HANDBOOK OF FORMAL LANGUAGES
  • 1991-04. Effective construction of the syntactic algebra of a recognizable series on trees in ACTA INFORMATICA
  • 2007-01-01. Definable Transductions and Weighted Logics for Texts in DEVELOPMENTS IN LANGUAGE THEORY
  • 1997. Tree Languages in HANDBOOK OF FORMAL LANGUAGES
  • 2010. Kleene and Büchi Theorems for Weighted Automata and Multi-valued Logics over Arbitrary Bounded Lattices in DEVELOPMENTS IN LANGUAGE THEORY
  • 2002-09-02. Automata, Logic, and XML in COMPUTER SCIENCE LOGIC
  • 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
  • 2009. Handbook of Weighted Automata in NONE
  • 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-07-23. Weighted Picture Automata and Weighted Logics in THEORY OF COMPUTING SYSTEMS
  • 2007-01-01. Weighted Automata and Weighted Logics with Discounting in IMPLEMENTATION AND APPLICATION OF AUTOMATA
  • 2007-10-24. A Kleene Theorem for Weighted Tree Automata over Distributive Multioperator Monoids in THEORY OF COMPUTING SYSTEMS
  • 2005. Weighted Automata and Weighted Logics in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 2009. Weighted Timed MSO Logics in DEVELOPMENTS IN LANGUAGE THEORY
  • 2006. Weighted Logics for Traces in COMPUTER SCIENCE – THEORY AND APPLICATIONS
  • 2008-01-01. Weighted Logics for Nested Words and Algebraic Formal Power Series in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 1968-03. Generalized finite automata theory with an application to a decision problem of second-order logic in THEORY OF COMPUTING SYSTEMS
  • 2005. Logics for Unranked Trees: An Overview in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 2004. Relating Tree Series Transducers and Weighted Tree Automata in DEVELOPMENTS IN LANGUAGE THEORY
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00224-010-9296-1

    DOI

    http://dx.doi.org/10.1007/s00224-010-9296-1

    DIMENSIONS

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


    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, 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": "St\u00fcber", 
            "givenName": "Torsten", 
            "id": "sg:person.012312257577.46", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012312257577.46"
            ], 
            "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/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/3-540-45793-3_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002630146", 
              "https://doi.org/10.1007/3-540-45793-3_2"
            ], 
            "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/11753728_25", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028313790", 
              "https://doi.org/10.1007/11753728_25"
            ], 
            "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/978-3-642-02737-6_34", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053404068", 
              "https://doi.org/10.1007/978-3-642-02737-6_34"
            ], 
            "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/978-3-540-73208-2_31", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039600070", 
              "https://doi.org/10.1007/978-3-540-73208-2_31"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "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/978-3-540-30550-7_27", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037447229", 
              "https://doi.org/10.1007/978-3-540-30550-7_27"
            ], 
            "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-009-9225-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046469438", 
              "https://doi.org/10.1007/s00224-009-9225-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11523468_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046282968", 
              "https://doi.org/10.1007/11523468_4"
            ], 
            "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/bf01893886", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018745916", 
              "https://doi.org/10.1007/bf01893886"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-14455-4_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020627853", 
              "https://doi.org/10.1007/978-3-642-14455-4_16"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-01492-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005381459", 
              "https://doi.org/10.1007/978-3-642-01492-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-76336-9_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025393494", 
              "https://doi.org/10.1007/978-3-540-76336-9_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-70583-3_19", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031990544", 
              "https://doi.org/10.1007/978-3-540-70583-3_19"
            ], 
            "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"
          }, 
          {
            "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"
          }
        ], 
        "datePublished": "2010-10-28", 
        "datePublishedReg": "2010-10-28", 
        "description": "A multioperator monoid \\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}$\\mathcal{A}$\\end{document} is a commutative monoid with additional operations on its carrier set. A\u00a0weighted tree automaton over \\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}$\\mathcal{A}$\\end{document} is a finite state tree automaton of which each transition is equipped with an operation of\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}$\\mathcal{A}$\\end{document}. We define M-expressions over \\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}$\\mathcal{A}$\\end{document} in the spirit of formulas of weighted monadic second-order logics and, as our main result, we prove that if \\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}$\\mathcal{A}$\\end{document} is absorptive, then the class of tree series recognizable by weighted tree automata over \\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}$\\mathcal{A}$\\end{document} coincides with the class of tree series definable by M-expressions over\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}$\\mathcal{A}$\\end{document}. This result implies the known fact that for the series over semirings recognizability by weighted tree automata is equivalent with definability in syntactically restricted weighted monadic second-order logic. We prove this implication by providing two purely syntactical transformations, from M-expressions into formulas of syntactically restricted weighted monadic second-order logic, and vice versa.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00224-010-9296-1", 
        "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": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "50"
          }
        ], 
        "keywords": [
          "operation", 
          "results", 
          "additional operations", 
          "formula", 
          "logic", 
          "carrier set", 
          "series", 
          "transition", 
          "transformation", 
          "set", 
          "main results", 
          "automata", 
          "vice", 
          "class", 
          "fact", 
          "theorem", 
          "syntactical transformations", 
          "expression", 
          "implications", 
          "recognizability", 
          "monadic second-order logic", 
          "spirit", 
          "second-order logic", 
          "monoids", 
          "commutative monoids", 
          "tree series", 
          "tree automata", 
          "definability", 
          "finite-state tree automaton", 
          "Weighted Tree Automata"
        ], 
        "name": "A B\u00fcchi-Like Theorem for Weighted Tree Automata over Multioperator Monoids", 
        "pagination": "241-278", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1051700987"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00224-010-9296-1"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00224-010-9296-1", 
          "https://app.dimensions.ai/details/publication/pub.1051700987"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-05-20T07:26", 
        "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/article/article_523.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00224-010-9296-1"
      }
    ]
     

    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-010-9296-1'

    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-010-9296-1'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-010-9296-1'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00224-010-9296-1'


     

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

    205 TRIPLES      22 PREDICATES      80 URIs      47 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00224-010-9296-1 schema:about anzsrc-for:01
    2 anzsrc-for:0102
    3 anzsrc-for:08
    4 anzsrc-for:0802
    5 anzsrc-for:0805
    6 schema:author N7280aab7f9bf43c9b107b1a1f2728c1e
    7 schema:citation sg:pub.10.1007/11523468_4
    8 sg:pub.10.1007/11523468_42
    9 sg:pub.10.1007/11753728_25
    10 sg:pub.10.1007/3-540-45793-3_2
    11 sg:pub.10.1007/978-3-540-30550-7_27
    12 sg:pub.10.1007/978-3-540-70583-3_19
    13 sg:pub.10.1007/978-3-540-73208-2_31
    14 sg:pub.10.1007/978-3-540-76336-9_9
    15 sg:pub.10.1007/978-3-642-01492-5
    16 sg:pub.10.1007/978-3-642-01492-5_5
    17 sg:pub.10.1007/978-3-642-01492-5_9
    18 sg:pub.10.1007/978-3-642-02737-6_34
    19 sg:pub.10.1007/978-3-642-14455-4_16
    20 sg:pub.10.1007/978-3-642-59126-6_1
    21 sg:pub.10.1007/978-3-642-59126-6_4
    22 sg:pub.10.1007/bf01691346
    23 sg:pub.10.1007/bf01704020
    24 sg:pub.10.1007/bf01893886
    25 sg:pub.10.1007/s00224-004-1096-z
    26 sg:pub.10.1007/s00224-007-9091-9
    27 sg:pub.10.1007/s00224-009-9224-4
    28 sg:pub.10.1007/s00224-009-9225-3
    29 schema:datePublished 2010-10-28
    30 schema:datePublishedReg 2010-10-28
    31 schema:description A multioperator monoid \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{A}$\end{document} is a commutative monoid with additional operations on its carrier set. A weighted tree automaton over \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{A}$\end{document} is a finite state tree automaton of which each transition is equipped with an operation of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{A}$\end{document}. We define M-expressions over \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{A}$\end{document} in the spirit of formulas of weighted monadic second-order logics and, as our main result, we prove that if \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{A}$\end{document} is absorptive, then the class of tree series recognizable by weighted tree automata over \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{A}$\end{document} coincides with the class of tree series definable by M-expressions over \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{A}$\end{document}. This result implies the known fact that for the series over semirings recognizability by weighted tree automata is equivalent with definability in syntactically restricted weighted monadic second-order logic. We prove this implication by providing two purely syntactical transformations, from M-expressions into formulas of syntactically restricted weighted monadic second-order logic, and vice versa.
    32 schema:genre article
    33 schema:inLanguage en
    34 schema:isAccessibleForFree false
    35 schema:isPartOf N14347ebcef2c4eb4bea580702cc78179
    36 N981fb05258cd4e79a8281f4a54087e01
    37 sg:journal.1052098
    38 schema:keywords Weighted Tree Automata
    39 additional operations
    40 automata
    41 carrier set
    42 class
    43 commutative monoids
    44 definability
    45 expression
    46 fact
    47 finite-state tree automaton
    48 formula
    49 implications
    50 logic
    51 main results
    52 monadic second-order logic
    53 monoids
    54 operation
    55 recognizability
    56 results
    57 second-order logic
    58 series
    59 set
    60 spirit
    61 syntactical transformations
    62 theorem
    63 transformation
    64 transition
    65 tree automata
    66 tree series
    67 vice
    68 schema:name A Büchi-Like Theorem for Weighted Tree Automata over Multioperator Monoids
    69 schema:pagination 241-278
    70 schema:productId N390b98f19b7d472ea911e6e2b0f462ae
    71 Ne3455713ec7e4e508cc1dc3fbdfe9068
    72 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051700987
    73 https://doi.org/10.1007/s00224-010-9296-1
    74 schema:sdDatePublished 2022-05-20T07:26
    75 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    76 schema:sdPublisher N0721cc25d32047ff8027f07ea80aba2a
    77 schema:url https://doi.org/10.1007/s00224-010-9296-1
    78 sgo:license sg:explorer/license/
    79 sgo:sdDataset articles
    80 rdf:type schema:ScholarlyArticle
    81 N0721cc25d32047ff8027f07ea80aba2a schema:name Springer Nature - SN SciGraph project
    82 rdf:type schema:Organization
    83 N14347ebcef2c4eb4bea580702cc78179 schema:issueNumber 2
    84 rdf:type schema:PublicationIssue
    85 N390b98f19b7d472ea911e6e2b0f462ae schema:name dimensions_id
    86 schema:value pub.1051700987
    87 rdf:type schema:PropertyValue
    88 N53ed244fcbaa4d6cb3ed4fede332a86e rdf:first sg:person.012312257577.46
    89 rdf:rest N691065cadee84e059ad9a2a208614da9
    90 N691065cadee84e059ad9a2a208614da9 rdf:first sg:person.014562633673.93
    91 rdf:rest rdf:nil
    92 N7280aab7f9bf43c9b107b1a1f2728c1e rdf:first sg:person.014007607055.43
    93 rdf:rest N53ed244fcbaa4d6cb3ed4fede332a86e
    94 N981fb05258cd4e79a8281f4a54087e01 schema:volumeNumber 50
    95 rdf:type schema:PublicationVolume
    96 Ne3455713ec7e4e508cc1dc3fbdfe9068 schema:name doi
    97 schema:value 10.1007/s00224-010-9296-1
    98 rdf:type schema:PropertyValue
    99 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    100 schema:name Mathematical Sciences
    101 rdf:type schema:DefinedTerm
    102 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
    103 schema:name Applied Mathematics
    104 rdf:type schema:DefinedTerm
    105 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    106 schema:name Information and Computing Sciences
    107 rdf:type schema:DefinedTerm
    108 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    109 schema:name Computation Theory and Mathematics
    110 rdf:type schema:DefinedTerm
    111 anzsrc-for:0805 schema:inDefinedTermSet anzsrc-for:
    112 schema:name Distributed Computing
    113 rdf:type schema:DefinedTerm
    114 sg:journal.1052098 schema:issn 1432-4350
    115 1433-0490
    116 schema:name Theory of Computing Systems
    117 schema:publisher Springer Nature
    118 rdf:type schema:Periodical
    119 sg:person.012312257577.46 schema:affiliation grid-institutes:grid.4488.0
    120 schema:familyName Stüber
    121 schema:givenName Torsten
    122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012312257577.46
    123 rdf:type schema:Person
    124 sg:person.014007607055.43 schema:affiliation grid-institutes:grid.9008.1
    125 schema:familyName Fülöp
    126 schema:givenName Zoltán
    127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014007607055.43
    128 rdf:type schema:Person
    129 sg:person.014562633673.93 schema:affiliation grid-institutes:grid.4488.0
    130 schema:familyName Vogler
    131 schema:givenName Heiko
    132 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014562633673.93
    133 rdf:type schema:Person
    134 sg:pub.10.1007/11523468_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046282968
    135 https://doi.org/10.1007/11523468_4
    136 rdf:type schema:CreativeWork
    137 sg:pub.10.1007/11523468_42 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003892152
    138 https://doi.org/10.1007/11523468_42
    139 rdf:type schema:CreativeWork
    140 sg:pub.10.1007/11753728_25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028313790
    141 https://doi.org/10.1007/11753728_25
    142 rdf:type schema:CreativeWork
    143 sg:pub.10.1007/3-540-45793-3_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002630146
    144 https://doi.org/10.1007/3-540-45793-3_2
    145 rdf:type schema:CreativeWork
    146 sg:pub.10.1007/978-3-540-30550-7_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037447229
    147 https://doi.org/10.1007/978-3-540-30550-7_27
    148 rdf:type schema:CreativeWork
    149 sg:pub.10.1007/978-3-540-70583-3_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031990544
    150 https://doi.org/10.1007/978-3-540-70583-3_19
    151 rdf:type schema:CreativeWork
    152 sg:pub.10.1007/978-3-540-73208-2_31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039600070
    153 https://doi.org/10.1007/978-3-540-73208-2_31
    154 rdf:type schema:CreativeWork
    155 sg:pub.10.1007/978-3-540-76336-9_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025393494
    156 https://doi.org/10.1007/978-3-540-76336-9_9
    157 rdf:type schema:CreativeWork
    158 sg:pub.10.1007/978-3-642-01492-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005381459
    159 https://doi.org/10.1007/978-3-642-01492-5
    160 rdf:type schema:CreativeWork
    161 sg:pub.10.1007/978-3-642-01492-5_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009402049
    162 https://doi.org/10.1007/978-3-642-01492-5_5
    163 rdf:type schema:CreativeWork
    164 sg:pub.10.1007/978-3-642-01492-5_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013273492
    165 https://doi.org/10.1007/978-3-642-01492-5_9
    166 rdf:type schema:CreativeWork
    167 sg:pub.10.1007/978-3-642-02737-6_34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053404068
    168 https://doi.org/10.1007/978-3-642-02737-6_34
    169 rdf:type schema:CreativeWork
    170 sg:pub.10.1007/978-3-642-14455-4_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020627853
    171 https://doi.org/10.1007/978-3-642-14455-4_16
    172 rdf:type schema:CreativeWork
    173 sg:pub.10.1007/978-3-642-59126-6_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000867424
    174 https://doi.org/10.1007/978-3-642-59126-6_1
    175 rdf:type schema:CreativeWork
    176 sg:pub.10.1007/978-3-642-59126-6_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001827630
    177 https://doi.org/10.1007/978-3-642-59126-6_4
    178 rdf:type schema:CreativeWork
    179 sg:pub.10.1007/bf01691346 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038809008
    180 https://doi.org/10.1007/bf01691346
    181 rdf:type schema:CreativeWork
    182 sg:pub.10.1007/bf01704020 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006876172
    183 https://doi.org/10.1007/bf01704020
    184 rdf:type schema:CreativeWork
    185 sg:pub.10.1007/bf01893886 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018745916
    186 https://doi.org/10.1007/bf01893886
    187 rdf:type schema:CreativeWork
    188 sg:pub.10.1007/s00224-004-1096-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1014237043
    189 https://doi.org/10.1007/s00224-004-1096-z
    190 rdf:type schema:CreativeWork
    191 sg:pub.10.1007/s00224-007-9091-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003330683
    192 https://doi.org/10.1007/s00224-007-9091-9
    193 rdf:type schema:CreativeWork
    194 sg:pub.10.1007/s00224-009-9224-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045410699
    195 https://doi.org/10.1007/s00224-009-9224-4
    196 rdf:type schema:CreativeWork
    197 sg:pub.10.1007/s00224-009-9225-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046469438
    198 https://doi.org/10.1007/s00224-009-9225-3
    199 rdf:type schema:CreativeWork
    200 grid-institutes:grid.4488.0 schema:alternateName Faculty of Computer Science, Technische Universität Dresden, 01062, Dresden, Germany
    201 schema:name Faculty of Computer Science, Technische Universität Dresden, 01062, Dresden, Germany
    202 rdf:type schema:Organization
    203 grid-institutes:grid.9008.1 schema:alternateName Department of Computer Science, University of Szeged, Árpád tér 2., 6720, Szeged, Hungary
    204 schema:name Department of Computer Science, University of Szeged, Árpád tér 2., 6720, Szeged, Hungary
    205 rdf:type schema:Organization
     




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


    ...