A Medvedev Characterization of Recognizable Tree Series

Luisa HerrmannLuisa Herrmann

DOI Link

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

Details
Bibtex

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}
}