Bisimulation Minimisation of Weighted Automata on Unranked Trees

• Autorzy: Högberg J. , Maletti A.
• Języki publikacji: EN

Abstrakty

EN

Several models of automata are available that operate unranked trees. Two well-known examples are the stepwise unranked tree automaton (suta) and the parallel unranked tree automaton (puta). By adding a weight, taken from some semiring, to every transition we generalise these two qualitative automata models to quantitative models, thereby obtaining weighted stepwise unranked tree automata (wsuta) and weighted parallel unranked tree automata (wputa); the qualitative automata models are reobtained by choosing the BOOLEAN semiring. The weighted versions have applications in natural language processing, XML-based data management and quantitative information retrieval. We address the minimisation problem of wsuta and wputa by using (forward and backward) bisimulations and we prove the following results: (1) for every wsuta an equivalent forward (resp. backward) bisimulation minimal wsuta can be computed in time O(mn) where n is the number of states and m is the number of transitions of the given wsuta; (2) the same result is proved for wputa instead of wsuta; (3) if the semiring is additive cancellative or the BOOLEAN semiring, then the bound can be improved to O(mlog n) for both wsuta and wputa; (4) for every deterministic puta we can compute a minimal equivalent deterministic puta in time O(mlog n); (5) the automata models wsuta, wputa, and weighted unranked tree automaton have the same computational power.

Słowa kluczowe

EN

bisimulation; minimisation; automata; unranked trees

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 92, nr 1-2
• Strony: 103--130
• Opis fizyczny: Bibliogr. 36 poz.

Twórcy

autor

Högberg J.

autor

Maletti A.

• Faculty of Computer Science, Technische Universit¨at Dresden D-01062 Dresden, Germany

Bibliografia

