%0 Journal Article %1 Maletti2023-pp %A Maletti, Andreas %A Nasz, Teodora %A Stier, Kevin %A Ulbricht, Markus %D 2023 %I World Scientific Pub Co Pte Ltd %J Int. J. Found. Comput. Sci. %K automata hierarchies tree from:scadsfct weighted Ambiguity %N 08 %P 903--921 %T Ambiguity hierarchies for weighted tree automata %V 34 %X Weighted tree automata (WTA) extend classical weighted automata (WA) to the non-linear structure of trees. The expressive power of WA with varying degrees of ambiguity has been extensively studied. Unambiguous, finitely ambiguous, and polynomially ambiguous WA over the tropical (as well as the arctic) semiring strictly increase in expressive power. The recently developed pumping results of Mazowiecki and Riveros (STACS 2018) are lifted to trees in order to achieve the same strict hierarchy for WTA over the tropical (as well as the arctic) semiring.

@article{Maletti2023-pp, abstract = {Weighted tree automata (WTA) extend classical weighted automata (WA) to the non-linear structure of trees. The expressive power of WA with varying degrees of ambiguity has been extensively studied. Unambiguous, finitely ambiguous, and polynomially ambiguous WA over the tropical (as well as the arctic) semiring strictly increase in expressive power. The recently developed pumping results of Mazowiecki and Riveros (STACS 2018) are lifted to trees in order to achieve the same strict hierarchy for WTA over the tropical (as well as the arctic) semiring.}, added-at = {2025-01-07T12:36:48.000+0100}, author = {Maletti, Andreas and Nasz, Teodora and Stier, Kevin and Ulbricht, Markus}, biburl = {https://puma.scadsai.uni-leipzig.de/bibtex/2345faf3dc41ada8dff8b0a5333e3a563/scads.ai}, interhash = {6f21ce8f1017a5f815ceb0069b20dc32}, intrahash = {345faf3dc41ada8dff8b0a5333e3a563}, journal = {Int. J. Found. Comput. Sci.}, keywords = {automata hierarchies tree from:scadsfct weighted Ambiguity}, language = {en}, month = dec, number = 08, pages = {903--921}, publisher = {World Scientific Pub Co Pte Ltd}, timestamp = {2025-01-07T12:36:48.000+0100}, title = {Ambiguity hierarchies for weighted tree automata}, volume = 34, year = 2023 }