Abstract
We consider the problem of minimising the number of states in a multiplicity tree automaton over the field of rational numbers. We give a minimisation algorithm that runs in polynomial time assuming unit-cost arithmetic. We also show that a polynomial bound in the standard Turing model would require a breakthrough in the complexity of polynomial identity testing by proving that the latter problem is logspace equivalent to the decision version of minimisation. The developed techniques also improve the state of the art in multiplicity word automata: we give an NC algorithm for minimising multiplicity word automata. Finally, we consider the minimal consistency problem: does there exist an automaton with n states that is consistent with a given finite sample of weight-labelled words or trees? We show that this decision problem is complete for the existential theory of the rationals, both for words and for trees of a fixed alphabet rank.
Chapter PDF
Similar content being viewed by others
References
Berstel, J., Reutenauer, C.: Recognizable formal power series on trees. Theoretical Computer Science 18(2), 115–148 (1982)
Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and real computation. Springer (1997)
Borchardt, B.: A pumping lemma and decidability problems for recognizable tree series. Acta Cybern. 16(4), 509–544 (2004)
Bozapalidis, S.: Effective construction of the syntactic algebra of a recognizable series on trees. Acta Inf. 28(4), 351–363 (1991)
Bozapalidis, S., Alexandrakis, A.: Représentations matricielles des séries d’arbre reconnaissables. RAIRO-Theoretical Informatics and Applications-Informatique Théorique et Applications 23(4), 449–459 (1989)
Bozapalidis, S., Louscou-Bozapalidou, O.: The rank of a formal tree power series. Theoretical Computer Science 27(1), 211–215 (1983)
Brainerd, W.S.: The minimalization of tree automata. Information and Control 13(5), 484–491 (1968)
Canny, J.: Some algebraic and geometric computations in PSPACE. In: Proceedings of STOC 1988, pp. 460–467. ACM (1988)
Carlyle, J.W., Paz, A.: Realizations by stochastic finite automata. Journal of Computer and System Sciences 5(1), 26–40 (1971)
Carme, J., Gilleron, R., Lemay, A., Terlutte, A., Tommasi, M.: Residual finite tree automata. In: Ésik, Z., Fülöp, Z. (eds.) DLT 2003. LNCS, vol. 2710, pp. 171–182. Springer, Heidelberg (2003)
Carrasco, R.C., Daciuk, J., Forcada, M.L.: An implementation of deterministic tree automata minimization. In: Holub, J., Žďárek, J. (eds.) CIAA 2007. LNCS, vol. 4783, pp. 122–129. Springer, Heidelberg (2007)
Cho, S., Huynh, D.T.: The parallel complexity of finite-state automata problems. Inf. Comput. 97(1), 1–22 (1992)
Cook, S.A.: A taxonomy of problems with fast parallel algorithms. Information and Control 64(1-3), 2–22 (1985)
Cortes, C., Mohri, M., Rastogi, A.: On the computation of some standard distances between probabilistic automata. In: Ibarra, O.H., Yen, H.-C. (eds.) CIAA 2006. LNCS, vol. 4094, pp. 137–149. Springer, Heidelberg (2006)
Csanky, L.: Fast parallel matrix inversion algorithms. SIAM J. Comput. 5(4), 618–623 (1976)
Fliess, M.: Matrices de Hankel. Journal de Mathématiques Pures et Appliquées 53, 197–222 (1974)
Gold, E.M.: Complexity of automaton identification from given data. Information and Control 37(3), 302–320 (1978)
Habrard, A., Oncina, J.: Learning multiplicity tree automata. In: Sakakibara, Y., Kobayashi, S., Sato, K., Nishino, T., Tomita, E. (eds.) ICGI 2006. LNCS (LNAI), vol. 4201, pp. 268–280. Springer, Heidelberg (2006)
Ibarra, O.H., Moran, S., Rosier, L.E.: A note on the parallel complexity of computing the rank of order n matrices. Information Processing Letters 11(4/5), 162 (1980)
Jiang, T., Ravikumar, B.: Minimal NFA problems are hard. SIAM J. Comput. 22(6), 1117–1141 (1993)
Kiefer, S., Marusic, I., Worrell, J.: Minimisation of multiplicity tree automata. Technical report, arxiv.org (2014), http://arxiv.org/abs/1410.535
Kiefer, S., Murawski, A., Ouaknine, J., Wachter, B., Worrell, J.: On the complexity of equivalence and minimisation for ℚ-weighted automata. Logical Methods in Computer Science 9(1) (2013)
Maletti, A.: Minimizing deterministic weighted tree automata. Inf. Comput. 207(11), 1284–1299 (2009)
Marusic, I., Worrell, J.: Complexity of equivalence and learning for multiplicity tree automata. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds.) MFCS 2014, Part I. LNCS, vol. 8634, pp. 414–425. Springer, Heidelberg (2014)
Schützenberger, M.P.: On the definition of a family of automata. Information and Control 4(2-3), 245–270 (1961)
Seidl, H.: Deciding equivalence of finite tree automata. SIAM J. Comput. 19(3), 424–437 (1990)
Tzeng, W.-G.: A polynomial-time algorithm for the equivalence of probabilistic automata. SIAM J. Comput. 21(2), 216–227 (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kiefer, S., Marusic, I., Worrell, J. (2015). Minimisation of Multiplicity Tree Automata. In: Pitts, A. (eds) Foundations of Software Science and Computation Structures. FoSSaCS 2015. Lecture Notes in Computer Science(), vol 9034. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-46678-0_19
Download citation
DOI: https://doi.org/10.1007/978-3-662-46678-0_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-46677-3
Online ISBN: 978-3-662-46678-0
eBook Packages: Computer ScienceComputer Science (R0)