Skip to main content
Springer Nature Link
Log in

Tree Automata for Non-linear Arithmetic

  • Conference paper
Rewriting Techniques and Applications (RTA 2008)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5117))

Included in the following conference series:

Abstract

Tree automata modulo associativity and commutativity axioms, called AC tree automata, accept trees by iterating the transition modulo equational reasoning. The class of languages accepted by monotone AC tree automata is known to include the solution set of the inequality \(x \times y \geqslant z\), which implies that the class properly includes the AC closure of regular tree languages. In the paper, we characterize more precisely the expressiveness of monotone AC tree automata, based on the observation that, in addition to polynomials, a class of exponential constraints (called monotone exponential Diophantine inequalities) can be expressed by monotone AC tree automata with a minimal signature. Moreover, we show that a class of arithmetic logic consisting of monotone exponential Diophantine inequalities is definable by monotone AC tree automata. The results presented in the paper are obtained by applying our novel tree automata technique, called linearly bounded projection.

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

Access this chapter

Log in via an institution

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. Baader, F., Nipkow, T.: Term Rewriting and All That. Cambridge University Press, Cambridge (1998)

    Google Scholar 

  2. Boneva, I., Talbot, J.-M., Tison, S.: Expressiveness of a Spatial Logic for Trees. In: Proc. of 20th LICS, Chicago (USA), pp. 280–289. IEEE Computer Society, Los Alamitos (2005)

    Google Scholar 

  3. Comon-Lundh, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree Automata Techniques and Applications, draft (2005), http://www.grappa.univ-lille3.fr/tata

  4. Dal Zilio, S., Lugiez, D.: XML Schema, Tree Logic and Sheaves Automata. Applicable Algebra in Engineering, Communication and Computing 17, 337–377 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  5. Ginsburg, S., Spanier, E.H.: Semigroups, Presburger Formulas, and Languages. Pacific Journal of Mathematics 16, 285–296 (1966)

    MATH  MathSciNet  Google Scholar 

  6. Ginsburg, S.: The Mathematical Theory of Context-Free Languages. McGraw-Hill, New York (1966)

    MATH  Google Scholar 

  7. Hack, M.H.T.: Decidability Questions for Petri Nets, Ph.D. thesis, Massachusetts Institute of Technology, USA (1976)

    Google Scholar 

  8. Henzinger, T.A.: The Theory of Hybrid Automata. In: Proc. of 11th LICS, New Brunswick (USA). IEEE Computer Society, Los Alamitos (1996) (Extended version), http://mtc.epfl.ch/~tah/Publications

    Google Scholar 

  9. Hinman, P.G.: Fundamentals of Mathematical Logic. A K Peters (2005)

    Google Scholar 

  10. Kobayashi, N., Ohsaki, H.: Tree Automata for Non-Linear Arithmetic, draft (February 2008), http://staff.aist.go.jp/hitoshi.ohsaki/

  11. Kudlek, M., Mitrana, V.: Normal Forms of Grammars, Finite Automata, Abstract Families, and Closure Properties of Multiset Languages. In: Calude, C.S., Pun, G., Rozenberg, G., Salomaa, A. (eds.) Multiset Processing. LNCS, vol. 2235, pp. 135–146. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  12. Landweber, L.H.: Properties of Vector Addition Systems, Technical Report 258, University of Wisconsin-Madison, USA (1975)

    Google Scholar 

  13. Lugiez, D.: Multitree Automata That Count. TCS 333, 225–263 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  14. Matiyasevich, Y.: Hilbert’s Tenth Problem. MIT Press, Cambridge (1993)

    Google Scholar 

  15. Ohsaki, H., Talbot, J.-M., Tison, S., Roos, Y.: Monotone AC-Tree Automata. In: VMCAI 2006. LNCS (LNAI), vol. 3855, pp. 337–351. Springer, Heidelberg (2005)

    Google Scholar 

  16. Ohsaki, H., Seki, H., Takai, T.: Recognizing Boolean Closed A-Tree Languages with Membership Conditional Rewriting Mechanism. In: Nieuwenhuis, R. (ed.) RTA 2003. LNCS, vol. 2706, pp. 483–498. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  17. Ohsaki, H.: Beyond Regularity: Equational Tree Automata for Associative and Commutative Theories. In: Fribourg, L. (ed.) CSL 2001 and EACSL 2001. LNCS, vol. 2142, pp. 539–553. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  18. Parikh, R.: On Context-Free Languages. JACM 13, 570–581 (1966)

    Article  MATH  MathSciNet  Google Scholar 

  19. Seidl, H., Schwentick, T., Muscholl, A.: Numerical Document Queries. In: Proc. of 22nd PODS, SanDiego (USA), pp. 155–166. ACM, New York (2003)

    Google Scholar 

  20. Thatcher, J.W.: Characterizing Derivation Trees of Context-Free Grammars Through a Generalization of Automata Theory. Journal of Computer and System Sciences 1, 317–322 (1967)

    MATH  MathSciNet  Google Scholar 

  21. Verma, K.N., Goubault-Larrecq, J.: Alternating Two-Way AC-Tree Automata. Information and Computation 205, 817–869 (2007)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Tohoku University, Japan

    Naoki Kobayashi

  2. National Institute of Advanced Industrial Science and Technology, Japan

    Hitoshi Ohsaki

Authors
  1. Naoki Kobayashi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hitoshi Ohsaki
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Andrei Voronkov

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Kobayashi, N., Ohsaki, H. (2008). Tree Automata for Non-linear Arithmetic. In: Voronkov, A. (eds) Rewriting Techniques and Applications. RTA 2008. Lecture Notes in Computer Science, vol 5117. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-70590-1_20

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-70590-1_20

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-70588-8

  • Online ISBN: 978-3-540-70590-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation