A Medvedev Characterization of Recognizable Tree Series

From International Center for Computational Logic

Toggle side column

A Medvedev Characterization of Recognizable Tree Series

Luisa HerrmannLuisa Herrmann
Luisa Herrmann
A Medvedev Characterization of Recognizable Tree Series
In Émilie Charlier, Julien Leroy, Michel Rigo, eds., Developments in Language Theory, volume 10396 of Lecture Notes in Computer Science, 210-221, 2017. Springer
  • KurzfassungAbstract
    We introduce representable tree series over commutative semirings, which extend representable sets 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.
  • Projekt:Project: QuantLA
  • Forschungsgruppe:Research Group: Computational LogicComputational Logic
The final publication is available at Springer via http://dx.doi.org/https://doi.org/10.1007/978-3-319-62809-7_15.
@inproceedings{H2017,
  author    = {Luisa Herrmann},
  title     = {A Medvedev Characterization of Recognizable Tree Series},
  editor    = {{\'{E}}milie Charlier and Julien Leroy and Michel Rigo},
  booktitle = {Developments in Language Theory},
  series    = {Lecture Notes in Computer Science},
  volume    = {10396},
  publisher = {Springer},
  year      = {2017},
  pages     = {210-221},
  doi       = {https://doi.org/10.1007/978-3-319-62809-7_15}
}