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.

Borgwardt, S., Penaloza, R. (2011). The Inclusion Problem for Weighted Automata on Infinite Trees. In Proceedings of the 13th International Conference on Automata and Formal Languages (AFL'11) (pp.108-122). Institute of Mathematics and Computer Science of Nyíregyháza College.

The Inclusion Problem for Weighted Automata on Infinite Trees

Penaloza, R
2011

Abstract

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.
paper
weighted automata, complexity theory
English
International Conference on Automata and Formal Languages (AFL'11)
13th
Dömösi, P; Iván, S
Proceedings of the 13th International Conference on Automata and Formal Languages (AFL'11)
978-615-5097-19-5
2011
108
122
open
Borgwardt, S., Penaloza, R. (2011). The Inclusion Problem for Weighted Automata on Infinite Trees. In Proceedings of the 13th International Conference on Automata and Formal Languages (AFL'11) (pp.108-122). Institute of Mathematics and Computer Science of Nyíregyháza College.
File in questo prodotto:
File Dimensione Formato  
BoPe-AFL11.pdf

accesso aperto

Tipologia di allegato: Author’s Accepted Manuscript, AAM (Post-print)
Dimensione 495.66 kB
Formato Adobe PDF
495.66 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/257699
Citazioni
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
Social impact