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.
%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
}
