×

Backward and forward bisimulation minimization of tree automata. (English) Zbl 1194.68139

Summary: We improve on an existing [Parosh Aziz Abdulla, Johanna Högberg and Lisa Kaati, Int. J. Found. Comput. Sci. 18, No. 4, 699–713 (2007; Zbl 1143.68428)] bisimulation minimization algorithm for finite-state tree automata by introducing backward and forward bisimulation and developing minimization algorithms for them. Minimization via forward bisimulation is also effective on deterministic tree automata, faster than the previous algorithm, and yields the minimal equivalent deterministic tree automaton. Minimization via backward bisimulation generalizes the previous algorithm and can yield smaller automata but is just as fast. We demonstrate implementations of these algorithms on a typical task in natural language processing.

MSC:

68Q45 Formal languages and automata
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)

Citations:

Zbl 1143.68428
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Hopcroft, J. E., An \(n \log n\) algorithm for minimizing states in a finite automaton, (Theory of Machines and Computations (1971), Academic Press), 189-196
[2] Meyer, A. R.; Stockmeyer, L. J., The equivalence problem for regular expressions with squaring requires exponential space, (Proc. 13th Annual Symp. Foundations of Computer Science (1972), IEEE Computer Society), 125-129
[3] Gramlich, G.; Schnitger, G., Minimizing nfas and regular expressions, (Proc. 22nd Int. Symp. Theoretical Aspects of Computer Science. Proc. 22nd Int. Symp. Theoretical Aspects of Computer Science, LNCS, vol. 3404 (2005), Springer Verlag), 399-411 · Zbl 1118.68525
[4] Gramlich, G.; Schnitger, G., Minimizing nfa’s and regular expressions, Journal of Computer and System Sciences, 73, 6, 908-923 (2007) · Zbl 1152.68459
[5] Gruber, H.; Holzer, M., Inapproximability of nondeterministic state and transition complexity assuming \(P \neq NP\), (Proc. 11th Int. Conf. Developments in Language Theory. Proc. 11th Int. Conf. Developments in Language Theory, LNCS, vol. 4588 (2007), Springer Verlag), 205-216 · Zbl 1202.68226
[6] Abdulla, P. A.; Kaati, L.; Högberg, J., Bisimulation minimization of tree automata, (Proc. 11th Int. Conf. Implementation and Application of Automata. Proc. 11th Int. Conf. Implementation and Application of Automata, LNCS, vol. 4094 (2006), Springer Verlag), 173-185 · Zbl 1160.68395
[7] Abdulla, P. A.; Jonsson, B.; Mahata, P.; d’Orso, J., Regular tree model checking, (Proc. 14th Int. Conf. Computer Aided Verification. Proc. 14th Int. Conf. Computer Aided Verification, LNCS, vol. 2404 (2002), Springer Verlag), 555-568 · Zbl 1010.68087
[8] Knight, K.; Graehl, J., An overview of probabilistic tree transducers for natural language processing, (Proc. 6th Int. Conf. Computational Linguistics and Intelligent Text Processing. Proc. 6th Int. Conf. Computational Linguistics and Intelligent Text Processing, LNCS, vol. 3406 (2005), Springer Verlag), 1-24
[9] Paige, R.; Tarjan, R., Three partition refinement algorithms, SIAM Journal on Computing, 16, 6, 973-989 (1987) · Zbl 0654.68072
[10] H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, S. Tison, M. Tommasi, Tree automata: Techniques and applications. Available on: http://www.grappa.univ-lille3.fr/tata; H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, S. Tison, M. Tommasi, Tree automata: Techniques and applications. Available on: http://www.grappa.univ-lille3.fr/tata
[11] Buchholz, P., Bisimulation relations for weighted automata, Theoretical Computer Science, 393, 1-3, 109-123 (2008) · Zbl 1136.68032
[12] Yu, S., Regular languages, (Word, Language, Grammar. Word, Language, Grammar, Handbook of Formal Languages, vol. 1 (1997), Springer Verlag), 41-110, (Ch. 2)
[13] Abdulla, P. A.; Bouajjani, A.; Holík, L.; Kaati, L.; Vojnar, T., Composed bisimulation for tree automata, (Proc. 13th Int. Conf. Implementation and Applications of Automata. Proc. 13th Int. Conf. Implementation and Applications of Automata, LNCS, vol. 5148 (2008), Springer Verlag), 212-222 · Zbl 1172.68487
[14] Abdulla, P. A.; Högberg, J.; Kaati, L., Bisimulation minimization of tree automata, International Journal of Foundations of Computer Science, 18, 4, 699-713 (2007) · Zbl 1143.68428
[15] Papadimitriou, C. H., Computational Complexity (1994), Addison-Wesley · Zbl 0557.68033
[16] Gécseg, F.; Steinby, M., Tree Automata (1984), Akadémiai Kiadó · Zbl 0396.68041
[17] Gécseg, F.; Steinby, M., Tree languages, (Handbook of Formal Languages, vol. 3 (1997), Springer Verlag), 1-68, (Ch. 1) · Zbl 0396.68041
[18] J. Högberg, A. Maletti, J. May, Backward and forward bisimulation minimisation of tree automata, Tech. Rep. ISI-TR-633, University of Southern California, 2007; J. Högberg, A. Maletti, J. May, Backward and forward bisimulation minimisation of tree automata, Tech. Rep. ISI-TR-633, University of Southern California, 2007 · Zbl 1139.68363
[19] Jelinek, F., Continuous speech recognition by statistical methods, Proceedings of the IEEE, 64, 4, 532-557 (1976)
[20] M. Galley, M. Hopkins, K. Knight, D. Marcu, What’s in a translation rule? in: Proc. 2004 Human Language Technology Conf. of the North American Chapter of the Association for Computational Linguistics, 2004, pp. 273-280; M. Galley, M. Hopkins, K. Knight, D. Marcu, What’s in a translation rule? in: Proc. 2004 Human Language Technology Conf. of the North American Chapter of the Association for Computational Linguistics, 2004, pp. 273-280
[21] Yamada, K.; Knight, K., A syntax-based statistical translation model, (Proc. 39th Meeting of the Association for Computational Linguistics (2001), Morgan Kaufmann), 523-530
[22] Marcus, M. P.; Marcinkiewicz, M. A.; Santorini, B., Building a large annotated corpus of English: The Penn treebank, Computational Linguistics, 19, 2, 313-330 (1993)
[23] May, J.; Knight, K., Tiburon: A weighted tree automata toolkit, (Proc. 11th Int. Conf. Implementation and Application of Automata. Proc. 11th Int. Conf. Implementation and Application of Automata, LNCS, vol. 4094 (2006), Springer Verlag), 102-113 · Zbl 1160.68423
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.