Skip to main content
Springer Nature Link
Log in

Beyond Regularity: Equational Tree Automata for Associative and Commutative Theories

  • Conference paper
  • First Online:
Computer Science Logic (CSL 2001)

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

Included in the following conference series:

  • 859 Accesses

Abstract

A new tree automata framework, called equational tree automata, is presented. In the newly introduced setting, congruence closures of recognizable tree languages are recognizable. Furthermore, we prove that in certain useful cases, recognizable tree languages are closed under union and intersection. To compare with early related work, e.g. [7], we discuss the relationship between linear bounded automata and equational tree automata. As a consequence, we obtain some (un)decidability results. We further present a hierarchy of 4 classes of tree languages.

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
€32.70 /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
EUR 29.95
Price includes VAT (France)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 85.59
Price includes VAT (France)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 105.49
Price includes VAT (France)
  • 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. R.V. Book and F. Otto: String-Rewriting Systems, Texts and Monographs in Computer Science, Springer-Verlag, 1993.

    Google Scholar 

  2. H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, S. Tison and M. Tommasi: Tree Automata Techniques and Applications, draft, 1997. Available on http://www.grappa.univ-lille3.fr/tata/.

  3. M. Dauchet and S. Tison: The Theory of Ground Rewrite Systems is Decidable, Proc. 5th LICS, Philadelphia (Pennsylvania), pp. 242–248, 1990.

    Google Scholar 

  4. M. Dauchet and S. Tison: Structual Complexity of Classes of Tree Languages, In Tree Automata and Languages, Studies in Computer Science and Artificial Intelligence 10, pp. 327–353, Elsevier Science Publishers B.V., 1992.

    Google Scholar 

  5. A. Deruyver and R. Gilleron: The Reachability Problem for Ground TRS and Some Extensions, Proc. CAAP’89, Barcelona (Spain), LNCS 351, pp. 227–243, 1989.

    Google Scholar 

  6. I. Durand and A. Middeldorp: Decidable Call by Need Computations in Term Rewriting (Extended Abstract), Proc. 14th CADE, Townsville (Australia), LNAI 1249, pp. 4–18, 1997.

    Google Scholar 

  7. R. Gilleron and S. Tison: Regular Tree Languages and Rewriting Systems, Fundamenta Informaticae 24, pp. 157–175, 1995.

    MATH  MathSciNet  Google Scholar 

  8. J.E. Hopcroft and J.D. Ullman: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing Company, 1979.

    Google Scholar 

  9. H. Hosoya, J. Vouillon and B.C. Pierce: Regular Expression Types for XML, Proc. 5th ICFP, Montreal (Canada), SIGPLAN Notices 35(9), pp. 11–22, 2000.

    Google Scholar 

  10. Y. Kaji, T. Fujiwara and T. Kasami: Solving a Unification Problem under Constrained Substitutions Using Tree Automata, Journal of Symbolic Computation 23, pp. 79–117, 1997.

    Article  MATH  MathSciNet  Google Scholar 

  11. D. Lugiez and J.L. Moysset: Tree Automata Help One to Solve Equational Formulae in AC-Theories, Journal of Symbolic Computation 18(4), pp. 297–318, 1994.

    Article  MATH  MathSciNet  Google Scholar 

  12. D. Monniaux: Abstracting Cryptographic Protocols with Tree Automata, Proc. 6th SAS, Venice (Italy), LNCS 1694, pp. 149–163, 1999.

    Google Scholar 

  13. E.L. Post: Recursive Unsolvability of a Problem of Thue, Journal of Symbolic Logic 13, pp. 1–11, 1947.

    MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. National Institute of Advanced Industrial Science and Technology, Nakoji 3-11-46, Amagasaki, 661-0974, Japan

    Hitoshi Ohsaki

Authors
  1. Hitoshi Ohsaki
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. LSV (Ecole Normale Supérieure de Cachan and CNRS), 61, Avenue du Président Wilson, 94230, Cachan, France

    Laurent Fribourg

Rights and permissions

Reprints and permissions

Copyright information

© 2001 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Ohsaki, H. (2001). Beyond Regularity: Equational Tree Automata for Associative and Commutative Theories. In: Fribourg, L. (eds) Computer Science Logic. CSL 2001. Lecture Notes in Computer Science, vol 2142. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44802-0_38

Download citation

  • DOI: https://doi.org/10.1007/3-540-44802-0_38

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-42554-0

  • Online ISBN: 978-3-540-44802-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation