Ambiguity hierarchies for weighted tree automata. (English) Zbl 07770235
Summary: 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.
MSC:
| 68Q45 | Formal languages and automata |
References:
| [1] | Berstel, J. and Reutenauer, C., Recognizable formal power series on trees, Theoret. Comput. Sci.18(2) (1982) 115-148. · Zbl 0485.68077 |
| [2] | Berstel, J. and Reutenauer, C., Rational Series and Their Languages (Springer, 1988). · Zbl 0668.68005 |
| [3] | B. Borchardt, The theory of recognizable tree series, PhD thesis, Technische Universität Dresden (2005). · Zbl 1115.68419 |
| [4] | Bozapalidis, S. and Louscou-Bozapalidou, O., The rank of a formal tree power series, Theoret. Comput. Sci.27(1-2) (1983) 211-215. · Zbl 0537.68053 |
| [5] | Chattopadhyay, A., Mazowiecki, F., Muscholl, A. and Riveros, C., Pumping lemmas for weighted automata, Logical Methods in Computer Science (LMCS)17(3) (2021). · Zbl 1487.68143 |
| [6] | Comon, H., Dauchet, M., Gilleron, R., Löding, C., Jacquemard, F., Lugiez, D., Tison, S. and Tommasi, M., Tree automata techniques and applications (2007). |
| [7] | Doner, J. E., Tree acceptors and some of their applications, J. Comput. System Sci.4(5) (1970) 406-451. · Zbl 0212.02901 |
| [8] | Droste, M., Kuich, W. and Vogler, H. (eds.), Handbook of Weighted Automata (Springer, 2009). · Zbl 1200.68001 |
| [9] | Ésik, Z. and Maletti, A., The category of simulations for weighted tree automata, Int. J. Found. Comput. Sci.22(8) (2011) 1845-1859. · Zbl 1244.68046 |
| [10] | Fülöp, Z. and Vogler, H., Weighted tree automata and tree transducers, Handbook of weighted automata, eds. Droste, M., Kuich, W. and Vogler, H. (Springer, 2009), pp. 313-403. · Zbl 1484.68085 |
| [11] | Gécseg, F. and Steinby, M., Tree Automata (Akadémiai Kiadó, Budapest, 1984). · Zbl 0537.68056 |
| [12] | Gécseg, F. and Steinby, M., Tree languages, Handbook of Formal Languages, eds. Rozenberg, G. and Salomaa, A., 3 (Springer, 1997), pp. 1-68. · Zbl 0866.68057 |
| [13] | Golan, J. S., Semirings and their Applications (Kluwer Academic, Dordrecht, 1999). · Zbl 0947.16034 |
| [14] | Hall, T. E. and Sapir, M. V., Idempotents, regular elements and sequences from finite semigroups, Discrete Math.161(1-3) (1996) 151-160. · Zbl 0871.20051 |
| [15] | Hebisch, U. and Weinert, H. J., Semirings—Algebraic Theory and Applications in Computer Science (World Scientific, 1998). · Zbl 0934.16046 |
| [16] | Högberg, J., Maletti, A. and Vogler, H., Bisimulation minimisation of weighted automata on unranked trees, Fundam. Inform.92(1-2) (2009) 103-130. · Zbl 1191.68388 |
| [17] | Klimann, I., Lombardy, S., Mairesse, J. and Prieur, C., Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton, Theoret. Comput. Sci.327(3) (2004) 349-373. · Zbl 1071.68035 |
| [18] | Krob, D., The equality problem for rational series with multiplicities in the tropical semiring is undecidable, Internat. J. Algebra Comput.4(3) (1994) 405-425. · Zbl 0834.68058 |
| [19] | Maletti, A., Nasz, T., Stier, K. and Ulbricht, M., Ambiguity hierarchies for weighted tree automata, International Conference on Implementation and Application of Automata, Springer (2021), pp. 140-151. · Zbl 07495111 |
| [20] | Mazowiecki, F. and Riveros, C., Pumping lemmas for weighted automata, Proc. 35th STACS, LIPIcs96, (2018). · Zbl 1487.68151 |
| [21] | Paul, E., On finite and polynomial ambiguity of weighted tree automata, Proc. 20th DLT, LNCS9840, (Springer, 2016), pp. 368-379. · Zbl 1436.68186 |
| [22] | Paul, E., The equivalence, unambiguity and sequentiality problems of finitely ambiguous max-plus tree automata are decidable, Proc. 42nd MFCS, LIPIcs83, (2017). · Zbl 1441.68128 |
| [23] | Paul, E., Finite sequentiality of unambiguous max-plus tree automata, Proc. 36th STACS, LIPIcs126, (2019). · Zbl 1517.68212 |
| [24] | Rabusseau, G., Balle, B. and Cohen, S. B., Low-rank approximation of weighted tree automata, Proc. 19th AISTATS, JMLR51, (JMLR.org, 2016), pp. 839-847. |
| [25] | Sakarovitch, J., Rational and recognisable power series, Handbook of Weighted Automata, eds. Droste, M., Kuich, W. and Vogler, H. (Springer, 2009), pp. 105-174. · Zbl 1484.68110 |
| [26] | Salomaa, A. and Soittola, M., Automata-Theoretic Aspects of Formal Power Series (Springer, 2012). · Zbl 0377.68039 |
| [27] | Simon, I., Limited subsets of a free monoid, Proc. 19th FOCS, (IEEE, 1978), pp. 143-150. |
| [28] | Thatcher, J. W., Characterizing derivation trees of context-free grammars through a generalization of finite automata theory, J. Comput. System Sci.1(4) (1967) 317-322. · Zbl 0155.01802 |
| [29] | Yu, S., Regular languages, Handbook of Formal Languages, eds. Rozenberg, G. and Salomaa, A., 1 (Springer, 1997), pp. 41-110. · Zbl 0866.68057 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
