Skip to main content
SpringerLink
Log in

Super-state automata and rational trees

  • Conference paper
  • First Online:
LATIN'98: Theoretical Informatics (LATIN 1998)

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

Included in the following conference series:

Abstract

We introduce the notion of super-state automata constructed from other automata. This construction is used to solve an open question about enumerative sequences in rational trees. We prove that any IN-rational sequence s=(s n)n≥0 of nonnegative integers satisfying the Kraft inequality σn≥0 s n k −n ≤1 is the enumerative sequence of leaves by height of a k-ary rational tree. This result had been conjectured and was known only in the case of strict inequality. We also give a new proof of a result about enumerative sequences of nodes in k-ary rational trees.

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.

References

  1. R. L. Adler, D. Coppersmith, and M. Hassner. Algorithms for sliding block codes. I.E.E.E. Trans. Inform. Theory, IT-29:5–22, 1983.

    Article  MathSciNet  Google Scholar 

  2. F. Bassino, M.-P. Béal, and D. Perrin. Enumerative sequences of leaves and nodes in rational trees. Theoret. Comput. Sci., 1997. (to appear).

    Google Scholar 

  3. F. Bassino, M.-P. Béal, and D. Perrin. Enumerative sequences of leaves in rational trees. In ICALP'97, LNCS 1256, pages 76–86. Springer, 1997.

    Google Scholar 

  4. M.-P. Béal. Codage Symbolique. Masson, 1993.

    Google Scholar 

  5. M.-P. Béal and D. Perrin. Symbolic dynamics and finite automata. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume 2, chapter 10. Springer-Verlag, 1997.

    Google Scholar 

  6. J. Berstel and C. Reutenauer. Rational Series and their Languages Springer-Verlag, 1988.

    Google Scholar 

  7. D. Lind and B. Marcus. An Introduction to Symbolic Dynamics and Coding Cambridge, 1995.

    Google Scholar 

  8. B. Marcus. Factors and extensions of full shifts. Monats.Math, 88:239–247, 1979.

    Article  MATH  Google Scholar 

  9. D. Perrin. Arbres et séries rationnelles. C.R.A.S. Paris, Série I, 309:713–716, 1989.

    MATH  MathSciNet  Google Scholar 

  10. D. Perrin. A conjecture on rational sequences. In R. Capocelli, editor, Sequences, pages 267–274. Springer-Verlag, 1990.

    Google Scholar 

  11. A. Salomaa and M. Soittola. Automata-theoretic Aspect of Formal Power Series. Springer-Verlag, Berlin, 1978.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut Gaspard Monge, Université de Marne-la-Vallée, 2, rue de la butte verte, 93166, Noisy le Grand Cedex, France

    Frédérique Bassino & Dominique Perrin

  2. Institut Gaspard Monge, Université Paris 7, France

    Marie -Pierre Béal

Authors
  1. Frédérique Bassino
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Marie -Pierre Béal
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Dominique Perrin
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Cláudio L. Lucchesi Arnaldo V. Moura

Rights and permissions

Reprints and permissions

Copyright information

© 1998 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Bassino, F., Béal, M.P., Perrin, D. (1998). Super-state automata and rational trees. In: Lucchesi, C.L., Moura, A.V. (eds) LATIN'98: Theoretical Informatics. LATIN 1998. Lecture Notes in Computer Science, vol 1380. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0054309

Download citation

  • DOI: https://doi.org/10.1007/BFb0054309

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-64275-6

  • Online ISBN: 978-3-540-69715-2

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation