# A Büchi-Like Theorem for Weighted Tree Automata over Multioperator Monoids

Ontology type: schema:ScholarlyArticle

### Article Info

DATE

2010-10-28

AUTHORS 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
• ### Journal

TITLE

Theory of Computing Systems

ISSUE

2

VOLUME

50

### 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:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"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",
}
],
"keywords": [
"operation",
"results",
"formula",
"logic",
"carrier set",
"series",
"transition",
"transformation",
"set",
"main results",
"automata",
"vice",
"class",
"fact",
"theorem",
"syntactical transformations",
"expression",
"implications",
"recognizability",
"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",
"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"
}
]

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'

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
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
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
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
76 schema:sdPublisher N0721cc25d32047ff8027f07ea80aba2a
77 schema:url https://doi.org/10.1007/s00224-010-9296-1
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
91 rdf:rest rdf:nil
92 N7280aab7f9bf43c9b107b1a1f2728c1e rdf:first sg:person.014007607055.43
93 rdf:rest N53ed244fcbaa4d6cb3ed4fede332a86e
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