The Inclusion Problem for Weighted Automata on Infinite Trees

Stefan BorgwardtStefan Borgwardt, Rafael PeñalozaRafael Peñaloza

Download

Stefan Borgwardt, Rafael Peñaloza
The Inclusion Problem for Weighted Automata on Infinite Trees
In Pál Dömösi and Szabolcs Iván, eds., Proceedings of the 13th International Conference on Automata and Formal Languages (AFL'11), 108-122, 2011. College of Nyíregyháza

Details
Bibtex

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 paper we study the problems of intersection, complementation and inclusion for weighted automata on infinite trees and show that they are not harder complexity-wise than reasoning with unweighted automata. We also present explicit methods for solving these problems optimally.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ BoPe-AFL11,
  address = {Debrecen, Hungary},
  author = {Stefan {Borgwardt} and Rafael {Pe{\~n}aloza}},
  booktitle = {Proceedings of the 13th International Conference on Automata and Formal Languages (AFL'11)},
  editor = {P{\'a}l {D{\"o}m{\"o}si} and Szabolcs {Iv{\'a}n}},
  pages = {108--122},
  publisher = {College of Ny{\'i}regyh{\'a}za},
  title = {The Inclusion Problem for Weighted Automata on Infinite Trees},
  year = {2011},
}