Weighted automata with storage

From International Center for Computational Logic

Toggle side column

Weighted automata with storage

Luisa HerrmannLuisa Herrmann,  Heiko VoglerHeiko Vogler,  Manfred DrosteManfred Droste
Luisa Herrmann, Heiko Vogler, Manfred Droste
Weighted automata with storage
Information and Computation, 269, 2019
  • KurzfassungAbstract
    We consider finite-state automata that are equipped with a storage. Moreover, the transitions are weighted by elements of a unital valuation monoid. A weighted automaton with storage recognizes a weighted language, which is a mapping from input strings to elements of the carrier set of the unital valuation monoid. For the class of weighted languages recognizable by such automata we prove closure properties, a Chomsky-Schützenberger theorem, and a Büchi-Elgot-Trakhtenbrot theorem. In case of idempotent, locally finite, and sequential unital valuation monoids, the recognized weighted languages are step functions.
  • Projekt:Project: QuantLA
  • Forschungsgruppe:Research Group: Computational Logic
@article{HVD2019,
  author    = {Luisa Herrmann and Heiko Vogler and Manfred Droste},
  title     = {Weighted automata with storage},
  journal   = {Information and Computation},
  volume    = {269},
  publisher = {Elsevier},
  year      = {2019},
  doi       = {https://doi.org/10.1016/j.ic.2019.104447}
}