Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Recognizing Boolean Closed A-Tree Languages with Membership Conditional Rewriting Mechanism

  • Conference paper
  • First Online:

Abstract

This paper provides an algorithm to compute the complement of tree languages recognizable with A-TA (tree automata with associativity axioms [16]). Due to this closure property together with the previously obtained results, we know that the class is boolean closed, while keeping recognizability of A-closures of regular tree languages. In the proof of the main result, a new framework of tree automata, calledsequence-tree automata, is introduced as a generalization of Lugiez and Dal Zilio’s multi-tree automata [14] of an associativity case. It is also shown that recognizable A-tree languages are closed under a one-step rewrite relation in case of ground A-term rewriting. This result allows us to compute an under-approximation of A-rewrite descendants of recognizable A-tree languages with arbitrary accuracy.

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

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /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
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • 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

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. F. Baader and T. Nipkow:Term Rewriting and All That, Cambridge University Press, 1998.

    Google Scholar 

  2. L. Bachmair and D.A. Plaisted:Associative Path Orderings, Proc. of 1st RTA, Dijon (France), LNCS 202, pp. 241–254, 1985.

    Google Scholar 

  3. M. Bezem, R. de Vrijer, and J.W. Klop (eds.):Term Rewriting Systems, Cambridge Tracts in Theoretical Computer Science 55, Cambridge University Press, 2003.

    Google Scholar 

  4. H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, S. Tison, and M. Tommasi:Tree Automata Techniques and Applications, 2002. Draft available onhttp://www.grappa.univ-lille3.fr/tata/

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

    Google Scholar 

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

    Google Scholar 

  7. A. Finkel and Ph. Schnoebelen:Well-Structured Transition Systems Everywhere!, Theoretical Computer Science 256, pp. 63–92, 2001.

    Article MATH MathSciNet  Google Scholar 

  8. F. Gécseg and M. Steinby:Tree Languages, Handbook of Formal Languages 3, pp. 1–68 (Chapter 1), Springer-Verlag, 1996.

    Google Scholar 

  9. J. Goubault-Larrecq and K.N. Verma:Alternating Two-Way AC-Tree Automata, Research Report LSV-02-11, ENS de Cachan (France), 2002.

    Google Scholar 

  10. M. Hamana:Term Rewriting with Sequences, Proc. of 1st Theorema Workshop, Hagenberg (Austria), 1997. Draft included in technical report 97-20, RISC-Linz.

    Google Scholar 

  11. N. Immerman:Nondeterministic Space is Closed Under Complementation, SIAM Journal on Computing 17(5), pp. 935–938, 1988.

    Article MATH MathSciNet  Google Scholar 

  12. S.Y. Kuroda:Classes of Languages and Linear Bounded Automata, Information and Control 7, pp. 207–223, 1964.

    Article MATH MathSciNet  Google Scholar 

  13. T. Kutsia:Unification in the Empty and Flat Theories with Sequence Variables and Flexible Arity Symbols, technical report 01-13, RISC-Linz, 2001. Available onhttp://www.sfb013.uni-linz.ac.at/~sfb/reports/2001/ps-files/

  14. D. Lugiez and S. Dal Zilio:Multitrees Automata, Presburger’s Constraints and Tree Logics, technical report 08-2002, LIF-CNRS-Université Provence, 2002. Available onhttp://www.lim.univ-mrs.fr/Rapports/

  15. A. Mateescu and A. Salomaa:Aspects of Classical Language Theory, Handbook of Formal Languages 1, pp. 175–251 (Chapter 4), Springer-Verlag, 1996.

    Google Scholar 

  16. H. Ohsaki:Beyond Regularity: Equational Tree Automata for Associative and Commutative Theories, Proc. of 15th CSL, Paris (France), LNCS 2142, pp. 539–553, 2001.

    Google Scholar 

  17. H. Ohsaki and T. Takai:Decidability and Closure Properties of Equational Tree Languages, Proc. of 13th RTA, Copenhagen (Denmark), LNCS 2378, pp. 114–128, 2002.

    Google Scholar 

  18. H. Ohsaki and T. Takai:A Tree Automata Theory for Unification Modulo Equational Rewriting, 16th UNIF, Copenhagen (Denmark), 2002. Draft available fromhttp://staff.aist.go.jp/hitoshi.ohsaki/unif2002.ps.gz

  19. H. Ohsaki, H. Seki, and T. Takai:Recognizable A-Tree Languages are Boolean Closed, technical report AIST-PS-2003-001, Programming Science Group, AIST, 2003. The revised version with the new title (Recognizing Boolean Closed A-Tree Languages with Membership Conditional Rewriting Mechanism) is available fromhttp://staff.aist.go.jp/hitoshi.ohsaki/rta2003.ps.gz

  20. Y. Toyama:Membership Conditional Term Rewriting Systems, Trans. of IEICE E72(11), pp. 1224–1229, 1989.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. PRESTO “Information and Systems”, Japan Science and Technology Corporation, Japan

    Hitoshi Ohsaki

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

    Hitoshi Ohsaki & Toshinori Takai

  3. Nara Institute of Science and Technology, Takayama 8916-5, Ikoma, 630-0192, Japan

    Hiroyuki Seki

Authors
  1. Hitoshi Ohsaki

    You can also search for this author inPubMed Google Scholar

  2. Hiroyuki Seki

    You can also search for this author inPubMed Google Scholar

  3. Toshinori Takai

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Dpt. Lenguajes y Sistemas Informáticos (LSI), Technical University of Catalonia (UPC), Jordi Girona 1, 08034, Barcelona, Spain

    Robert Nieuwenhuis

Rights and permissions

Copyright information

© 2003 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Ohsaki, H., Seki, H., Takai, T. (2003). Recognizing Boolean Closed A-Tree Languages with Membership Conditional Rewriting Mechanism. In: Nieuwenhuis, R. (eds) Rewriting Techniques and Applications. RTA 2003. Lecture Notes in Computer Science, vol 2706. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44881-0_34

Download citation

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /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
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • 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

[8]ページ先頭
©2009-2025 Movatter.jp