Complementation and Inclusion of Weighted Automata on Infinite Trees: Revised Version

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche
Toggle side column

Complementation and Inclusion of Weighted Automata on Infinite Trees: Revised Version

Stefan BorgwardtStefan Borgwardt,  Rafael PeñalozaRafael Peñaloza
Stefan Borgwardt, Rafael Peñaloza
Complementation and Inclusion of Weighted Automata on Infinite Trees: Revised Version
Technical Report, Chair for Automata Theory, Institute for Theoretical Computer Science, Technische Universität Dresden, volume 11-02, 2011. LTCS-Report
  • KurzfassungAbstract
    Weighted automata can be seen as a natural generalization of finite state automata to more complex algebraic structures. The standard reasoning tasks for unweighted automata can also be generalized to the weighted setting. In this report we study the problems of intersection, complementation, and inclusion for weighted automata on infinite trees and show that they are not harder than reasoning with unweighted automata. We also present explicit methods for solving these problems optimally.
  • Bemerkung: Note: See http://lat.inf.tu-dresden.de/research/reports.html.
  • Forschungsgruppe:Research Group: Automatentheorie
@techreport{ BoPe-LTCS-11-02,
  address = {Dresden, Germany},
  author = {Stefan {Borgwardt} and Rafael {Pe{\~n}aloza}},
  institution = {Chair for Automata Theory, Institute for Theoretical Computer Science, Technische Universit{\"a}t Dresden},
  note = {See http://lat.inf.tu-dresden.de/research/reports.html.},
  number = {11-02},
  title = {Complementation and Inclusion of Weighted Automata on Infinite Trees: Revised Version},
  type = {LTCS-Report},
  year = {2011},
}