%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 Ambiguity Zno automata hierarchies tree weighted %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/scadsfct}, interhash = {6f21ce8f1017a5f815ceb0069b20dc32}, intrahash = {345faf3dc41ada8dff8b0a5333e3a563}, journal = {Int. J. Found. Comput. Sci.}, keywords = {Ambiguity Zno automata hierarchies tree weighted}, language = {en}, month = dec, number = 08, pages = {903--921}, publisher = {World Scientific Pub Co Pte Ltd}, timestamp = {2025-02-17T11:21:10.000+0100}, title = {Ambiguity hierarchies for weighted tree automata}, volume = 34, year = 2023 }