• [1] Abdulla, P. A., Hőgberg, J., Kaati, L.: Bisimulation Minimization of Tree Automata, Int. J. Foundations of Computer Science, 18(4), 2007, 699-713.
• [2] Abiteboul, S., Bunemann, P., Suciu, D.: Data on the Web: From Relations to Semistructured Data and XML, Morgan Kaufmann, 1999.
• [3] Alexandrakis, A., Bozapalidis, S.: Weighted grammars and Kleene's theorem., Information Processing Letters, 24(1), 1987, 1-4.
• [4] Berstel, J., Reutenauer, C.: Recognizable Formal Power Series on Trees, Theoretical Computer Science, 18(2), 1982, 115-148.
• [5] Bistarelli, S., Montanari, U., Rossi, F.: Semiring-based Constraint Logic Programming: Syntax and Semantics, ACM Transactions on Programming Languages and Systems, 23(1), 2001, 1-29.
• [6] Borchardt, B.: The theory of recognizable tree series, Akademische Abhandlungen zur Informatik, Verlag für Wissenschaft und Forschung, 2005.
• [7] Brüggemann-Klein, A., Murata, M., Wood, D.: Regular tree and regular hedge languages over unranked alphabets, Technical Report HKUST-TCSC-2001-0, The Hongkong University of Science and Technology, 2001.
• [8] Buchholz, P.: Bisimulation Relations for Weighted Automata, Theoretical Computer Science, 393(1-3), 2008, 109-123.
• [9] Carme, J., Niehren, J., Tommasi, M.: Querying unranked trees with stepwise tree automata, Proc. 15th Int. Conf. Rewriting Techniques and Applications, 3091, Springer, 2004.
• [10] Cristau, J., Lőding, C., Thomas, W.: Deterministic Automata on Unranked Trees, Proc. 15th Int. Symp. Fundamentals of Computation Theory, 3623, Springer, 2005.
• [11] Droste, M., Kuich,W., Vogler, H., Eds.: Handbook of Weighted Automata, Springer, 2008, To appear.
• [12] Droste, M., Pech, C., Vogler, H.: A Kleene Theorem for Weighted Tree Automata, Theory of Computing Systems, 38(1), 2005, 1-38, ISSN 1432-4350.
• [13] Droste, M., Vogler, H.: Weighted logics for XML, 2008, Manuscript.
• [14] Eilenberg, S.: Automata, Languages, and Machines - Volume A, vol. 59 of Pure and Applied Mathematics, Academic Press, 1974.
• [15] Ésik, Z., Kuich,W.: Formal Tree Series, J. Automata, Languages and Combinatorics, 8(2), 2003, 219-285.
• [16] Flesca, S., Furfaro, F., Greco, S.: Weighted path queries on semistructured databases, Information and Computation, 204(5), 2006, 679-696.
• [17] Fülőp, Z., Vogler, H.: Weighted tree automata and tree transducers, in: Handbook of Weighted Automata, chapter 9, Springer, 2009, To appear.
• [18] Gécseg, F., Steinby, M.: Tree Automata, Akadémiai Kiadó, 1984.
• [19] Gécseg, F., Steinby, M.: Tree Languages, in: Handbook of Formal Languages, vol. 3, chapter 1, Springer, 1997, 1-68.
• [20] Golan, J.: Semirings and their applications, Kluwer Academic, 1999.
• [21] Gramlich, G., Schnitger, G.: Minimizing NFAs and Regular Expressions, Proc. 22nd Int. Symp. Theoretical Aspects of Computer Science, 3404, Springer, 2005.
• [22] Hőgberg, J., Maletti, A., May, J.: Backward and forward bisimulation minimisation of tree automata, Technical Report ISI-TR-633, University of Southern California, 2007.
• [23] Hőgberg, J., Maletti, A., May, J.: Backward and forward bisimulation minimisation of tree automata, Proc. 12th Int. Conf. Implementation and Application of Automata, 4783, Springer, 2007.
• [24] Hőgberg, J., Maletti, A., May, J.: Bisimulation minimisation for weighted tree automata, Proc. 11th Int. Conf. Developments in Language Theory, 4588, Springer, 2007.
• [25] Hőgberg, J., Maletti, A., May, J.: Bisimulation minimisation for weighted tree automata, Technical Report ISI-TR-634, University of Southern California, 2007.
• [26] Jiang, T., Ravikumar, B.: Minimal NFA problems are hard, SIAM Journal of Computing, 22(6), 1993, 1117-1141.
• [27] Jurafsky, D.,Martin, J.: Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics and Speech Recognition, Second edition, Prentice Hall, February 2008.
• [28] Klarlund, N., Schwentick, T., Suciu, D.: XML: Models, Schemas, Types, Logics, and Queries, Proc. Dagstuhl Seminar: Logics for Emerging Applications on Databases, Springer, 2003.
• [29] Kuich,W.: Formal Power Series over Trees, Proc. 3rd Int. Conf. Developments in Language Theory (S. Bozapalidis, Ed.), Aristotle University of Thessaloniki, 1997.
• [30] Malcher, A.: Minimizing finite automata is computationally hard, Theoretical Computer Science, 327(3), 2004, 375-390.
• [31] Martens, W., Niehren, J.: Minimizing Tree Automata for Unranked Trees., Proc. 10th Int. Symp. Database Programming Languages, 3774, Springer, 2005.
• [32] Meyer, A., Stockmeyer, L.: The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space, Proc. 13th Symp. Foundations of Computer Science, IEEE Computer Society, 1972.
• [33] Milner, R.: A Calculus of Communicating Systems, Springer, 1982.
• [34] Neven, F.: Automata, logic, and XML, Proc. 16th Int. Workshop Computer Science Logic, 2471, Springer, 2002.
• [35] Schützenberger,M.: On the definition of a family of automata, Information and Control, 4, 1961, 245-270.
• [36] Stüber, T., Vogler, H.: Weighted monadic datalog, Theoretical Computer Science, 403(2-3), 2008, 221-238.