Abstract
Due to the rapid growth of tree structured data or semistructured data such as Web documents, efficient learning of structural features from tree structured data becomes more and more important. In order to represent tree structured patterns with rich structural features, we introduce a new type of structural variables, called height-constrained variables. An (i,j)-height-constrained variable can be replaced with any tree such that the trunk length of the tree is at least i and the height of the tree is at most j. Then, we define a term tree as a rooted tree pattern with ordered children and height-constrained variables. The minimal language (MINL) problem for term trees is to find a term tree t such that the language generated by t is minimal among languages, generated by term trees, which contains all given tree structured data. Let \(\mathcal{OTT}^h\) be the set of all term trees with (i,j)-height-constrained variables for any i and j (1 ≤ i ≤ j) and no variable-chain. We assume that there are at least two edge labels. In this paper, we give a polynomial time algorithm for the MINL problem for \(\mathcal{OTT}^h\). Thus we show that the class \(\mathcal{OTT}^h\) is polynomial time inductively inferable from positive data.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abiteboul, S., Buneman, P., Suciu, D.: Data on the web: From relations to semistructured data and XML. Morgan Kaufmann, San Francisco (2000)
Aikou, K., Suzuki, Y., Shoudai, T., Uchida, T., Miyahara, T.: A Polynomial Time Matching Algorithm of Structured Ordered Tree Patterns with Height-Constrained Variables (2004) (to be submitted)
Amoth, T.R., Cull, P., Tadepalli, P.: On exact learning of unordered tree patterns. Machine Learning 44, 211–243 (2001)
Angluin, D.: Inductive inference of formal languages from positive data. Information and Control 45, 117–135 (1980)
Arimura, H., Sakamoto, H., Arikawa, S.: Efficient learning of semi-structured data from queries. In: Abe, N., Khardon, R., Zeugmann, T. (eds.) ALT 2001. LNCS (LNAI), vol. 2225, pp. 315–331. Springer, Heidelberg (2001)
Matsumoto, S., Suzuki, Y., Shoudai, T., Miyahara, T.: Learning of Finite Unions of Tree Patterns with Repeated Internal Structured Variables from Queries. In: Gavaldá, R., Jantke, K.P., Takimoto, E. (eds.) ALT 2003. LNCS (LNAI), vol. 2842, pp. 144–158. Springer, Heidelberg (2003)
Miyahara, T., Suzuki, Y., Shoudai, T., Uchida, T., Hirokawa, S., Takahashi, K., Ueda, H.: Extraction of tag tree patterns with contractible variables from irregular semistructured data. In: Whang, K.-Y., Jeon, J., Shim, K., Srivastava, J. (eds.) PAKDD 2003. LNCS (LNAI), vol. 2637, pp. 430–436. Springer, Heidelberg (2003)
Moriyama, T., Sato, M.: Properties of language classes with finite elasticity. IEICE Transactions on Information and Systems E-78-D(5), 532–538 (1995)
Suzuki, Y., Akanuma, R., Shoudai, T., Miyahara, T., Uchida, T.: Polynomial time inductive inference of ordered tree patterns with internal structured variables from positive data. In: Kivinen, J., Sloan, R.H. (eds.) COLT 2002. LNCS (LNAI), vol. 2375, pp. 169–184. Springer, Heidelberg (2002)
Suzuki, Y., Shoudai, T., Uchida, T., Miyahara, T.: Ordered term tree languages which are polynomial time inductively inferable from positive data. In: Cesa-Bianchi, N., Numao, M., Reischuk, R. (eds.) ALT 2002. LNCS (LNAI), vol. 2533, pp. 188–202. Springer, Heidelberg (2002)
Suzuki, Y., Shoudai, T., Matsumoto, S., Uchida, T.: Efficient Learning of Unlabeled Term Trees with Contractible Variables from Positive Data. In: Horváth, T., Yamamoto, A. (eds.) ILP 2003. LNCS (LNAI), vol. 2835, pp. 347–364. Springer, Heidelberg (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Suzuki, Y., Shoudai, T., Matsumoto, S., Miyahara, T. (2004). Polynomial Time Inductive Inference of Ordered Tree Languages with Height-Constrained Variables from Positive Data. In: Zhang, C., W. Guesgen, H., Yeap, WK. (eds) PRICAI 2004: Trends in Artificial Intelligence. PRICAI 2004. Lecture Notes in Computer Science(), vol 3157. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-28633-2_24
Download citation
DOI: https://doi.org/10.1007/978-3-540-28633-2_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22817-2
Online ISBN: 978-3-540-28633-2
eBook Packages: Springer Book Archive