2025/09/18 by Fülöp, Zoltán, Vogler, Heiko
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.2509.14914
Due to the works of S. Bozapalidis and A. Alexandrakis, there is a well-known characterization of recognizable weighted tree languages over fields in terms of finite-dimensionality of syntactic vector spaces. Here we prove a characterization of bottom-up deterministically recognizable weighted tree languages over commutative semifields in terms of the requirement that the respective m-syntactic scalar algebras are finitely generated. The concept of scalar algebra is introduced in this paper; it is obtained from the concept of vector space by disregarding the addition of vectors. Moreover, we prove a minimization theorem for bottom-up-deterministic weighted tree automata and we construct the minimal automaton.