摘要：We consider the problem of minimising the number of states in a multiplicitytree automaton over the field of rational numbers. We give a minimisationalgorithm that runs in polynomial time assuming unit-cost arithmetic. We alsoshow that a polynomial bound in the standard Turing model would require abreakthrough in the complexity of polynomial identity testing by proving thatthe latter problem is logspace equivalent to the decision version ofminimisation. The developed techniques also improve the state of the art inmultiplicity word automata: we give an NC algorithm for minimising multiplicityword automata. Finally, we consider the minimal consistency problem: does thereexist an automaton with $n$ states that is consistent with a given finitesample of weight-labelled words or trees? We show that this decision problem iscomplete for the existential theory of the rationals, both for words and fortrees of a fixed alphabet rank.
关键词：Computer Science - Formal Languages and Automata Theory
