Abstract
We define a weighted monadic second order logic for unranked trees and the concept of weighted unranked tree automata, and we investigate the expressive power of these two concepts. We show that weighted tree automata and a syntactically restricted weighted MSO-logic have the same expressive power in case the semiring is commutative or in case we deal only with ranked trees, but, surprisingly, not in general. This demonstrates a crucial difference between the theories of ranked trees and unranked trees in the weighted case.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abiteboul, S., Bunemann, P., Suciu, D.: Data on the Web. Morgan Kaufmann, San Francisco (2000)
Alexandrakis, A., Bozapalidis, S.: Weighted grammars and Kleene’s theorem. Inf. Process. Lett. 24(1), 1–4 (1987)
Berstel, J., Reutenauer, C.: Recognizable formal power series on trees. Theor. Comput. Sci. 18(2), 115–148 (1982)
Berstel, J., Reutenauer, C.: Rational Series and Their Languages. EATCS-Monographs, vol. 12. Springer, Berlin (1988)
Borchardt, B.: The Theory of Recognizable Tree Series. Ph.D. thesis, TU Dresden, Germany, Verlag für Wissenschaft und Forschung (2004)
Bray, T., Paoli, J., Sperberg-McQueen, C.M.: Extensible Markup Language (XML 1.0 W3C Recommendation). http://www.w3.org/TR/REC-xml/ (1998)
Brüggemann-Klein, A., Murata, M., Wood, D.: Regular tree and regular hedge languages over unranked alphabets: Version 1, April 2001. Technical Report HKUST-TCSC-2001-0, The Hongkong University of Science and Technology (2001)
Brüggemann-Klein, A., Wood, D.: Regular tree languages over non-ranked alphabets. Available at http://citeseer.ist.psu.edu/br98regular.html (1998)
Büchi, J.R.: Weak second-order arithmetic and finite automata. Zeitschr. Math. Logik Grundl. Math. 6, 66–92 (1960)
Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree automata techniques and applications. Available on: http://www.grappa.univ-lille3.fr/tata (1997)
Doner, J.: Tree acceptors and some of their applications. J. Comput. Syst. Sci. 4, 406–451 (1970)
Droste, M., Gastin, P.: Weighted automata and weighted logics. In: Automata, Languages and Programming—32nd International Colloquium, ICALP 2005, Lisbon, Portugal. Lecture Notes in Comput. Sci., vol. 3580, pp. 513–525. Springer, Berlin (2005)
Droste, M., Gastin, P.: Weighted automata and weighted logics. Theor. Comput. Sci. 380(1–2), 69–86 (2007)
Droste, M., Gastin, P.: Weighted automata and weighted logics. In: Droste, M., Kuich, W., Vogler, H. (eds.) Handbook of Weighted Automata. Springer, Berlin (2009). Chap. 5. To appear
Droste, M., Rahonis, G.: Weighted automata and weighted logics with discounting. In: Holub, J., Zdárek, J. (eds.) Proc. of: Implementation and Application of Automata, 12th CIAA, Prague. Lecture Notes in Comp. Sci., vol. 4783, pp. 73–84. Springer, Berlin (2007)
Droste, M., Vogler, H.: Weighted tree automata and weighted logics. Theor. Comput. Sci. 366, 228–247 (2006)
Droste, M., Kuich, W., Vogler, H. (eds.): Handbook of Weighted Automata. Springer, Berlin (2009). To appear
Eilenberg, S.: Automata, Languages, and Machines—Volume A. Pure and Applied Mathematics, vol. 59. Academic Press, New York (1974)
Elgot, C.C.: Decision problems of finite automata design and related arithmetics. Trans. Am. Math. Soc. 98, 21–52 (1961)
Fichtner, I.: Weighted picture automata and weighted logics. Theory Comput. Syst. (2009). To appear
Fülöp, Z., Vogler, H.: Weighted tree automata and tree transducers. In: Droste, M., Kuich, W., Vogler, H. (eds.) Handbook of Weighted Automata. Springer, Berlin (2009). Chap. 9. To appear
Gécseg, F., Steinby, M.: Tree Automata. Springer, Berlin (1984). Akadémiai Kiadó, Budapest
Gécseg, F., Steinby, M.: Tree languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 3, pp. 1–68. Springer, Berlin (1997). Chap. 1
Klarlund, N., Schwentick, Th., Suciu, D.: XML: models, schemas, types, logics, and queries. In: Logics for Emerging Applications on Databases, pp. 1–41. Springer, Berlin (2003)
Kuich, W.: Semirings and formal power series: their relevance to formal languages and automata. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 1, pp. 609–677. Springer, Berlin (1997). Chap. 9
Kuich, W.: Formal power series over trees. In: Bozapalidis, S. (ed.) 3rd International Conference on Developments in Language Theory, DLT 1997, Thessaloniki, Greece, Proceedings, pp. 61–101. Aristotle University of Thessaloniki (1998)
Kuich, W., Salomaa, A.: Semirings, Automata, Languages. Monogr. Theoret. Comput. Sci. EATCS Ser., vol. 5. Springer, Berlin (1986)
Libkin, L.: Logics for unranked trees: an overview. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) Automata, Languages and Programming: 32nd International Colloquium, ICALP 2005, Lisbon, Portugal. Lecture Notes in Comput. Sci., vol. 3580, pp. 35–50. Springer, Berlin (2005)
Libkin, L.: Logics for unranked trees: an overview. Log. Methods Comput. Sci. 2(3:2), 1–31 (2006)
Mathissen, C.: Definable transductions and weighted logics for texts. In: Proc. of the 11th Int. Conf. on Developments in Language Theory (DLT), Turku. Lecture Notes in Comput. Sci., vol. 4588, pp. 324–336. Springer, Berlin (2007)
Mathissen, C.: Weighted logics for nested words and algebraic formal power series. In: Proc. of the 35th Int. Colloquium on Automata, Languages and Programming (ICALP), Reykjavik. Lecture Notes in Comput. Sci., vol. 5126, pp. 221–232. Springer, Berlin (2008)
Meinecke, I.: Weighted logics for traces. In: Proc. of: Computer Science—Theory and Applications, 1st CSR, St. Petersburg. Lecture Notes in Computer Science, vol. 3967, pp. 235–246. Springer, Berlin (2006)
Neven, F.: Design and Analysis of Query Languages for Structured Documents. PhD thesis, University of Limburg (1999)
Neven, F.: Automata, logic, and XML. In: Bradfield, J. (ed.) Computer Science Logic: 16th International Workshop, CSL 2002, Edinburgh, Scotland, UK. Lecture Notes in Comput. Sci., vol. 2471, pp. 2–26. Springer, Berlin (2002)
Neven, F., Schwentick, Th.: Query automata over finite trees. Theor. Comput. Sci. 275, 633–674 (2002)
Rahonis, G.: Weighted Muller tree automata and weighted logics. J. Autom. Lang. Program. 12, 455–483 (2007)
Salomaa, A., Soittola, M.: Automata-Theoretic Aspects of Formal Power Series. Texts and Monographs in Computer Science. Springer, Berlin (1978)
Seidl, H., Schwentick, T., Muscholl, A.: Numerical document queries. In: IEEE Symposium on Principles of Database Systems, pp. 155–166. ACM Press, New York (2003)
Seidl, H., Schwentick, T., Muscholl, A., Habermehl, P.: Counting in trees for free. In: Proc. 31st International Colloq. on Automata, Languages, and Programming, ICALP. Lecture Notes in Comput. Sci., vol. 3142, pp. 1136–1149. Springer, Berlin (2004)
Schützenberger, M.P.: On the definition of a family of automata. Inf. Control 4, 245–270 (1961)
Thatcher, J.W.: Characterizing derivation trees of context-free grammars through a generalization of finite automata theory. J. Comput. Syst. Sci. 4, 317–322 (1967)
Thatcher, J.W., Wright, J.B.: Generalized finite automata theory with an application to a decision problem of second-order logic. Math. Syst. Theory 2(1), 57–81 (1968)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Droste, M., Vogler, H. Weighted Logics for Unranked Tree Automata. Theory Comput Syst 48, 23–47 (2011). https://doi.org/10.1007/s00224-009-9224-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-009-9224-4