iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://unpaywall.org/10.1007/3-540-44669-9_32
Polynomial Time Algorithms for Finding Unordered Tree Patterns with Internal Variables | SpringerLink
Skip to main content
Springer Nature Link
Log in

Polynomial Time Algorithms for Finding Unordered Tree Patterns with Internal Variables

  • Conference paper
  • First Online:
Fundamentals of Computation Theory (FCT 2001)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2138))

Included in the following conference series:

  • 452 Accesses

Abstract

Many documents such as Web documents or XML files have tree structures. A term tree is an unordered tree pattern consisting of internal variables and tree structures. In order to extract meaningful and hidden knowledge from such tree structured documents, we consider a minimal language (MINL) problem for term trees. The 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 contain all given tree structured data. Firstly, we show that the MINL problem for regular term trees is computable in polynomial time if the number of edge labels is infinite. Next, we show that the MINL problems with optimizing the size of an output term tree are NP-complete. Finally, in order to show that our polynomial time algorithm for the MINL problem can be applied to data mining from real-world Web documents, we show that regular term tree languages are polynomial time inductively inferable from positive data if the number of edge labels is infinite.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. T. R. Amoth, P. Cull, and P. Tadepalli. Exact learning of unordered tree patterns from queries. Proc. COLT-99, ACM Press, pages 323–332, 1999.

    Google Scholar 

  2. D. Angluin. Finding patterns common to a set of strings. Journal of Computer and System Science, 21:46–62, 1980.

    Article  MATH  MathSciNet  Google Scholar 

  3. H. Arimura, T. Shinohara, and S. Otsuki. Polynomial time algorithm for finding finite unions of tree pattern languages. Proc. NIL-91, Springer-Verlag, LNAI 659, pages 118–131, 1993.

    Google Scholar 

  4. S. Goldman and S. Kwek. On learning unions of pattern languages and tree patterns. Proc. ALT-99, Springer-Verlag, LNAI 1720, 1720:347–363, 1999.

    Google Scholar 

  5. S. Matsumoto, Y. Hayashi, and T. Shoudai. Polynomial time inductive inference of regular term tree languages from positive data. Proc. ALT-97, Springer-Verlag, LNAI 1316, pages 212–227, 1997.

    Google Scholar 

  6. T. Miyahara, T. Shoudai, T. Uchida, T. Kuboyama, K. Takahashi, and H. Ueda. Discovering new knowledge from graph data using inductive logic programming. Proc. ILP-99, Springer-Verlag, LNAI 1634, pages 222–233, 1999.

    Google Scholar 

  7. T. Miyahara, T. Shoudai, T. Uchida, K. Takahashi, and H. Ueda. Polynomial time matching algorithms for tree-like structured patterns in knowledge discovery. Proc. PAKDD-2000, Springer-Verlag, LNAI 1805, pages 5–16, 2000.

    Google Scholar 

  8. T. Miyahara, T. Shoudai, T. Uchida, K. Takahashi, and H. Ueda. Discovery of frequent tree structured patterns in semistructured web documents. Proc. PAKDD-2001, Springer-Verlag, LNAI 2035, pages 47–52, 2001.

    Google Scholar 

  9. S. Nestorov, S. Abiteboul, and R. Motwani. Extracting schema from semistructured data. Proceedings of ACM SIGMOD International Conference on Management of Data, pages 295–306, 1998.

    Google Scholar 

  10. T. Shinohara. Polynomial time inference of extended regular pattern languages. In Springer-Verlag, LNCS 147, pages 115–127, 1982.

    Google Scholar 

  11. T. Shoudai, T. Miyahara, T. Uchida, and S. Matsumoto. Inductive inference of regular term tree languages and its application to knowledge discovery. Information Modelling and Knowledge Bases XI, IOS Press, pages 85–102, 2000.

    Google Scholar 

  12. K. Wang and H. Liu. Discovering structural association of semistructured data. IEEE Trans. Knowledge and Data Engineering, 12:353–371, 2000.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Informatics, Kyushu University, Kasuga, 816-8580, Japan

    Takayoshi Shoudai

  2. Faculty of Information Sciences, Hiroshima City University, Hiroshima, 731-3194, Japan

    Tomoyuki Uchida & Tetsuhiro Miyahara

Authors
  1. Takayoshi Shoudai
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tomoyuki Uchida
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Tetsuhiro Miyahara
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. University of Latvia, Raiņa bulvaris 29, LV-1459, Riga, Latvia

    Rūsiņš Freivalds

Rights and permissions

Reprints and permissions

Copyright information

© 2001 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Shoudai, T., Uchida, T., Miyahara, T. (2001). Polynomial Time Algorithms for Finding Unordered Tree Patterns with Internal Variables. In: Freivalds, R. (eds) Fundamentals of Computation Theory. FCT 2001. Lecture Notes in Computer Science, vol 2138. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44669-9_32

Download citation

  • DOI: https://doi.org/10.1007/3-540-44669-9_32

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-42487-1

  • Online ISBN: 978-3-540-44669-9

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation