Skip to main content
SpringerLink
Log in
Book cover

International Conference on Developments in Language Theory

DLT 2017: Developments in Language Theory pp 210–221Cite as

A Medvedev Characterization of Recognizable Tree Series

  • Conference paper
  • First Online:

  • 602 Accesses

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

Abstract

We introduce representable tree series over commutative semirings, which extend representable sets [10] to the weighted setting. We prove that restricted representable tree series are exactly those tree series that can be recognized by weighted tree automata. Moreover, we investigate the relation between unrestricted representable tree series and weighted monadic second-order logic.

Supported by DFG Graduiertenkolleg 1763 (QuantLA).

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

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 EPUB and 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

Learn about institutional subscriptions

Notes

  1. 1.

    Note that here the notion of representable tree series is different from the one in [3].

  2. 2.

    In \(\mathrm {MSO}(\varSigma )\), \(\lnot \) can appear anywhere.

References

  1. Berstel, J., Reutenauer, C.: Recognizable formal power series on trees. Theor. Comput. Sci. 18(2), 115–148 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  2. Berstel, J., Reutenauer, C.: Rational Series and Their Languages. EATCS Monographs on Theoretical Computer Science, vol. 12. Springer, Heidelberg (1988)

    Book  MATH  Google Scholar 

  3. Bozapalidis, S.: Representable tree series. Fundam. Inf. 21(4), 367–389 (1994)

    MathSciNet  MATH  Google Scholar 

  4. Costich, O.L.: A Medvedev characterization of sets recognized by generalized finite automata. Math. Syst. Theor. 6(1–2), 263–267 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  5. Droste, M., Gastin, P.: Weighted automata and weighted logics. Theor. Comput. Sci. 380(1), 69–86 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  6. Droste, M., Götze, D., Märcker, S., Meinecke, I.: Weighted tree automata over valuation monoids and their characterization by weighted logics. In: Kuich, W., Rahonis, G. (eds.) Algebraic Foundations in Computer Science. LNCS, vol. 7020, pp. 30–55. Springer, Heidelberg (2011). doi:10.1007/978-3-642-24897-9_2

    Chapter  Google Scholar 

  7. Droste, M., Vogler, H.: Weighted tree automata and weighted logics. Theor. Comput. Sci. 366, 228–247 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  8. Droste, M., Vogler, H.: Weighted logics for unranked tree automata. Theor. Comput. Syst. 48(1), 23–47 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  9. Fülöp, Z., Vogler, H.: Weighted tree automata and tree transducers. In: Droste, M., Kuich, W., Vogler, H. (eds.) Handbook of Weighted Automata, pp. 313–403. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  10. Medvedev, Y.T.: On the class of events representable in a finite automaton. Automata Studies (1956). Also in Sequential machines - Selected papers (translated from Russian), pp. 215–227. Addison-Wesley (1964)

    Google Scholar 

Download references

Acknowledgement

The author thanks Tobias Denkinger and Johannes Osterholzer for several useful discussions concerning the content of this work.

Author information

Authors and Affiliations

  1. Faculty of Computer Science, Technische Universität Dresden, Nöthnitzer Str. 46, 01062, Dresden, Germany

    Luisa Herrmann

Authors
  1. Luisa Herrmann
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Luisa Herrmann .

Editor information

Editors and Affiliations

  1. Université de Liège, Liège, Belgium

    Émilie Charlier

  2. Université de Liège, Liège, Belgium

    Julien Leroy

  3. Université de Liège, Liège, Belgium

    Michel Rigo

Rights and permissions

Reprints and permissions

Copyright information

© 2017 Springer International Publishing AG

About this paper

Cite this paper

Herrmann, L. (2017). A Medvedev Characterization of Recognizable Tree Series. In: Charlier, É., Leroy, J., Rigo, M. (eds) Developments in Language Theory. DLT 2017. Lecture Notes in Computer Science(), vol 10396. Springer, Cham. https://doi.org/10.1007/978-3-319-62809-7_15

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-62809-7_15

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-62808-0

  • Online ISBN: 978-3-319-62809-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation